>>43-46
Mazeltov
!
It can be tricky for beginners. This is a good final gateway problem for students learning induction. It's not as straightforward as the other beginning induction proofs, which tend to follow the pattern of assuming the inductive hypothesis, substituting, and simplifying. The inductive hypothesis doesn't give you every thing you need at first, since it only applies to the odd term fibonacci numbers. But you get around that by expressing the even term fibs in terms of the two adjacent odd term fibs. Then the following algebraic manipulation requires more substitutions using the definition of the fibonacci numbers. It's not that hard, especially if you've seen or done more complex proofs, but it can trip up people that are still learning the procedure.