1
$\begingroup$

I'm trying to picture this closed form from Wikipedia visually:

enter image description here

The idea is, if you take $\phi^n / \sqrt{5}$ and round it to the nearest integer, you'll get the $n$th Fibonacci number. I see how it works out on paper, but is there an intuitive way to understand this? Specifically I'm trying to wrap my brain around how $\phi^n$ would lead to the correct answer... if I want the 8th Fibonacci number, for example, how does it help to multiply $\phi$ by itself 8 times?

$\endgroup$
  • 1
    $\begingroup$ Do you know the fact that $$\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi\;?$$ $\endgroup$ – Brian M. Scott May 29 '13 at 6:05
  • 1
    $\begingroup$ Yes. Okay, so that clears up my first question. The next question: why divide by sqrt(5)? $\endgroup$ – Goose Bumper May 29 '13 at 6:10
  • $\begingroup$ Have you tried solving this using a recurrence relation $F_n=F_{n-1}+F_{n-2}$, and then finding the closed form by plugging in $F_n=\lambda^n$, and then solving for $\lambda$? $\endgroup$ – Noy Soffer May 29 '13 at 6:12
3
$\begingroup$

The fact that $F_n$ is the integer nearest to $\dfrac{\varphi^n}{\sqrt5}$ follows from the closed form for the Fibonacci numbers known as the Binet formula:

$$F_n=\frac{\varphi^n-\widehat\varphi^n}{\sqrt5}=\frac{\varphi^n}{\sqrt5}-\frac{\widehat\varphi^n}{\sqrt5}\;,$$

where $\widehat\varphi=\dfrac{1-\sqrt5}2$. Note that $\widehat\varphi\approx-0.618$, so $|\widehat\varphi|<1$, and $|\widehat\varphi^n|$ decreases rapidly as $n$ increases. It turns out that even for small $n$ the correction $\dfrac{\widehat\varphi^n}{\sqrt5}$ is small enough so that $F_n$ is the integer nearest to $\dfrac{\varphi^n}{\sqrt5}$.

The $\sqrt5$ in the Binet formula ultimately comes from the initial conditions $F_0=0$ and $F_1=1$; a sequence with the same recurrence $x_n=x_{n-1}+x_{n-2}$ but different initial values would still grow approximately proportionally to $\varphi^n$ (or in exceptional cases $\widehat\varphi^n$), but the coefficient of approximate proportionality would be different.

Added: Specifically, each such sequence has a closed form $x_n=\alpha\varphi^n+\beta\widehat\varphi^n$, where $\alpha$ and $\beta$ are chosen to give the correct values when $n=0$ and $n=1$. Suppose that $x_0=a$ and $x_1=b$. Then from $n=0$ we must have $\alpha+\beta=a$, and from $n=1$ we must have $\alpha\varphi+\beta\widehat\varphi=b$. This pair of linear equations can then be solved for $\alpha$ and $\beta$, and provided that $\alpha\ne0$, we’ll have $x_n\approx\alpha\varphi^n$ for sufficiently large $n$. (Just how large sufficiently large actually is will depend on $\alpha$ and $\beta$.)

$\endgroup$
  • $\begingroup$ For the last paragraph: Of course there is the exceptional case that the sequence rather grows like $\hat\varphi^n$ instead ... $\endgroup$ – Hagen von Eitzen May 29 '13 at 6:20
  • $\begingroup$ Cool! Sounds like I'll understand this better by figuring out how to find closed form solutions for recurrences. "The sqrt(5) in the Binet formula ultimately comes from the initial conditions F0=0 and F1=1" could you elaborate more on this? $\endgroup$ – Goose Bumper May 29 '13 at 6:22
  • $\begingroup$ @Hagen: Yep; caught it in the addition, but had to go back to fix it in the original paragraph. $\endgroup$ – Brian M. Scott May 29 '13 at 6:25
  • $\begingroup$ @GooseBumper: Does the added bit give you a better idea? $\endgroup$ – Brian M. Scott May 29 '13 at 6:25
  • $\begingroup$ @BrianM.Scott I think so. Let me work it out and see, thanks! $\endgroup$ – Goose Bumper May 29 '13 at 6:31
2
$\begingroup$

The defining relation is $F_n=F_{n-1}+F_{n-2}$ with $F_1=F_2=1$, and this clearly defines the whole sequence.


To see why powers arise, look first at a much simpler problem, with $$A_n=cA_{n-1}$$ and $A_0=1$, so that $$A_1=c, A_2=c^2 \dots A_n=c^n \dots$$ - this is easy to prove by induction. And if $A_0$ were instead to be $d$, say, then we'd have $A_n=dc^n$. So in this simple recurrence the power of $c$ arises simply and naturally.


Now let's tackle $$B_n=cB_{n-1}+tb^n$$ with $b\neq c$. This is a linear recurrence, and if we have a particular solution $B_n$ then it is easy to see that $B_n+kA_n$ is another solution to the recurrence. An initial value will determine the unknown constant $k$.

To find a solution, we try $B_n=rb^n$, whence $$rb^n=cb^{n-1}+tb^n$$ which gives $$rb=c+tb$$ so that $r=t+\frac cb$ and the solution $B_n=kc^n+rb^n$ involves two different powers.


We now have the tools to tackle a recurrence of the form $$C_n=(\alpha+\beta)C_{n-1}-\alpha\beta C_{n-2} $$ or $$ C_n-\alpha C_{n-1}=\beta (C_{n-1}-\alpha C_{n-2})$$

We set $D_n=C_n-\alpha C_{n-1}$ which gives us $$D_n=\beta D_{n-1}$$ We know that this has solution $$D_n=t\beta^n$$ and this can be written in terms of $C_n$ as $$C_n-\alpha C_{n-1}=t\beta^n$$ which is the form we had before for $B_n$ and which is solved by $C_n=k\alpha^n+r\beta^n$ where $k$ and $r$ are fully determined by two initial values.


Now we note that $\alpha$ and $\beta$ are the roots of the quadratic equation $x^2-(\alpha+\beta)x+\alpha\beta=0$

So to put $F_n=F_{n-1}+F_{n-2}$ into the form we can solve we need $\alpha+\beta=1$ and $\alpha\beta=-1$.

So we need to find the roots of $x^2-x-1$, which are $\phi, -\frac 1{\phi}$ and we expect $F_n$ to be the sum of powers of these roots ($k\phi^n+r(-\phi)^{-n}$, where $k$ and $r$ can be determined from the initial values).


Finally we note that $\phi \gt 1, \phi^{-1} \lt 1$ so that the term in $\phi^{-n}$ gets much smaller as $n$ increases.

This is a somewhat extensive explanation of how powers arise.

$\endgroup$
  • $\begingroup$ Damn, well explained. $\endgroup$ – Goose Bumper May 29 '13 at 20:33

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.