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.