Inductive step for the Fibonacci sequence

Question

Let $F_{n}$ be a Fibonacci sequence given by $$F_{n}=\begin{cases} 0 & \text{ if } n=0 \\ 1 & \text{ if } n=1 \\ F_{n-1}+F_{n-2} & \text{ if } n\geq 2. \end{cases}$$ I was asked to prove that $(3/2)^{n-1}\leq F_{n}$ holds for all $n\geq 6$. I fail to satisfy the Inductive Step. Assume that it holds for some $n=k$ and I wish to show that it is true for $n=k+1$. We have $$\left ( \frac{3}{2} \right )^{k}=\frac{3}{2}\left ( \frac{3}{2} \right )^{k-1}\leq \frac{3}{2}F_{k}\overset{?}<F_{k+1}.$$ Is there another correct way to show it?

Answer 1

Note: As remarked by @ThomasAndrews, it is absolutely essential that the induction start somewhere. In particular, in this case one must check that the desired inequality holds for $F_6$ and $F_7$. This is not difficult (by straight computation), but it has to be done. Worth remarking that the inequality is false below $6$, but happily true for $F_6=8>(\frac 32)^5\sim7.59$. (just to be thorough , $F_7$ passes easily as $F_7=13>(\frac 32)^6\sim 11.39$).

From the recursion (and the induction hypothesis) we have $$F_n=F_{n-1}+F_{n-2}≥\left(\frac 32\right)^{n-2}+\left(\frac 32\right)^{n-3}=\left(\frac 32\right)^{n-3}\left(\frac 32+1\right)$$

All that remains is for you to verify that $$\left(\frac 32+1\right)≥\left(\frac 32\right)^2$$