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

Prove an inequality for the nth Fibonacci number

by RoRi

We use the following recursive definition of the Fibonacci numbers,

    \[ a_1 = 1, \qquad a_2 = 2, \qquad a_{n+1} = a_n + a_{n-1} \quad \text{if } n \geq 2. \]

Prove that for all n \geq 1 we have,

    \[ a_n < \left( \frac{1+\sqrt{5}}{2} \right)^n. \]

Proof. For the case n = 1, we have a_1 =1 and

    \[ \left( \frac{1+\sqrt{5}}{2} \right)^1 = \frac{1+\sqrt{5}}{2} > 1 \qquad (\text{since } \sqrt{5} > 2). \]

So, the inequality is true for n=1. Assume then that the inequality is true for some n = k \in \mathbb{Z}_{\geq 1}. Then,

    \begin{align*} a_k + a_{k-1} &< \left( \frac{1+\sqrt{5}}{2} \right)^k + \left( \frac{1+\sqrt{5}}{2} \right)^{k-1} \\ \implies \qquad \qquad a_{k+1} &< \left( \frac{1+\sqrt{5}}{2} \right)^{k-1} \cdot \left( \frac{1+\sqrt{5}}{2} + 1 \right) \\ &= \left( \frac{1 + \sqrt{5}}{2} \right)^{k-1} \cdot \left( \frac{3+\sqrt{5}}{2} \right). \end{align*}

But, as one can compute, \left( \frac{3+\sqrt{5}}{2} \right) = \left( \frac{1+\sqrt{5}}{2} \right)^2. Hence,

    \[ a_{k+1} < \left( \frac{1+\sqrt{5}}{2} \right)^{k+1}. \]

Thus, the inequality holds for all n \in \mathbb{Z}_{\geq 1}. \qquad \blacksquare

3 comments

  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.

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):