Prove that for all $n\geqslant 1$ we have $F_n<{\left(\frac 74\right)}^n$. [closed]

Solution 1:

Use strong induction

It's sufficient to show

$$(7/4)^m+(7/4)^{m+1}<(7/4)^{m+2}$$

$$\iff1+(7/4)<(7/4)^2$$

$$\iff4^2+7\cdot4<7^2$$

Solution 2:

The proof will be by strong induction on n. There are two steps you need to prove here since it is an induction argument. You will have two base cases since it is strong induction.

First show the base cases by showing this inequailty is true for n=1 and n=2.

Then for the inductive step, assume the inequality is true for $F_{n-1}$ and $F_{n-2}$ (known as the inductive hypothesis) then show it is true for $F_{n}$.
$F_{n}$

=$F_{n-1}$+$F_{n-2}$ (by definition of Fibonacci numbers.)

<$(7/4)^{n-1}$+$(7/4)^{n-2}$ (by the inductive hypotheses)

=$(7/4)^{n-2}((7/4)+1)$ (arithmetic, factor $(7/4)^{n-2}$ from both terms)

=$(7/4)^{n-2} ((28/16)+16/16)$ (arithmetic, why? I wanted to compare to $7/4^2$=49/16 so I wanted a denominator of 16)

=$(7/4)^{n-2}(42/16)$ <$(7/4)^{n}$. (since 42/16<49/16)

So by the principle of mathematical induction, this inequality is true.

Hope this makes sense now.