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.

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

## 5 comments:

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.

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

"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?

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

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.

Post a Comment