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
 A: 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.
A: You can use strong induction.
Start with $f_k = f_1 + f_2 + ... + f_{k-1} = 2 + ... + f_{k-1}$
Assume the proposition holds true for every $f_m$ where $m \leq k-1$.
Then we can bound $f_k$ using the geometric series sum as:
$\displaystyle f_k > 2 + \frac{(\frac 54)^3((\frac 54)^{k-3}-1)}{\frac 54 -1}$
and the expression on the right can be simplified into the form $A + B(\frac 54)^k$ (you're left to find constants $A$ and $B$).
Using the same method (and assuming the strong inductive hypothesis), you can quickly find the expression for $f_{k-1}$. It'll just be $A + \frac 45B(\frac 54)^k$.
Add those up (you're finding a lower bound on $f_{k+1}$) and show that this is greater than $(\frac 54)^{k+1} = \frac 54(\frac 54)^k$.
You will likely find it easier (I did) to put $(\frac 54)^k = x$, solve for the range of $x$ that satisfies the inequality and deduce that it the lower bound of such $x$ is lower than $\frac 54$, which naturally means it's lower than any value of $(\frac 54)^k$ for $k \geq 3$.
You've then established that $f_{k-1} + f_k = f_{k+1} > (\frac 54)^{k+1}$ and proven the proposition by strong induction. The base cases, you can handle.
