We use the following recursive definition of the Fibonacci numbers,

Prove that for all we have,

*Proof.*For the case , we have and

So, the inequality is true for . Assume then that the inequality is true for some . Then,

But, as one can compute, . Hence,

Thus, the inequality holds for all

The formatting is off, it should say “for all n less than k with k greater than 2”

Hi, shouldn’t this proof be by strong induction on n? i.e. you would need to show that the claim holds for both n=1 and n=2, then assume that the claim holds for all n 2 in order to show that the claim holds for n=k (as otherwise I’m not sure how you would be able to properly assert that the claim holds for a_(k-1) when attempting to prove that the claim holds for a_(k+1) as done in the solution above). Please correct me if I am misunderstanding something. Thanks

I agree with Rameel. I think the point of the question is that you need to adapt the induction technique to deal with a relation involving k-1, k and k+1.