<s>[INST] Is my proof of the Fibonacci sequence correct? Been working on this for some time now but have no idea if it's correct! Any hints are appreciated.
Recall the Fibonacci sequence: $f_1 = 1$, $f_2 = 1$, and for $n \geq 1$, $f_{n+2} = f_{n+1} + f_n$. Prove
that $f_n > (\frac{5}{4})^n\  \forall \ n \geq 3$.
My answer:
"base case"
$[f_3 = 2 > (\frac{5}{4})^3\ = \frac{125}{64}\ correct$
$[f_4 = 3 > (\frac{5}{4})^4\ = \frac{625}{256}\ correct$
$assume\ f_k > (\frac{5}{4})^k\ for\ some\ k \geq 3$
$[and\ f_{k-1} > (\frac{5}{4})^{k-1}$
$then \ f_{k+1} = f_k + f_{k+1} > (\frac{5}{4})^k + (\frac{5}{4})^{k-1}$
$so \ f_{k+1} > (\frac{5}{4})^k + (\frac{5}{4})^{k-1}\ > (\frac{5}{4})^k (\frac{5}{4})^k = (\frac{5}{4})((\frac{5}{4})^k) = (\frac{5}{4})^{k+1}$
$f_{k+1} > (\frac{5}{4})^{k+1}$
$so \ f_n > (\frac{5}{4})^n \ \forall \ n \geq 3$
QED
 [/INST] As J.W. Tanner mentioned, it's not true that $$\left(\frac{5}{4} \right)^k+ \left(\frac{5}{4} \right)^{k-1} > \left(\frac{5}{4} \right)^k\left(\frac{5}{4} \right)^k$$
(consider for example $k=3$ then $\frac{125}{64} + \frac{25}{16} < \frac{125} {64}  \times\frac{125}{64}$
Hint: You can consider $$\left(\frac{5}{4} \right)^k+ \left(\frac{5}{4} \right)^{k-1} = \left(\frac{5}{4} \right)^{k-1} \left(\frac{5}{4} + 1\right) = \left(\frac{5}{4} \right)^{k-1} \left(\frac{9}{4} \right) > \left(\frac{5}{4} \right)^{k-1} \left(\frac{5}{4} \right)^{2}$$
and proceed from there.
</s>