## 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, F = 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 mod 4
F = 1 = 1 mod 4
F = 1 = 1 mod 4
F = 2 = 2 mod 4
F = 3 = 3 mod 4
F = 5 = 1 mod 4
F = 8 = 0 mod 4
F = 13 = 1 mod 4

Note that (F, F) == (F, F) (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*F[n-1]+F*F[n-2]
=> F[n] = F*F[n-2]+F*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.