[seqfan] Re: Proof of A000350 conjecture

[Max Alekseyev]

I've added a comment to A000350 about that some time ago.
Actually, even stronger congruences hold: modulo 3*2^d.
Max

On Tue, Jul 14, 2009 at 10:34 AM, David Wilson<dwilson at gambitcomm.com> wrote:
> On A000350, it is conjectured that in binary, Fib(n) ends in n only for
> n in {0,1,5}. Here is a proof.
>
> Lemma: For d >= 0
>
>     [1] Fib(n) == n (mod 2^d)  ==>  n in {0,1,5} (mod 2^d).
>
> Proof:
>
> The base case 0 <= d <= 3 can be verified exhaustively.
>
> For the recursive case, assume [1] holds for some d = k >= 3. We now
> prove [1] for d = k+1.
>
> Let Fib(n) == n (mod 2^(k+1)). Then Fib(n) == n (mod 2^k), and by our
> hypothesis, n in {0,1,5} (mod 2^k), so n in {0,1,5,2^k,2^k+1,2^k+5} (mod
> 2^(k+1)). For k >= 3, analysis mod 8 rules out Fib(n) == n for n in
> {2^k,2^k+1,2^k+5} (mod 8) so we cannot have n in {2^k,2^k+1,2^k+5} (mod
> 2^(k+1)), leaving n in {0,1,5} (mod 2^(k+1)), QED.
>
> Theorem: If Fib(n) ends in n in binary, then n in {0,1,5}.
>
> Proof: Let Fib(n) end in n in binary. This is equivalent to Fib(n) == n
> (mod 2^d) where d is the number of binary digits in n. Our theorem then
> gives n in {0,1,5} (mod 2^d). Whereas n has d binary digits, n < 2^d,
> hence n in {0,1,5}, QED.
>
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>