Fibonacci Sequence Without Recursion

A Different Approach

The classic lesson in recursion for new programmers is finding the nth value of the Fibonacci sequence. It is a nice way to teach the basics of recursion since the Fibonacci sequence should be familiar to most people and the idea of summing the two previous elements in the sequence is simple enough to grasp. However, if you want to calculate $F_n$ for some large $n$, or you have some value $m$ and want to find $n$ such that $F_n = m$, there is a more efficient closed-form solution.

Relation to the Golden Ratio

Consider the first few terms of the Fibonacci sequence: $0,1,1,2,3,5,8,13,\dots$. Skipping the base cases $F_1 = 0, F_2 = 1$ and taking the ratio between consecutive terms we get the ratios $(\frac{F_n}{F_{n-1}})_{n=3}^{\infty} = (1,2,1.5,\frac{5}{3},1.6,1.65,\dots)$. At a glance there seems to be a pattern here, in fact this sequence will quickly converge upon the golden ratio.

Viewed graphically, the red dots are values of the Fibonacci sequence, blue dots are the values in our sequence of ratios, and the dashed orange line is $y=\frac{1+\sqrt{5}}{2}$ — the true golden ratio. Visually it appears that this ratio converges very quickly to the golden ratio. Now that we have motivated the connection between these two sequences, we will use linear algebra to derive a closed-form solution to the value of any $F_n$.

Deriving the Closed-Form Solution

Representing the Sequence as a Linear Operator

We can treat the Fibonacci sequence as linear operator $T$ on $\mathbb{R}^2$. We will define this operator as $T(a,b) = (b, a+b)$. First we will use induction to show that $T^n(0,1) = (F_n,F_{n+1})$ for any $n \in \mathbb{N}$. For our base case, $n=1$, by definition $T(0,1) = (1,1) = (F_1, F_2) = (F_n, F_{n+1})$. Now assume that this holds for all $n < k$.

$$\begin{align*} T^k(0,1) &= TT^{k-1}(0,1) \\ &= T(F_{k-1}, F_k) \\ &= T(F_k, F_{k-1} + F_k) \\ &= (F_k, F_{k+1}) \end{align*}$$

Thus $T^n(0,1) = (F_n,F_{n+1})$ for all $n \in \mathbb{N}$.

Finding the Eigenvalues

Given some eigenvalue $\lambda$ and its respective eigenvector $v$, we know $Tv - \lambda v = 0 \implies Tv = \lambda v \implies (b,a+b) = (\lambda a, \lambda b)$. This gives us the following equations:

$$\begin{gather} b = \lambda a \\ a + b = \lambda b \end{gather}$$

Substituting (1) into (2) gives $a + \lambda a = \lambda^2 a \implies (\lambda^2 - \lambda - 1)a = 0$. Clearly $a$ cannot be zero since that would imply $b$ is also zero, but our eigenvector $(a,b)$ cannot be zero. Thus the quadratic given by $\lambda^2 - \lambda - 1$ must be zero. Apply the quadratic equation to solve for the roots:

$$\begin{align*} \lambda &= \frac{1 \pm \sqrt{1^2-4(1)(-1)}}{2} \\ &= \frac{1 \pm \sqrt{5}}{2} \end{align*}$$

Recall that the formula for the golden ratio is $\phi = \frac{1 + \sqrt{5}}{2}$, thus the golden ratio is one of the eigenvalues for $T$. Our second eigenvalue, $\frac{1 - \sqrt{5}}{2}$, is the conjugate of the golden ratio and we will denote it as $\psi$.

Creating a Basis

Now we will find a basis for $\mathbb{R}^2$ consisting of eigenvectors of $T$. We know we have the eigenvalues $\phi$ and $\psi$. Let $v = (a,b)$ be an eigenvector of $\mathbb{R}^2$ corresponding to the eigenvalue $\phi$ such that $Tv = (b,a+b) = \phi v = (\phi a, \phi b)$. This implies the following relations:

$$\begin{gather} b = \phi a \\ a + b = \phi b \end{gather}$$

Substituting (3) into (4) we get $a + \phi a = \phi^2 a$. However, $\phi^2 = 1 + \phi$. Using this to simplify, $a + \phi a = (1 + \phi)a = a + \phi a$. Thus a solution is $a = 1$ from which (3) gives us $b = \phi$, thus our eigenvector is $(1, \phi)$. A similar process gives us the eigenvector $(1, \psi)$ for the eigenvalue $\psi$. In combination, $(1, \phi), (1, \psi)$ is a basis for $\mathbb{R}^2$ consisting of eigenvectors of $T$.

Using This Basis to Compute $T^n(0,1)$

Let $c_1,c_2 \in \mathbb{R}$ such that $(0,1) = c_1v_1 + c_2v_2$ where $v_1 = (1,\phi)$ and $v_2 = (1,\psi)$.

$$\begin{align*} (0,1) &= c_1v_1 + c_2v_2 \\ &= c_1(1,\phi) + c_2(1,\psi) \\ &= (c_1,c_1\phi) + (c_2, c_2\psi) \\ &= (c_1+c_2, c_1\phi + c_2\psi) \\ \end{align*}$$

This implies

$$\begin{gather*} 0 = c_1+c_2 \implies c_1 = -c_2 \end{gather*}$$

and

$$\begin{align*} 1 &= c_1\phi + c_2\psi \\ &= c_1(\phi - \psi) \\ &= c_1\Big[\Big(\frac{1+\sqrt{5}}{2}\Big) - \Big(\frac{1-\sqrt{5}}{2}\Big)\Big] \\ &= c_1\sqrt{5} \\ &\implies c_1 = \frac{1}{\sqrt{5}} \end{align*}$$

Similarly, we obtain $c_2 = -\frac{1}{\sqrt{5}}$. Thus $(0,1) = \frac{1}{\sqrt{5}}v_1 - \frac{1}{\sqrt{5}}v_2$. Now we can compute $T^n(0,1)$:

$$\begin{align*} T^n(0,1) &= T^n(\frac{1}{\sqrt{5}}v_1 - \frac{1}{\sqrt{5}}v_2) \\ &= \frac{1}{\sqrt{5}}T^n(v_1) - \frac{1}{\sqrt{5}}T^n(v_2) \\ &= \frac{1}{\sqrt{5}}(\phi^n v_1 - \psi^n v_2) \\ &= \frac{1}{\sqrt{5}}((\phi^n, \phi^{n+1}) - (\psi^n, \psi^{n+1})) \\ &= \frac{1}{\sqrt{5}}(\phi^n - \psi^n, \phi^{n+1} - \psi^{n+1}) \end{align*}$$

Recall that earlier we proved that $T^n(0,1) = (F_n,F_{n+1})$. Comparing this to the equation above we arrive at $F_n = \frac{1}{\sqrt{5}}(\phi^n - \psi^n) = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n]$. This is called Binet’s formula. Note that we are only interested in values where $n \geq 0$ and for these values $\frac{\psi^n}{\sqrt{5}} < \frac{1}{2}$. In fact, this error is practically nonexistent by the time we reach $n=8$ ($< 0.01$). Armed with this, we can further simplify the formula by simply rounding the $\phi$ portion to the nearest integer. In its final form, we achieve the following closed-form expression for the Fibonacci sequence for $n \geq 0$:

$$F_n = \Big\lfloor \frac{\phi^n}{\sqrt{5}} \Big\rceil$$

Bonus: Getting the Index of a Fibonacci Value

Our closed-form solution can be easily reversed (with some slight hand-waving where we temporarily drop the rounding function):

$$\begin{gather*} F_n = \frac{\phi^n}{\sqrt{5}} \implies \\ \sqrt{5}F_n = \phi^n \implies \\ \log_\phi^n = \log_\phi{\sqrt{5}F_n} \implies \\ n = \Big\lfloor \log_\phi{\sqrt{5}F_n} \Big\rceil \end{gather*}$$

So we can express the index $n$ as a function of some Fibonacci value F, i.e. $n(F) = \Big\lfloor \log_\phi{\sqrt{5}F} \Big\rceil$ for $F > 0$.