Is my proof of the Fibonacci sequence correct?

Question

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

Answer 1

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.

Answer 2

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.