How to establish this inequality without using induction?

Question

Given the Fibonacci sequence $a_1 = 1$, $a_2 = 2$, $\ldots$, $a_{n+1} = a_n + a_{n-1} $ for $n \geq 2$, how to derive, without using induction, the inequality $$ a_n < (\frac{1+\sqrt{5}}{2})^n $$ for $n = 1, 2, 3, \ldots$?

I know how to establish the above inequality using induction.

Answer 1

The fibbonacci numbers have a closed form: $a_n = \dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}\right]$.

Since $\left|\dfrac{1-\sqrt{5}}{2}\right| < 1$, we have $-1 < \left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1} < 1$ for all $n \ge 1$.

Can you figure out what to do from here?

Answer 2

We may as well let the (Fibonacci) sequence $(a_n)_{n\geq0}$ begin with $a_0=1$. Put ${1+\sqrt{5}\over2}=:\phi$ and consider the auxiliary sequence $$b_n:=1-{a_n\over\phi^n}\qquad(n\geq0)\ .$$ We have to show that $b_n>0$ for all $n\geq1$.

Proof. One has $b_0=0$; then $\phi>1=a_1$ implies $b_1>0$. Finally it is easily verified that the $b_n$ satisfy the recursion $$b_n={b_{n-1}\over\phi}+{b_{n-2}\over\phi^2}\qquad(n\geq2)\ ,$$ so that the claim follows by inspection.