Home » Blog » Prove an inequality for the nth Fibonacci number

Prove an inequality for the nth Fibonacci number

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 1. Rameel says:

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

2. Rameel says:

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

• Anonymous says:

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.