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 denote the nth Fibonacci number. Let’s start counting with , and say . Then . These are known as the initial conditions. For , . This is known as the recurrence.
The first thing I want to prove is that the set of solutions to the Fibonacci recurrence (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 is a solution to the Fibonacci recurrence. Most of the vector space axioms are satisfied simply because 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 and are solutions, then substituting for in the right side of the recurrence yields , which proves that is also a solution to the Fibonacci recurrence. Second, if is a solution and c is a constant then substituting into the right side of the recurrence yields , which means that 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 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 and 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 , where p and q are some constants that depend on the initial conditions. The set 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: . If we let and A denote the matrix, this equation becomes . 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 has as a solution. Since the Fibonacci recurrence can be represented just like this, , with the matrix A instead of 2 and a vector instead of , maybe there is also a solution to the Fibonacci recurrence of the form . We just need to figure out the value of r. So let’s substitute into the Fibonacci recurrence and see if there are any values of r that work. We get . Dividing by , we end up with . Solving this equation with the quadratic formula, we get not one but two values for r: , and . This means that and 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 , where and . The specific solution we want is the one that has values for p and q such that the initial conditions and are satisfied. Plugging and into , we have and . Using the fact that , we can solve this system of equations to find out that , . Therefore, the explicit solution to the Fibonacci recurrence is
This formula is known as Binet’s formula.
- The number is known as the golden ratio.
- The number is between -1 and 0, which means that as n gets larger and larger gets closer and closer to 0. Thus, for large values of n, .
- The technique described here can be used to solve any linear homogeneous recurrence relation with constant coefficients.