[Math] Proving that $fib(n) < (\frac53)^n$ for $n \ge 1$ by induction

Question

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the help I needed, no one could explain to me at a basic level why you were able to perform some of these steps. The proof is below

Base case, $N = 1$

So, $f_1 = 1$ by the definition of Fibonacci numbers.

Then $f_1 < (\frac53)$ is true.

Then assume for all $n \geq 1, f_n < (\frac53)^n$ is true.

Then $f_n + f_{n-1} < (\frac53)^n + (\frac53)^{n-1}$ by the definition
of Fibonacci numbers.

Then $f_{n+1} < (\frac53)^n + (\frac53)^{n-1}$

Then $f_{n+1} < (\frac53)^{n-1}(1 + \frac53)$ by factoring out $
> (\frac53)^{n-1}$ from the right side

Then $f_{n+1} < (\frac53)^{n-1}(\frac83)$

(now this is where I got lost and had to get help)

Then note that $(\frac83) < (\frac53)^2$ and therefore $f_n <
> (\frac53)^2$

Then by substitution $f_{n+1} < (\frac53)^{n-1}(\frac53)^2$

Then $f_{n+1} < (\frac53)^{n+1}$

QED.

Now I understand most of this proof. I just dont understand how you can, essentially out of the blue, just state that $\frac83 < (\frac53)^2$ and use this directly in the proof. I understand the statement is true, but how can you just substitute them for each other? If anyone can fill in the blanks for me I would really appreciate it. I feel like I should understand this but I don't.

Thank you!

Answer 1

We'd like to show that $f_{n+1}< (5/3)^{n+1}$. But all we can get from the induction assumption is $f_{n+1}<(5/3)^{n-1}(8/3)$.

So, what is wrong with the term we are dealing with? It is lacking a factor of $(5/3)^2$ (Since $(5/3)^{n+1}=(5/3)^{n-1}(5/3)^2$), but there is a factor of $8/3$ too much. So what would happen if we replaced the $8/3$ by the desired amount of $(5/3)^2$? Luckily, $8/3$ is less than $(5/3)^2$, thus it makes the result greater if we replace it. Thus, we get

$$f_{n+1}<(5/3)^{n-1}(8/3) < (5/3)^{n-1}(5/3)^2 = (5/3)^{n+1},$$ the desired inequality.

Note that, apart from needing to check the base case for $n=2$ as well, there is a crucial mistake in your induction: You should not assume that the assertion you want to show is true for all $n \geq 1$, as this is assuming that what you want to show is already true. What you should assume is that there is a number $n\leq 2$ such that $f_n <(5/3)^n$ and $f_{n-1} <(5/3)^{n-1}$. You are actually using only these in your proof, it's just the start of your induction step which is phrased wrongly.