Using strong induction I am trying to prove that
$$F_n \geq \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \text{ for all } n \geq 2$$
for the Fibonacci Sequence defined by: $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n-1} + F_{n-2}$ for $n \geq 2$.
I know how to do strong induction for normal sequences, but not for inequalities (I have never liked inequalities).
If someone wouldn't mind pointing me in the right direction regarding what to do, I would be very grateful.
Best Answer
You want to use the recurrence $F_{n+1} = F_{n} + F_{n-1}$ and apply the inductive hypothesis to both $F_{n}$ and $F_{n-1}$. What you'll get is that you need to verify:
$$x^{(n+1)-2} \geq x^{n-2} + x^{(n-1)-2}$$
Write out what the terms should be and see if you can show the inequality holds.