Here is a question from our problem set...

FIbonacci numbers are defined as F0=0; F1=1, and for all k >= 2 Fk = Fk-1 + Fk-2. Use strong induction to prove the following

property of Fibonacci numbers: Fn+m-2 = FnFm-1 + Fn-1Fm-2. Here n>=2 , m>=2. Please point out the part of the proof where you had to use strong induction.

Hint: you should do induction on n only and assume that m is fixed. The

other way around (induction on m with n fixed) should work as well, but you

cannot do induction on both.