Finding growth bounds on Fibonacci Sequence

Question

I've been working on this following problem:

Find a constant $c< 1$ such that $F_n \leq 2^{cn}$ for all $n \geq 0$.

I honestly have no idea where to begin on this. I've done plenty of proofs the one function is Big-O another, but I'm not sure where to start looking for c in this case. Guidance appreciated. Thanks!

Answer 1

Binet's formula seems like overkill, given the (relatively weak) desired conclusion.

A more naive strategy is to pretend that $F_{n} = 2^{cn}$ and see what the recursion relation $F_{n+2} = F_{n} + F_{n+1}$ suggests. Here, $$ 2^{c(n+2)} = 2^{cn} + 2^{c(n+1)}, \quad\text{or}\quad 2^{2c} = 1 + 2^{c}. $$ The latter is a quadratic in $2^{c}$, and by the quadratic formula has roots $$ 2^{c} = \frac{1 \pm \sqrt{5}}{2}. $$ It's therefore natural to attempt to show $F_{n} \leq \bigl[(1 + \sqrt{5})/2\bigr]^{n}$ for $n \geq 0$; this is a straightforward induction.

Answer 2

Hint: $$\text{If }\phi = \frac{1 + \sqrt5}{2}, \ F(n) = \frac{\phi^n - (1-\phi)^n}{\sqrt 5}\text{ where } F(n)\text{ is the nth Fibonacci number}$$

Answer 3

By Binet's formula you may prove that: $$0<F_n =\frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}2\right)^n-\frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}2\right)^n<\left(\frac{1+\sqrt{5}}2\right)^n$$ then choose $c$ such that $$ 2^c=\frac{1+\sqrt{5}}2, $$ giving $$ c=\frac{\ln \left(\frac{1+\sqrt{5}}2\right)}{\ln 2}=0.6942...<1. $$

Answer 4

Let $0\lt x=2^c\le 2$.

If $F_{n-2}\le x^{n-2}$ and $F_{n-1}\le x^{n-1}$ you have $F_n=F_{n-1}+F_{n-2}\le x^{n-1}+x^{n-2}$

So you will definitely succeed if you get the initial conditions (first values) to work and if $x^{n-1}+x^{n-2}\le x^n$ which gives you $x^2-x-1\ge 0$ (dividing through by $x^{n-2}\gt 0$). For example, $x=\frac 53$ works for the inequality.

There has been some debate elsewhere about the initial values of $F_n$ - whether $F_0=0$ or $F_0=1$ - $F_0=0$ is the best choice, because then $F_n\mid F_{kn}$ for all positive integers $n$ and $k$. Then $x=\frac 53$ works for the initial values too.

Then you need to take logs to get the appropriate value of $c$. Note that $\varphi = \frac {1+\sqrt 5}2$ is the least value of $x$ which would satisfy the inequality.