# [seqfan] Proof of A000350 conjecture

David Wilson dwilson at gambitcomm.com
Tue Jul 14 16:34:42 CEST 2009

```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.

```