How to prove a Fibonacci inequality using Strong Induction?

Question

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.

Answer 1

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.

Answer 2

Base case $n = 2, F_2 = 1 = x^0 = x^{2-2}$. Thus the inequality is true for $n = 2$. Assume it is true for $2 \leq n \leq k-1$, you show it is true for $n = k$: $F_k = F_{k-1}+F_{k-2} \geq x^{k-3}+ x^{k-4}= x^{k-4}(1+x)=x^{k-4}x^2 = x^{k-2}$. Thus it is true for all $n$.

Answer 3

\begin{align} F_n & = F_{n-1}+F_{n-2} \\[8pt] & \ge \left(\frac{1+\sqrt{5}}{2}\right)^{n-3} + \left( \frac{1+\sqrt{5}}{2} \right)^{n-4} & & \text{(by the induction hypothesis)} \\[8pt] & = \left(\frac{1+\sqrt{5}}{2}\right)^{n-4} \left( \frac{1+\sqrt{5}}{2} + 1 \right) & & \text{(Here we just pulled out a common factor.)} \\[8pt] & = \left(\frac{1+\sqrt{5}}{2}\right)^{n-4} \left( \frac{1+\sqrt{5}}{2} \right)^2 & & \text{Where did this come from? See below.} \\[8pt] & = \left(\frac{1+\sqrt{5}}{2}\right)^{n-2} \end{align}

We used the equality $\dfrac{1+\sqrt{5}}{2} + 1 = \left( \dfrac{1+\sqrt{5}}{2} \right)^2$.

To see this, just simplify both sides completely. In both cases, it comes to $\dfrac{3+\sqrt 5} 2$.