[seqfan] Proof of A000350 conjecture

[David Wilson]

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.