$f_{n+1}<(\frac{7}{4})^{n}, n\geq 1.$

76 Views Asked by At

Here is my proof of the statement: $f_{(n+1)}<(\frac{7}{4})^{n}, n\geq 1$.

Note: $f_{(n+1)}$ and etc. denote the Fibonacci numbers, and hence each term is the sum of the previous two terms, so: $f_{(n+1)} = f_{(n)}+f_{(n-1)}.$

Base case: LHS: $f_{2} = 1$, RHS: $(\frac{7}{4}),$ so $1<(\frac{7}{4}).$

Induction Hypothesis: Let us assume $f_{(k+1)}<(\frac{7}{4})^{k}$, for some $k>1.$

Induction step: By the principle of induction, this implies that: $f_{(k+2)}<(\frac{7}{4})^{(k+1)}.$

Proof:

We assumed that: $f_{(k+1)}<(\frac{7}{4})^{k}$, for some $k>1.$

This then implies that: \begin{align}(\frac{7}{4})f_{(k+1)}&<(\frac{7}{4})(\frac{7}{4})^{k}\\ &=(\frac{7}{4})^{(k+1)}. \end{align}

If we can show that, $(\frac{7}{4})f_{(k+1)}>f_{(k+2)}$, for $k>1$ then, we have shown that: $f_{(k+2)}<(\frac{7}{4})^{(k+1)}.$

\begin{align} (\frac{7}{4})f_{(k+1)}&>f_{(k+2)}\\ (\frac{7}{4})f_{(k+1)}&>f_{(k+1)}+f_{(k)}\\ (\frac{3}{4})f_{(k+1)}&>f_{(k)}.\\ \end{align}

Hence, since this inequality is true for $k>1,$ this implies that: $f_{(k+2)}<(\frac{7}{4})^{(k+1)}.$

Hence, by induction we have proven that: $f_{(n+1)}<(\frac{7}{4})^{n}, n\geq 1$.

Please let me know if there are any mistakes.