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?
Best Answer
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$.)