This blog is part of a series dedicated to Fibonacci sequence. In the Series page you can find the other posts of the series.

In a previous blog I discussed different ways of implementing Fibonacci series, finishing with the mind-blowing and straightforward closed-form expression.

In this blog, I will show that the proposed closed form does generate the Fibonacci series using the following ansatz¹:

\[f_n \propto \varphi^n - \psi^n\]

where $\varphi$ and $\psi$ are to unknown constants. Now, if we replace the ansatz into the Fibonacci recurrence relation, we get as a result

\[f_n \propto f_{n-1} + f_{n-2} \propto \varphi^n (\varphi^{-1} + \varphi^{-2}) - \psi^n (\psi^{-1} + \psi^{-2})\]

and therefore the only way to comply with the recurrence formula is if and only if

\[\varphi^{-1} + \varphi^{-2} = \psi^{-1} + \psi^{-2} = 1.\]

Following this through we can see that

\[\varphi^{-1} + \varphi^{-2} = \frac{\varphi + 1}{\varphi^{2}} = 1 \Leftrightarrow \varphi^{2} - \varphi - 1 = 0\]

where the same equation is also valid for $\psi$, and therefore both constants are the roots of a polynomial, meaning they are the solution to

\[x^2 - x - 1 = 0\]

or

\[\varphi = \frac{1}{2}\left(1+\sqrt{5}\right) \text{ } \psi = \frac{1}{2}\left(1-\sqrt{5}\right).\]

The proportionality constant can be extracted by the initial condition $f_2 = 1$ resulting in

\[f_2 = c \frac{\left(1+\sqrt{5}\right)^2-\left(1-\sqrt{5}\right)^2}{4}=c\sqrt{5}.\]

So, Fibonacci series can be expressed as result of an analytical function

\[f_n = \frac{\varphi^n - \psi^n}{\sqrt{5}}\]

As final step, it is easy to verify $\left\vert\psi^n/\sqrt{5}\right\vert<1/2$ and therefore

\[f_n = \left[\frac{\varphi^n}{\sqrt{5}}\right]\]

where $[\cdot]$ denote round to the closest integer.

Now the question is, is it possible to derive this formula without being assisted by the ansatz? Can we gain more insight into why this particular closed form? I am planning to explore these questions in future blogs.

References