Is the Fibonacci sequence exponential?

Question

I could not find any information on this online so I thought I'd make a question about this.

If we take the Fibonacci sequence $F_n = F_{n-1} + F_{n-2}$, is this growing exponentially? Or perhaps if we consider it as a function $F(x) = F(x-1) + F(x-2)$, is $F(x)$ an exponential function?

I know Fibonacci grows rather quick, but is there a proof that shows whether it is exponential or not?

Answer 1

The Fibonacci Sequence does not take the form of an exponential $b^n$, but it does exhibit exponential growth. Binet's formula for the $n$th Fibonacci number is $$F_n=\frac{1}{\sqrt{5}}\bigg(\frac{1+\sqrt 5}{2}\bigg)^n-\frac{1}{\sqrt{5}}\bigg(\frac{1-\sqrt 5}{2}\bigg)^n$$ Which shows that, for large values of $n$, the Fibonacci numbers behave approximately like the exponential $F_n\approx \frac{1}{\sqrt{5}}\phi^n$.

Answer 2

Assuming

• $F_n = F_{n-1} + F_{n-2}$
• $F_n > F_{n-1}$
• $F_{n-1} > F_{n-2}$

$=>$

Start with $F_n = F_{n-1} + F_{n-2}$, and make the right side bigger by replacing $F_{n-2}$ with $F_{n-1}$

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

$=>$

$F_n < 2F_{n-1}$

$=>$

$F_n < 2^n$

So the fibonacci sequence, one item at a time, grows more slowly than $2^n$.

But on the other hand every 2 items the Fibonacci sequence more than doubles itself:

$(1) F_n = F_{n-1} + F_{n-2}$

$(2) F_{n-1} = F_{n-2} + F_{n-3}$

$=>$

Replace $F_{n-1}$ in $(1)$ with $F_{n-1}$ from $(2)$

$F_n = 2F_{n-2} + F_{n-3}$

$=>$

Because $F_{n-3}$ is greater than zero, we can drop it from the right side, and that makes the right side smaller than the left.

$F_n > 2F_{n-2}$

$=>$

$F_n > 2^{n/2}$

$F_n > (2^{1/2})^n$

$F_n > \sqrt{2}^n$

Because the Fibonacci sequence is bounded between two exponential functions, it's effectively an exponential function with the base somewhere between 1.41 and 2.

${1.41}^n$ < $F_n < 2^n$

That base ends up being the golden ratio. See https://math.stackexchange.com/a/1201069/62698