# intuition for the closed form of the fibonacci sequence

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

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?

• Do you know the fact that $$\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi\;?$$ – Brian M. Scott May 29 '13 at 6:05
• Yes. Okay, so that clears up my first question. The next question: why divide by sqrt(5)? – Goose Bumper May 29 '13 at 6:10
• 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$? – Noy Soffer May 29 '13 at 6:12

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

• For the last paragraph: Of course there is the exceptional case that the sequence rather grows like $\hat\varphi^n$ instead ... – Hagen von Eitzen May 29 '13 at 6:20
• 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? – Goose Bumper May 29 '13 at 6:22
• @Hagen: Yep; caught it in the addition, but had to go back to fix it in the original paragraph. – Brian M. Scott May 29 '13 at 6:25
• @GooseBumper: Does the added bit give you a better idea? – Brian M. Scott May 29 '13 at 6:25
• @BrianM.Scott I think so. Let me work it out and see, thanks! – Goose Bumper May 29 '13 at 6:31

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.

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