## An Explicit Solution to the Fibonacci Recurrence

The Fibonacci sequence is a famous sequence of numbers that starts 1, 1, 2, 3, 5, 8, 13, 21, and continues forever.  Each number in the sequence is the sum of the two previous numbers in the sequence.  It’s easy to generate the sequence this way, but if you want, say, the 1000th Fibonacci number, it’s going to take you a while to get there by hand.  In this post I’m going to discuss how to come up with a formula for the nth Fibonacci number.

Let’s let $F_n$ denote the nth Fibonacci number.  Let’s start counting with $n = 0$, and say $F_0 = 0$.  Then $F_1 = 1$.  These are known as the initial conditions. For $n \geq 2$, $F_n = F_{n-1} + F_{n-2}$.  This is known as the recurrence.

The first thing I want to prove is that the set of solutions to the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ (ignoring the initial conditions for now) form what’s called a vector space (under function addition and scalar multiplication).  To show that a set is a vector space we need to show that it satisfies a particular collection of axioms.  Suppose the sequence $\{s_n\}$ is a solution to the Fibonacci recurrence.  Most of the vector space axioms are satisfied simply because $s_n$ is a function; the ones we still need to check are that (1) adding two solutions gives us another solution, and (2) multiplying a solution by a constant (a scalar) gives us another solution.  First, if $s_n$ and $t_n$ are solutions, then substituting $s_n + t_n$ for $F_n$ in the right side of the recurrence yields $(s_{n-1} + t_{n-1}) + (s_{n-2} + t_{n-2}) = (s_{n-1} + s_{n-2}) + (t_{n-1} + t_{n-2}) = s_n + t_n$, which proves that $s_n + t_n$ is also a solution to the Fibonacci recurrence.  Second, if $s_n$ is a solution and c is a constant then substituting $cs_n$ into the right side of the recurrence yields $cs_{n-1} + cs_{n-2} = c(s_{n-1} + s_{n-2}) = cs_n$, which means that $c s_n$ is also a solution to the recurrence.  Thus (1) and (2) are satisfied, which means that the set of solutions to the Fibonacci recurrence is a vector space.  (Again, we’re ignoring the initial conditions.)

This may seem like a lot of overhead, but there’s a good reason. Vector spaces have something called a dimension.  (Example: Real Euclidean three-space $\mathbb{R}^3$ has dimension 3.)  The vector space consisting of the solutions to the Fibonacci recurrence turns out to have dimension 2.  (See below.)  Because of this, if we can find two solutions $s_n$ and $t_n$ to the Fibonacci recurrence that are not simply multiples of each other (more generally, are not linearly independent), then every solution to the Fibonacci recurrence must be of the form $p s_n + q t_n$, where p and q are some constants that depend on the initial conditions.  The set $\{s_n, t_n\}$ is called a basis of the solution space.

Let’s now see why the dimension of the solution space to the Fibonacci recurrence is 2. We can represent the Fibonacci recurrence in matrix form like so: $\displaystyle \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix}$.  If we let $X_n = (F_n, F_{n-1})$ and A denote the matrix, this equation becomes $X_n = A X_{n-1}$.  Since the transition matrix A has dimension 2, so does the vector space of solutions to the Fibonacci recurrence.

Now we just need to find two solutions to the Fibonacci recurrence that aren’t multiples of each other.  Going simpler, the recurrence $S_n = 2 S_{n-1}$ has $S_n = 2^n$ as a solution.  Since the Fibonacci recurrence can be represented just like this, $X_n = A X_{n-1}$, with the matrix A instead of 2 and a vector $X_n$ instead of $S_n$, maybe there is also a solution to the Fibonacci recurrence of the form $F_n = r^n$.  We just need to figure out the value of r.  So let’s substitute $F_n = r^n$ into the Fibonacci recurrence and see if there are any values of r that work.  We get $r^n = r^{n-1} + r^{n-2}$. Dividing by $r^{n-2}$, we end up with $r^2 = r + 1$.  Solving this equation with the quadratic formula, we get not one but two values for r: $\displaystyle r_1 = \frac{1 + \sqrt{5}}{2}$, and $\displaystyle r_2 = \frac{1 - \sqrt{5}}{2}$.  This means that $s_n = r_1^n$ and $t_n = r_2^n$ are both solutions to the Fibonacci recurrence.  And since these solutions are not multiples of each other, they can be our set of basis solutions!

This means that every solution to the Fibonacci recurrence must be of the form $F_n = p r_1^n + q r_2^n$, where $r_1 = \frac{1 + \sqrt{5}}{2}$ and $r_2 = \frac{1 - \sqrt{5}}{2}$.  The specific solution we want is the one that has values for p and q such that the initial conditions $F_0 = 0$ and $F_1 = 1$ are satisfied.  Plugging $n = 0$ and $n = 1$ into $F_n = p r_1^n + q r_2^n$, we have $0 = p + q$ and $1 = p r_1 + q r_2$.  Using the fact that $r_1 + r_2 = 1$, we can solve this system of equations to find out that $p = 1/\sqrt{5}$, $q = -1/\sqrt{5}$.  Therefore, the explicit solution to the Fibonacci recurrence is $\displaystyle F_n = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1 - \sqrt{5}}{2}\right)^n.$

This formula is known as Binet’s formula.

1. The number $r_1 = \frac{1+\sqrt{5}}{2}$ is known as the golden ratio.
2. The number $r_2 = \frac{1-\sqrt{5}}{2}$ is between -1 and 0, which means that as n gets larger and larger $r_2^n$ gets closer and closer to 0.  Thus, for large values of n, $F_n \approx \frac{1}{\sqrt{5}} r_1^n$.