If $F_n$ is the Fibonacci sequence, show that $F_n < \left(\frac 74\right)^n$ for $n\geq 1.$

Question

Recall that the Fibonacci sequence is defined by $F_0 = 0$, $F_1 = 1$, and $F_n = F_{n−1} + F_{n−2}$ for $n ≥ 2$. Prove that:

$$\forall \,\, n ≥ 1 ,\,\, F_n < \left(\frac 74\right)^n$$

In this question I understand how to do the basis step. In the induction step I know that you have to assume that n=k but I am having trouble figuring out on how to do that. Could someone please explain how to do this question.

Answer 1

The proposition that you're trying to prove is that $F_n<(\frac{7}{4})^n$

For $n = 0$, this is trivial; $0 < (\frac{7}{4})^0$

For $n = 1$, we have $1 < (\frac{7}{4})^1$

For your induction step, you assume that for all k < n, $F_k<(\frac{7}{4})^k$

So $F_{n-2}<(\frac{7}{4})^{n-2}$ and $F_{n-1}<(\frac{7}{4})^{n-1}$

$F_{n} = $

$F_{n-2}+ F_{n-1}$ <

$(\frac{7}{4})^{n-2} + (\frac{7}{4})^{n-1}$ =

$(\frac{7}{4})^{n-2} + \frac 7 4 (\frac{7}{4})^{n-2} = $

$\frac 4 4(\frac{7}{4})^{n-2} + \frac 7 4 (\frac{7}{4})^{n-2} $=

$\frac {11} 4 (\frac{7}{4})^{n-2}$=

$\frac {44} {16} (\frac{7}{4})^{n-2}$<

$\frac {49} {16} (\frac{7}{4})^{n-2}$=

$ (\frac{7}{4})^{n}$

Answer 2

There's something called Strong Induction.

The base cases are for $F_k$ such that $k=0,1$.

For the inductive step, assume that $\exists~ n$ such that $F_{n-1}<\frac{7^n}{4^n}$ and $F_{n-1}<\frac{7^{n-1}}{4^{n-1}}$

It's now quite easy to show that $$\begin{align*} F_{n+1}&=F_n+F_{n-1}\\ &<\frac{7^n}{4^n} + \frac{7^{n-1}}{4^{n-1}}\\ &<\frac{7^{n+1}}{4^{n-1}} \end{align*}$$ for all $n\geq 1$

Answer 3

Method 1: Base case: $$F_1=1<\frac74; F_2=1<\frac74.$$ Inductive hypothesis: $$F_{n-1}<\left(\frac74\right)^{n-1}; F_n<\left(\frac74\right)^n.$$ Inductive step: $$F_{n+1}=F_{n-1}+F_n<\left(\frac74\right)^{n-1}+\left(\frac74\right)^n=\left(\frac74\right)^n\left(\frac47+1\right)<\left(\frac74\right)^{n+1}.$$

Method 2: Prove $F_n=\frac{\phi^n-\psi^n}{\sqrt{5}}<\left(\frac74\right)^n$.

Base case: $F_1=1<\frac74$.

Inductive hypothesis: the above estimate.

Inductive step: $$F_{n+1}=\frac{\phi^n\cdot \frac{1+\sqrt{5}}{2}-\psi^n\cdot \frac{1-\sqrt{5}}{2}}{\sqrt{5}}=$$ $$\left(\frac12+\frac{\sqrt{5}}{2}\right)\cdot \frac{\phi^n-\psi^n}{\sqrt{5}}+2\left(\frac{1-\sqrt{5}}{2}\right)^n<$$ $$\left(\frac12+\frac{\sqrt{5}}{2}+2\right)\cdot \left(\frac74\right)^n<\left(\frac74\right)^{n+1}.$$