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.

Additional comments:

  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.
  3. The technique described here can be used to solve any linear homogeneous recurrence relation with constant coefficients.
Advertisements
This entry was posted in Fibonacci sequence, recurrence relations, sequences and series. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s