# Is the Fibonacci sequence exponential?

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?

• Look at Binet's formula en.wikipedia.org/wiki/… Nov 1, 2018 at 21:39
• Yes, of course, it is extremely close to $C \varphi^n \; , \;$ where $\varphi = \frac{1 + \sqrt 5}{2}$ and $C$ is a constant Nov 1, 2018 at 21:39
• @J.G. yah, I lost my focus... Nov 1, 2018 at 21:45

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$$.

• +1 for a clear and succinct answer. I might write $F_n \approx \frac{1}{\sqrt{5}} \phi^n$ for precision. Nov 1, 2018 at 21:41
• @Travis Fair enough. :) Nov 1, 2018 at 21:42
• "does not take the form of an exponential b^n, but it does exhibit exponential growth" Is it possible? I thought the two statements ("it takes the form of an exponential b^n" and "it exhibits exponential growth") were synonyms. May 14 at 8:00
• @ThePhi By "exponential growth", I mean that the sequence is asymptotically $\sim \beta\cdot\alpha^n$ for some $\alpha,\beta>0$, but it is not precisely equal to $\beta\cdot\alpha^n$ for any $\alpha,\beta>0$. In this case, $\alpha=\phi$ and $\beta=1/\sqrt{5}$. May 14 at 17:08

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