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.
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}$$
then we have
\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$.