Computing the first few terms of any recurrence relation is fairly easy to do by hand; however, finding larger terms is impractical. It would be nice if we had some mathematical function in which we simply plug in a number, and it returns the n^th term in a sequence. Fortunately, for linear recurrence relations, such a mathematical function does exist! This is known as a closed-form solution to a recurrence relation. We will explore a technique that allows us to derive such a solution for any linear recurrence relation.

As an example, we will derive the closed-form solution for the classic Fibonacci sequence.

We start with the recurrence relation, which in this case is:

$a_n = a_{n-1} + a_{n-2}$

Before we proceed, we should note that the recurrence relation for the Fibonacci sequence is known as a homogenous relation because there is no explicit dependence on n; the equation doesn’t look like this:

$a_n = a_{n-1} + a_{n-2} + f(n)$

For example, this recurrence relation:

$a_n = a_{n-1} + a_{n-2} + n^3$

Is not homogeneous because of the n³ term.

To solve a homogeneous linear recurrence relation, we essentially guess the form of the closed-form solution and we assign proper coefficients to make our function work. Any guess of a mathematical function that satisfies the recurrence relation is acceptable; however, power functions work particularly well for this case so we start by assuming that a_n = rⁿ. We then plug it into the recurrence relation:

$r^n = r^{n-1} + r^{n-2}$

We perform the following algebraic manipulations:

$r^n = \frac{r^n}{r} + \frac{r^n}{r^2}$

$1 = \frac{1}{r} + \frac{1}{r^2}$

$r^2 = r + 1$

$r^2 - r - 1 = 0$

The equation above is known as the characteristic equation of the recurrence relation.

In this exercise, we will focus on handling roots that are real and distinct. In later exercises, we will discuss other scenarios. The roots of the characteristic equation for the Fibonacci recurrence relation (solved using the quadratic formula) are:

$r_1 = \frac{1}{2}\left ( 1 + \sqrt{5} \right )$

$r_2 = \frac{1}{2}\left ( 1 - \sqrt{5} \right )$

Since we have two choices for r and the Fibonacci sequence is a linear relation, the final solution for a_n is a linear combination of r₁ⁿ and r₂ⁿ like so:

$a_n = \alpha r_{1} ^n + \beta r_{2}^n$

We can determine the constants 𝛼 and 𝛽 by plugging in the following initial conditions into the equation above.

$a_0 = 0, \ a_1 = 1$

Leading to two equations which can be solved for 𝛼 and 𝛽

$\alpha + \beta = 0$

$\alpha r_1 + \beta r_2 = 1$

Solving this system of equations to determine 𝛼 and 𝛽 yields:

$\alpha= \frac{1}{r_1 - r_2}, \ \beta = - \frac{1}{r_1 - r_2}$

Leading to the final closed-form equation for the Fibonacci sequence:

$a_n= \frac{r_{1}^n}{r_1 - r_2} - \frac{r_{2}^n}{r_1 - r_2}$

$a_n= \frac{r_{1}^n - r_{2}^n}{r_1 - r_2}$

Remember:

$r_1 = \frac{1}{2}\left ( 1 + \sqrt{5} \right )$

$r_2 = \frac{1}{2}\left ( 1 - \sqrt{5} \right )$