Pages

Thursday, June 21, 2012

The even fibonacci

Prove that F[2n] cannot be of the form 4k+2, where F[i] is ith Fibonacci number. (F[0] = 0, F[1] = 1 etc...)

5 comments:

Aakash N S said...

My Solution :
First, note that F[n](mod 4) depends only on F[n-1](mod 4) and F[n-2](mod 4).
F[0] = 0 = 0 mod 4
F[1] = 1 = 1 mod 4
F[2] = 1 = 1 mod 4
F[3] = 2 = 2 mod 4
F[4] = 3 = 3 mod 4
F[5] = 5 = 1 mod 4
F[6] = 8 = 0 mod 4
F[7] = 13 = 1 mod 4

Note that (F[6], F[7]) == (F[0], F[1]) (mod 4). Thus the sequence repeats with period of size 6. Thus, as is clear from the sequence, the only candidates for F[2n] (mod 4) are 0, 1, and 3. Q.E.D.

Vinod Kumar Reddy G said...

F[n] = 1*F[n-1]+1*F[n-2]
=> F[n] = F[2]*F[n-1]+F[1]*F[n-2]
=> F[n] = F[3]*F[n-2]+F[2]*F[n-3]
in general F[n] = F[k+1]*F[n-k]+F[k]*F[n-k-1] for any k < n;
now put n = 2*n and k = n in above equation
we get F[2*n] = F[n]*(F[n-1]+F[n+1])
now in above equation if F[n] is even then both F[n-1] and F[n+1] should be odd leaking F[2*n] as a multiple of 4.
if F[n] is odd then one of F[n-1] and F[n+1] should be odd and the other even
leaving F[2*n] odd.
From above results F[2n] cannot be of the form 4k+2

Aakash N S said...

"if F[n] is even then both F[n-1] and F[n+1] should be odd leaking F[2*n] as a multiple of 4." How can you claim that?

pathankhan salman said...

What he meant was that F[n-1] + F[n+1] will be even if F[n] is even. Is it so vinod?

Vinod Kumar Reddy G said...

if F[n] is even and if any of F[n-1] and F[n+1] are even then whole sequence will be even integers which contradicts the base case f[1] = 1.