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?
$\endgroup$ 32 Answers
$\begingroup$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$.
$\endgroup$ 4 $\begingroup$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
$\endgroup$
