Question

The Fibonacci numbers ${\mathbf{F}}_{\mathbf{0}}\mathbf{,}{\mathbf{F}}_{\mathbf{1}}\mathbf{,}{\mathbf{F}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{..}$ are defined by the rule

${\mathbf{F}}_{\mathbf{0}}\mathbf{=}\mathbf{0}\mathbf{,}{\mathbf{F}}_{\mathbf{1}}\mathbf{=}\mathbf{1}\mathbf{,}{\mathbf{F}}_{\mathbf{n}}\mathbf{=}{\mathbf{F}}_{\mathbf{n}\mathbf{-}\mathbf{1}}\mathbf{+}{\mathbf{F}}_{\mathbf{n}\mathbf{-}\mathbf{2}}$.

In this problem we will confirm that this sequence grows exponentially fast and obtain some bounds on its growth.

(a) Use induction to prove that ${\mathbf{F}}_{\mathbf{n}}\mathbf{\ge }{\mathbf{2}}^{\mathbf{0}\mathbf{.5}\mathbf{n}}$for $\mathbf{n}\mathbf{\ge }\mathbf{6}$.

(b) Find a constant $\mathbf{c}\mathbf{<}\mathbf{1}$such that${\mathbf{F}}_{\mathbf{n}}\mathbf{\ge }{\mathbf{2}}^{\mathbf{cn}}$ for all $\mathbf{n}\mathbf{\ge }\mathbf{0}$. Show that your answer is correct.

(c) What is the largest$\mathbf{c}$ you can find for which ${\mathbf{F}}_{\mathbf{n}}\mathbf{=}\mathbf{\Omega }\mathbf{\left(}{\mathbf{2}}^{\mathbf{cn}}\mathbf{\right)}$?

Short answer

1. It is proved that ${\mathrm{F}}_{\mathrm{n}}\ge 2^{0.5\mathrm{n}}$ for $\mathrm{n}\ge 6$.
2. The value of the constant is $1>\mathrm{c}\ge 0.69$.
3. The largest value is $\mathrm{c}~0.69$.

Step-by-step solution

Rules for Fibonacci

We are given that:

$\begin{array}{l}{\mathrm{F}}_0=0\\ {\mathrm{F}}_1=1\\ {\mathrm{F}}_{\mathrm{n}}={\mathrm{F}}_{\mathrm{n}-1}+{\mathrm{F}}_{\mathrm{n}-2}\end{array}$

Step 2:Solution to part (a) 

We know that for $\mathrm{n}=6$,the Fibonacci number${\mathrm{F}}_6=8$.

Also, for $\mathrm{n}=6$, use induction to prove that ${\mathrm{F}}_{\mathrm{n}}\ge 2^{0.5\mathrm{n}}$ for $\mathrm{n}=6$.

Find ${\mathrm{F}}_{\mathrm{n}}\ge 2^{0.5\mathrm{n}}$for $\mathrm{n}=6$.

$\begin{array}{l}\mathrm{F}\left(6\right)\stackrel{?}{\ge }{2}^{0.5\cdot 6}\\ 8\stackrel{?}{\ge }{2}^3\\ 8\ge 8\end{array}$

This is true. Or it can be said that $\mathrm{F}\left(6\right)\ge 2^{0.5\cdot 6}$ is true.

So, let us assume this statement${\mathrm{F}}_{\mathrm{n}}\ge 2^{0.5\mathrm{n}}$ is true for all values of k, i.e., ${\mathrm{F}}_{\mathrm{k}}\ge 2^{0.5\mathrm{k}}$.

Now, we will check for$\mathrm{k}=\mathrm{k}+1$.

So, we have the Fibonacci series as:

$\begin{array}{c}{\mathrm{F}}_{\mathrm{k}+1}={\mathrm{F}}_{(\mathrm{k}+1)-1}+{\mathrm{F}}_{(\mathrm{k}+1)-2}\\ ={\mathrm{F}}_{\mathrm{k}}+{\mathrm{F}}_{\mathrm{k}-1}\\ \ge 2^{0.5\mathrm{k}}+2^{0.5(\mathrm{k}-1)}\\ \ge 2^{0.5\mathrm{k}}+2^{0.5\mathrm{k}}\cdot 2^{-0.5}\\ \ge 2^{0.5\mathrm{k}}(1+2^{-0.5})\end{array}$

We know that$1+2^{-0.5}\ge 2^{0.5}$.

Hence,${\mathrm{F}}_{\mathrm{k}+1}\ge 2^{0.5(\mathrm{k}+1)}$for all $\mathrm{k}$.

So,${\mathrm{F}}_{\mathrm{n}}\ge 2^{0.5\mathrm{n}}$for $\mathrm{n}\ge 6$ is true.

Hence it is proved.

Step 3:Solution (b)

We are given that ${\mathrm{F}}_{\mathrm{n}}\le 2^{\mathrm{cn}}$ for $\mathrm{n}\ge 0$.

Also from the Fibonacci series:${\mathrm{F}}_{\mathrm{n}}\ge {\mathrm{F}}_{\mathrm{n}-1}+{\mathrm{F}}_{\mathrm{n}-2}$.

Thus,

$\begin{array}{c}{2}^{\mathrm{cn}}\ge 2^{\mathrm{c}(\mathrm{n}-1)}+2^{\mathrm{c}(\mathrm{n}-2)}\\ 2^{\mathrm{c}}\ge 2^{-\mathrm{c}}+2^{-2\mathrm{c}}\\ 2^{2\mathrm{c}}\ge 2^{\mathrm{c}}+1\end{array}$

Let$2^{\mathrm{c}}=\mathrm{x}$.

Then,

$\begin{array}{c}{\mathrm{x}}^2\ge \mathrm{x}+1\\ {\mathrm{x}}^2-\mathrm{x}-1\ge 0\end{array}$

On solving the above quadratic equation:

$\begin{array}{c}\mathrm{x}\ge \frac{1\pm \sqrt{5}}{2}\\ \Rightarrow 2^{\mathrm{c}}\ge \frac{1\pm \sqrt{5}}{2}\end{array}$

Take log on both sides; we have:

$\begin{array}{c}{\log }_2\left(2^{\mathrm{c}}\right)\ge {\log }_2\left(\frac{1\pm \sqrt{5}}{2}\right)\\ \Rightarrow \mathrm{c}\ge 0.69\end{array}$

So, the value must be $1>\mathrm{c}\ge 0.69$.

Step 4:Solution (c)

In the previous solution, the largest possible value of $\mathrm{c}$ would be $0.69$.

Since ${\mathrm{F}}_{\mathrm{n}}=\mathrm{\Omega }\left(2^{\mathrm{cn}}\right)$, this means it is the lowest bound.

Therefore,$\mathrm{c}=0.69$ .