How to establish this inequality without using induction? 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. 

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.
