27
$\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
  • 2
    $\begingroup$ Look at Binet's formula en.wikipedia.org/wiki/… $\endgroup$ Nov 1, 2018 at 21:39
  • 1
    $\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
    Nov 1, 2018 at 21:39
  • $\begingroup$ @J.G. yah, I lost my focus... $\endgroup$
    – Doug M
    Nov 1, 2018 at 21:45

2 Answers 2

41
$\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
  • 4
    $\begingroup$ +1 for a clear and succinct answer. I might write $F_n \approx \frac{1}{\sqrt{5}} \phi^n$ for precision. $\endgroup$ Nov 1, 2018 at 21:41
  • $\begingroup$ @Travis Fair enough. :) $\endgroup$ 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
    May 14 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$ May 14 at 17:08
3
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.