[seqfan] Re: Gilbreath on Fibonacci

[Robert Dougherty-Bliss]

Even better, this example generalizes to arbitrary initial conditions.

If a(n) = a(n - 1) + a(n) with initial conditions a(0) = x and a(1) = y,
then
the Gilbreath transform of a(n) is eventually periodic, repeating 0, gcd(x,
y),
gcd(x, y) forever.

Here are the first 20 terms of the Gilbreath transform of sequences with
different initial conditions (x, y):

    (0, 1): 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1
    (2, 10): 8, 6, 2, 4, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0
    (5, 15): 10, 5, 5, 0, 5, 5, 0, 5, 5, 0, 5, 5, 0, 5, 5, 0, 5, 5, 0
    (20, 6): 14, 6, 8, 2, 6, 4, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2, 2, 0, 2

And here are the first 40 terms of (101, 7):

    94, 7, 87, 80, 7, 73, 66, 7, 59, 52, 7, 45, 38, 7,
    31, 24, 7, 17, 10, 7, 3, 4, 1, 3, 2, 1, 1, 0, 1, 1,
    0, 1, 1, 0, 1, 1, 0, 1, 1.

This is because the initial conditions (x, y) are eventually taken to
either (y
mod x, x) or (-y mod x, x), and applying this repeatedly leads to (0, gcd(x,
y)), which cycles.

Robert

On Tue, Sep 19, 2023 at 4:33 AM Jakob Schulz <bruderjakob17 at gmail.com>
wrote:

> Dear Sean,
>
> You can also just look back one row for a formal proof: Let d(n, 0) :=
> F(n), and d(n, k+1) := |d(n, k) - d(n+1, k).
>
> Claim: d(n, k) = ...
> ... F(n-k) if n >= k
> ... 0 if n <= k and n and k are equivalent mod 3
> ... 1 if n <= k and n and k are not equivalent mod 3
>
> (Note that the patterns overlap if n=k, but they result in the same value.)
>
> Now, do induction on k. The case k = 0 is trivial.
>
> In the induction step, do a case distinction:
> Case 1: n >= k + 1
> Case 2: n < k + 1
> ...Case 2.1: n and k+1 are equivalent mod 3
> ...Case 2.2: n+1 and k+1 are equivalent mod 3
> ...Case 2.3: n+2 and k+1 are equivalent mod 3
>
> Inserting the induction hypothesis and doing simple calculations (using
> that F(n+1-k)-F(n-k) = F(n-(k+1)) in Case 1) finishes the proof of the
> claim.
>
> Best,
> Jakob
>
>
> El mar., 19 sept. 2023 4:01, Sean A. Irvine <sairvin at gmail.com> escribió:
>
> > Hi,
> >
> > In terms of getting some traction on the sequences arising from the
> > Gilbreath transform, it looks to me like the Gilbreath transform of the
> > Fibonacci numbers which is apparently 0,1,1 repeated should be easy to
> > prove. In this case, terms with index >= n in row n, are simply the
> > Fibonacci numbers themselves and that after each set of three rows we
> have
> > one additional copy of 0,1,1 at the start of the row.  So I think you
> could
> > make this more formal with some kind of induction looking back 3 rows?
> >
> > 1:  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
> > 2:  1, 0, 1, 1, 2, 3, 5,  8, 13, 21, 34, 55, ...
> > 3:  1, 1, 0, 1, 1, 2, 3,  5,  8, 13, 21, 34, ...
> > 4:  0, 1, 1, 0, 1, 1, 2,  3,  5,  8, 13, 21, ...
> > 5:  1, 0, 1, 1, 0, 1, 1,  2,  3,  5,  8, 13, ...
> > 6:  1, 1, 0, 1, 1, 0, 1,  1,  2,  3,  5,  8, ...
> > 7:  0, 1, 1, 0, 1, 1, 0,  1,  1,  2,  3,  5, ...
> > ...
> >
> > Sean.
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>