I need help with the last inductive steps, can someone help? I hope my formatting is good enough, first time here.
The case:
"Let the fibonacci sequence be recursivly defined so that
$$F_0 = 0, F_1 = 1$$
Else if n >= 2
$$F_n = F_{n-1}+F_{n-2} $$
Prove that
$$F_n \geq (3/2)^{n-1}$$
For all numbers in the set $\{6,7,8,9…\}$"
Basecase:
$$F_{2} = F_{1} + F_{0} = 1 + 0 $$
$$F_{3} = F_{2} + F_{1} = 1 + 1 $$
$$F_{4} = F_{3} + F_{2} = 2 + 1 $$
$$F_{5} = F_{4} + F_{3} = 3 + 2 $$
$$F_{6} = F_{5} + F_{4} = 5 + 3 $$
$$F_{6} \geq (3/2)^{5} = 8 \geq 7.59 $$
Induction step:
We assume the above is true for $n=k$, so now we prove it is true for $n=k+1$
We remember
$$F_n \geq (3/2)^{n-1}$$
$$F_{k+1} \geq (3/2)^{k}$$
We know that
$$ F_{k} = F_{k-1}+F_{k-2} $$
$$ F_{k+1} = F_{k}+F_{k-1} $$
$$ F_{k}+F_{k-1} \geq (3/2)^{k} $$
I'm not quite sure where to go from here, can anyone help? I've looked at another thread about the same question, but I don't understand the last part of his equation nor the answers.
In my case we are told that "you may need to use $(3/2)+1 > (3/2)^{2}$", but I don't know how to apply it to my case.
Best Answer
If $F_k\geqslant\left(\frac32\right)^{k-1}$ and $F_{k+1}\geqslant\left(\frac32\right)^k$, then\begin{align}F_{k+2}&=F_k+F_{k+1}\\&\geqslant\left(\frac32\right)^{k-1}+\left(\frac32\right)^k\\&=\left(\frac32\right)^{k-1}\left(1+\frac32\right)\\&>\left(\frac32\right)^{k-1}\left(\frac32\right)^2\\&=\left(\frac32\right)^{k+1}.\end{align}