# Fibonacci proof by induction

I have fibonacci numbers defined as such:

$$f(n) = f(n-1) + f(n-2)$$with$$f(0) = 0$$$$f(1) = 1$$

I have to prove that $$F(n) \geq 1.5^{n-1}, n \geq 6$$

Base Case:

$$f(6) = 8 \geq (1.5)^5 = 7.6$$ Base holds

Inductive hypothesis $$k \geq 6$$$$f(k) \geq (1.5)^{k-1}$$

Inductive Step

Here is how I have started, any hints or pointers on how to continue are appreciated

$$f(k-1) \geq (1.5)^{k+1-1}$$ $$f(k) + f(k-1) = (1.5)^{k-1} + (1.5)^{k-2}$$ now I think where I want to go from here is to expand the right side of this equation out, but I am unsure how to do this.

-
The base case should include $f(7)=13$, then you can apply the recursion. Just remember $2.5\gt2.25$. – robjohn Mar 30 '14 at 23:52
Hint: $1.5 + 1 \ge 1.5^2$. – Carsten S Mar 30 '14 at 23:54

It's actually easier to use two base cases (corresponding to $n = 6,7$), and then use the previous two results to induct: Notice that if both $$f(k - 1) \ge (1.5)^{ k - 2}$$ and $$f(k) \ge (1.5)^{k - 1}$$
\begin{align*} f(k+1) &= f(k) + f(k - 1) \\ &\ge (1.5)^{k - 1} + (1.5)^{k - 2} \\ &= (1.5)^{k - 2}\Big(1.5 + 1\Big) \\ &> (1.5)^{k - 2} \cdot (1.5)^2 \end{align*} since $1.5^2 = 2.25 < 2.5$.