Proof of the inequality $F_i<(5/3)^i$ for the Fibonacci numbers

Question

The example states:

As an example, we prove that the Fibonacci numbers, F₀ = 1, F₁ = 1, F₂ = 2, F₃ = 3, F₄ = 5,..., F_i = F_{i - 1} + F_{i - 2}, satisfy F_i < (5/3)ⁱ, for all i >= 1. To do this, we first verify that the theorem is true for the trivial cases. It is easy to verify that F₁ = 1 < 5/3 and F₂ = 2 < 25/9; this proves the basis. We assume that the theorem is true for i = 1, 2,..., k; this is the inductive hypothesis. To prove the theorem, we need to show that F_{k + 1} < (5/3)^{k + 1}. We have F_{k + 1} = F_k + F_{k - 1}

And I got all of that until they started on the the rest of the proof which goes like this:

F_{k + 1} < (5/3)^k + (5/3)^{k - 1}

Got that...

F_{k + 1} < (3/5)(5/3)^{k + 1} + (3/5)²(5/3)^{k + 1}

Now I'm lost, but the the rest of the math makes sense up until the next to last step.

F_{k + 1} < (3/5)(5/3)^{k + 1} + (9/25)(5/3)^{k + 1}
which simplifies to
F_{k + 1} < (3/5 + 9/25)(5/3)^{k + 1}
F_{k + 1} < (24/25)(5/3)^{k + 1}
F_{k + 1} < (5/3)^{k + 1}

The two things I don't understand are how they got to the second step of the proof and how they eliminated the 24/25. I feel really dumb right now. Could some one show me what I'm missing?

Answer 1

First you can assume that $F_k < (5/3)^k$ and $F_{k-1} < (5/3)^{k-1}$ so.

$$F_{k+1} = \underbrace{F_{k}}_{<(5/3)^k}+\underbrace{F_{k-1}}_{< (5/3)^{k-1}} <(5/3)^k+ (5/3)^{k-1}$$

We can use $24/25 <1$ like so: $$F_{k+1} < \underbrace{24/25}_{<1} \cdot (5/3)^{k+1} < 1 \cdot (5/3)^{k+1}$$

Answer 2

To add to flawr's answer; regarding the "2nd part" - they're using the fact that $ 1 = \frac{5}{3} \times \frac{3}{5}$.

So $(\frac{5}{3})^k = \frac{3}{5} \times \frac{5}{3} \times (\frac{5}{3})^k = \frac{3}{5} \times (\frac{5}{3})^{k+1}$