Exponential lower bound for Fibonacci numbers Can someone show me how to solve through induction, $F(N) \geq (3/2)^N$ for all $N\geq N_0$, where $F(n)$ is the Fibonacci function and $N_0$ is some positive integer. I know that $N_0$ should be $11$, but I can't find the constant or show the proof correctly. Any help would be appreciated! 
 A: So. I'm going to assume that $F(0) = 0, F(1) = 1$, but you may need to recast this based on whatever convention you'd like to use.
Proceeding by strong induction, I'm going to use the base case $$F(11) = 89 \geq \left(\frac{3}{2}\right)^{11}, F(12) = 144 \geq \left(\frac{3}{2}\right)^{12}.$$
Now for the inductive step. Suppose that $F(k) \geq \left(\frac{3}{2}\right)^{k}$ for all $11 \leq k \leq n$. Now $$ F(n+1) = F(n) + F(n-1) \geq \left(\frac{3}{2}\right)^{n} + \left(\frac{3}{2}\right)^{n-1} = \frac{5}{2} \left(\frac{3}{2}\right)^{n-1}.$$
Now $\frac{5}{2} > \frac{9}{4}$, so
$$F(n+1) \geq \frac{9}{4}\left(\frac{3}{2}\right)^{n-1} = \left(\frac{3}{2}\right)^{n+1}$$
which completes the proof. The main subject that may be unfamiliar is the difference between weak and strong induction. In weak induction, we prove that $P(n) \implies P(n+1)$ for all $n \geq n_0$; in strong induction, we prove that $P(i) \; \forall i \in \{n_0 \ldots n\} \implies P(n+1)$. Happily, these two methods of induction are logically equivalent, proof of which is a nice exercise.
