Odd/even Fibonacci numbers

[morbius27]

Hi, I'm trying to prove by induction that Fn (the fibonacci sequence) is even if and only if n is divisble by 3.
I know that there should be separate arguments for indices of the form 3m, 3m-1, and 3m-2 with m being a natural number, and the proof must go both ways (since it has a bi conditional) but I have no idea how to apply induction to prove the claim.

Any help is much appreciated.

 

[tutor_joel]

You know Fibonacci? The recursive definition

\(\displaystyle F_n = F_{n-1} + F_{n-2} \;where\; n\ge3\)

Check it . some proofs there.

 

[daon]

Hi, I'm trying to prove by induction that Fn (the fibonacci sequence) is even if and only if n is divisble by 3.
I know that there should be separate arguments for indices of the form 3m, 3m-1, and 3m-2 with m being a natural number, and the proof must go both ways (since it has a bi conditional) but I have no idea how to apply induction to prove the claim.

Any help is much appreciated.

Here's one direction:

Base: F1,F2 are odd, F3 is even.

F(3(k+1))=F(3k+3) = F(3k+2)+F(3k+1) = F(3k)+2F(3k+1). Assuming F(3k) is even, we have the sum of two even numbers.