Consider the recursion Fk = Fk−1 + Fk−2, k ≥ 2, with F0 = 0 and F1 = 1. Prove
that Fk is even if and only if 3 | k. In other words, prove that, modulo 2, F3t = 0,
F3t+1 = 1, and F3t+2 = 1 for t ≥ 0.
I'm just having some trouble solving the above proof. I see why it works (because odd + odd = even, even + odd = odd, etc), but I cannot prove it with induction.
Nov 12th 2012, 09:10 PM
Re: Fibonacci Proof Help
Instead of looking at each individual step, look at each set of paired steps and prove that each paired step has only one even and odd result in that pair and that the order of each pair (in terms of being even or odd) is the same for each pair.