33
$\begingroup$

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$
3
  • 3
    $\begingroup$ Look at Binet's formula en.wikipedia.org/wiki/… $\endgroup$ Commented Nov 1, 2018 at 21:39
  • 2
    $\begingroup$ Yes, of course, it is extremely close to $C \varphi^n \; , \;$ where $\varphi = \frac{1 + \sqrt 5}{2}$ and $C$ is a constant $\endgroup$
    – Will Jagy
    Commented Nov 1, 2018 at 21:39
  • $\begingroup$ @J.G. yah, I lost my focus... $\endgroup$
    – Doug M
    Commented Nov 1, 2018 at 21:45

2 Answers 2

50
$\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$
5
  • 5
    $\begingroup$ +1 for a clear and succinct answer. I might write $F_n \approx \frac{1}{\sqrt{5}} \phi^n$ for precision. $\endgroup$ Commented Nov 1, 2018 at 21:41
  • $\begingroup$ @Travis Fair enough. :) $\endgroup$ Commented Nov 1, 2018 at 21:42
  • $\begingroup$ "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. $\endgroup$
    – ThePhi
    Commented May 14, 2022 at 8:00
  • $\begingroup$ @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}$. $\endgroup$ Commented May 14, 2022 at 17:08
  • $\begingroup$ I would understand exponential growth as $f(n)$ is both growing and $f(n) = Θ(e^n)$. $\endgroup$
    – TrayMan
    Commented Feb 9 at 18:36
6
$\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 https://math.stackexchange.com/a/1201069/62698

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .