# 21.3: Linear Recurrences

- Page ID
- 54600

So far we’ve solved recurrences with two techniques: guess-and-verify and plugand-chug. These methods require spotting a pattern in a sequence of numbers or expressions. In this section and the next, we’ll give cookbook solutions for two large classes of recurrences. These methods require no flash of insight; you just follow the recipe and get the answer

## Climbing Stairs

How many different ways are there to climb \(n\) stairs, if you can either step up one stair or hop up two? For example, there are five different ways to climb four stairs:

- step, step, step, step
- hop, hop
- hop, step, step
- step, hop, step
- step, step, hop

Working through this problem will demonstrate the major features of our first cookbook method for solving recurrences. We’ll fill in the details of the general solution afterward.

**Finding a Recurrence**

As special cases, there is 1 way to climb 0 stairs (do nothing) and 1 way to climb 1 stair (step up). In general, an ascent of \(n\) stairs consists of either a step followed by an ascent of the remaining \(n - 1\) stairs or a hop followed by an ascent of \(n - 2\) stairs. So the total number of ways to climb n stairs is equal to the number of ways to climb \(n - 1\) plus the number of ways to climb \(n - 2\). These observations define a recurrence:

\[\begin{aligned} f(0) &= 1 \\ f(1) &= 1 \\ f(n) &= f(n - 1) + f(n - 2) & \text{for } n \geq 2.\end{aligned}\]

Here, \(f(n)\) denotes the number of ways to climb \(n\) stairs. Also, we’ve switched from subscript notation to functional notation, from \(T_n\) to \(f_n\). Here the change is cosmetic, but the expressiveness of functions will be useful later.

This is the Fibonacci recurrence, the most famous of all recurrence equations. Fibonacci numbers arise in all sorts of applications and in nature. Fibonacci introduced the numbers in 1202 to study rabbit reproduction. Fibonacci numbers also appear, oddly enough, in the spiral patterns on the faces of sunflowers. And the input numbers that make Euclid’s GCD algorithm require the greatest number of steps are consecutive Fibonacci numbers.

**Solving the Recurrence **

The Fibonacci recurrence belongs to the class of linear recurrences, which are essentially all solvable with a technique that you can learn in an hour. This is somewhat amazing, since the Fibonacci recurrence remained unsolved for almost six centuries!

In general, a *homogeneous* linear recurrence has the form

\[\nonumber f(n) = a_1 f(n-1) + a_2 f(n-2) + \cdots + a_d f(n-d)\]

where \(a_1, a_2, \ldots, a_d\) and \(d\) are constants. The *order* of the recurrence is \(d\). Commonly, the value of the function \(f\) is also specified at a few points; these are called *boundary conditions*. For example, the Fibonacci recurrence has order \(d = 2\) with coefficients \(a_1 = a_2 = 1\) and \(g(n) = 0\). The boundary conditions are \(f(0) = 1\) and \(f(1) = 1\). The word “homogeneous” sounds scary, but effectively means “the simpler kind.” We’ll consider linear recurrences with a more complicated form later.

Let’s try to solve the Fibonacci recurrence with the benefit centuries of hindsight. In general, linear recurrences tend to have exponential solutions. So let’s guess that

\[\nonumber f(n) = x^n\]

where \(x\) is a parameter introduced to improve our odds of making a correct guess. We’ll figure out the best value for \(x\) later. To further improve our odds, let’s neglect the boundary conditions, \(f(0) = 0\) and \(f(1) = 1\), for now. Plugging this guess into the recurrence \(f(n) = f(n - 1) + f(n - 2)\) gives

\[\nonumber x^n = x^{n-1} + x^{n-2}.\]

Dividing both sides by \(x^{n-2}\) leaves a quadratic equation:

\[\nonumber x^2 = x + 1.\]

Solving this equation gives *two* plausible values for the parameter \(x\):

\[\nonumber x = \frac{1 \pm \sqrt{5}}{2}.\]

This suggests that there are at least two different solutions to the recurrence, neglecting the boundary conditions.

\[\nonumber f(n) = \left( \frac{1 + \sqrt{5}}{2} \right) ^n \text{ or } f(n) = \left( \frac{1 - \sqrt{5}}{2} \right) ^n\]

A charming features of homogeneous linear recurrences is that any linear combination of solutions is another solution.

Theorem \(\PageIndex{1}\)

*If \(f(n)\) and \(g(n)\) are both solutions to a homogeneous linear recurrence, then \(h(n) = sf(n) + tg(n)\) is also a solution for all \(s, t \in \mathbb{R}\).*

**Proof**-
\[\begin{aligned} h(n) &= sf(n) + tg(n) \\ &= s(a_1 f(n - 1) + \cdots + a_d f(n - d)) + t(a_1 g(n - 1) + \cdots + a_d g(n - d)) \\ &=a_1(s f(n - 1) + tg(n - 1)) + \cdots a_d(s f(n - d) + tg(n - d)) \\ &= a_1 h(n - 1) + \cdots + a_d h(n - d) \end{aligned}\]

The first step uses the definition of the function \(h\), and the second uses the fact that \(f\) and \(g\) are solutions to the recurrence. In the last two steps, we rearrange terms and use the definition of \(h\) again. Since the first expression is equal to the last, h is also a solution to the recurrence. \(\quad \blacksquare\)

The phenomenon described in this theorem—a linear combination of solutions is another solution—also holds for many differential equations and physical systems. In fact, linear recurrences are so similar to linear differential equations that you can safely snooze through that topic in some future math class.

Returning to the Fibonacci recurrence, this theorem implies that

\[\nonumber f(n) = s \left( \frac{1 + \sqrt{5}}{2} \right) ^n + t \left( \frac{1 - \sqrt{5}}{2} \right) ^n\]

is a solution for all real numbers \(s\) and \(t\). The theorem expanded two solutions to a whole spectrum of possibilities! Now, given all these options to choose from, we can find one solution that satisfies the boundary conditions, \(f(0) = 1\) and \(f(1) = 1\). Each boundary condition puts some constraints on the parameters \(s\) and \(t\). In particular, the first boundary condition implies that

\[\nonumber f(0) = s \left( \frac{1 + \sqrt{5}}{2} \right) ^0 + t \left( \frac{1 - \sqrt{5}}{2} \right) ^0 = s + t = 1.\]

Similarly, the second boundary condition implies that

\[\nonumber f(1) = s \left( \frac{1 + \sqrt{5}}{2} \right) ^1 + t \left( \frac{1 - \sqrt{5}}{2} \right) ^1 = 1.\]

Now we have two linear equations in two unknowns. The system is not degenerate, so there is a unique solution:

\[\nonumber s = \frac{1}{\sqrt{5}} \cdot \frac{1 + \sqrt{5}}{2} \quad s = -\frac{1}{\sqrt{5}} \cdot \frac{1 - \sqrt{5}}{2}.\]

These values of \(s\) and \(t\) identify a solution to the Fibonacci recurrence that also satisfies the boundary conditions:

\[\begin{aligned} f(n) &= \frac{1}{\sqrt{5}} \cdot \frac{1 + \sqrt{5}}{2} \left( \frac{1 + \sqrt{5}}{2} \right)^n - \frac{1}{\sqrt{5}} \cdot \frac{1 - \sqrt{5}}{2} \left( \frac{1 - \sqrt{5}}{2} \right)^n \\ &= \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{n+1} - \frac{1}{\sqrt{5}} \left( \frac{1 - \sqrt{5}}{2} \right)^{n + 1}. \end{aligned}\]

It is easy to see why no one stumbled across this solution for almost six centuries. All Fibonacci numbers are integers, but this expression is full of square roots of five! Amazingly, the square roots always cancel out. This expression really does give the Fibonacci numbers if we plug in \(n = 0, 1, 2,\) etc.

This closed form for Fibonacci numbers is known as Binet’s formula and has some interesting corollaries. p The first term tends to infinity because the base of the exponential, \((1 + \sqrt{5}) / 2 = 1.618 \ldots\) is greater than one. This value is often denoted \(\phi\) and called the “golden ratio.” The second term tends to zero, because \((1 - \sqrt{5}) / 2 = -0.618033988 \ldots\) has absolute value less than 1. This implies that the \(n\)th Fibonacci number is:

\[\nonumber f(n) = \frac{\phi ^{n+1}}{\sqrt{5}} + o(1).\]

Remarkably, this expression involving irrational numbers is actually very close to an integer for all large \(n\)—namely, a Fibonacci number! For example:

\[\nonumber \frac{\phi ^{20}}{\sqrt{5}} = 6765.000029 \cdots \approx f(19).\]

This also implies that the ratio of consecutive Fibonacci numbers rapidly approaches the golden ratio. For example:

\[\nonumber \frac{f(20)}{f(19)} = \frac{10946}{6765} = 1.618033998 \ldots.\]

## Solving Homogeneous Linear Recurrences

The method we used to solve the Fibonacci recurrence can be extended to solve any homogeneous linear recurrence; that is, a recurrence of the form

\[\nonumber f(n) = a_1 f(n - 1) + a_2 f(n - 2) + \cdots + a_d f(n - d)\]

where \(a_1, a_2, \ldots, a_d\) and \(d\) are constants. Substituting the guess \(f(n) = x_n\), as with the Fibonacci recurrence, gives

\[\nonumber x^n = a_1 x^{n-1} + a_2 x^{n-2} + \cdots + a_d x^{n-d}.\]

Dividing by \(x^{n-d}\) gives

\[\nonumber x^d = a_1 x^{d-1} + a_2 x^{d-2} + \cdots + a_{d-1} x + a_d.\]

This is called the *characteristic equation* of the recurrence. The characteristic equation can be read off quickly since the coefficients of the equation are the same as the coefficients of the recurrence.

The solutions to a linear recurrence are defined by the roots of the characteristic equation. Neglecting boundary conditions for the moment:

If \(r\) is a nonrepeated root of the characteristic equation, then \(r^n\) is a solution to the recurrence.

If \(r\) is a repeated root with multiplicity \(k\) then \(r^n, nr^n, n^2r^n, \ldots, n^{k-1}r^n\) are all solutions to the recurrence.

Theorem 21.3.1 implies that every linear combination of these solutions is also a solution.

For example, suppose that the characteristic equation of a recurrence has roots \(s, t,\) and \(u\) twice. These four roots imply four distinct solutions:

\[\nonumber f(n) = s^n \quad f(n) = t^n \quad f(n) = u^n \quad f(n) = nu^n.\]

Furthermore, every linear combination

\[f(n) = a \cdot s^n + b \cdot t^n + c \cdot u^n + d \cdot nu^n\]

is also a solution.

All that remains is to select a solution consistent with the boundary conditions by choosing the constants appropriately. Each boundary condition implies a linear equation involving these constants. So we can determine the constants by solving a system of linear equations. For example, suppose our boundary conditions were \(f(0) = 0\), \(f(1) = 1\), \(f(2) = 4\), and \(f(3) = 9\). Then we would obtain four equations in four unknowns:

\[\begin{aligned} f(0) &= 0 \quad \text{implies} \quad a \cdot s^0 + b \cdot t^0 + c \cdot u^0 + d \cdot 0u^0 = 0 \\ f(1) &= 1 \quad \text{implies} \quad a \cdot s^1 + b \cdot t^1 + c \cdot u^1 + d \cdot 0u^1 = 1 \\ f(2) &= 4 \quad \text{implies} \quad a \cdot s^2 + b \cdot t^2 + c \cdot u^2 + d \cdot 0u^2 = 4 \\ f(3) &= 9 \quad \text{implies} \quad a \cdot s^3 + b \cdot t^3 + c \cdot u^3 + d \cdot 0u^3 = 9 \\ \end{aligned}\]

This looks nasty, but remember that \(s, t,\) and \(u\) are just constants. Solving this system gives values for \(a, b, c,\) and \(d\) that define a solution to the recurrence consistent with the boundary conditions.

## Solving General Linear Recurrences

We can now solve all linear homogeneous recurrences, which have the form

\[\nonumber f(n) = a_1 f(n - 1) + a_2 f(n - 2) + \cdots a_d f(n - d).\]

Many recurrences that arise in practice do not quite fit this mold. For example, the Towers of Hanoi problem led to this recurrence:

\[\begin{aligned} f(1) &= 1 \\ f(n) &= 2f(n - 1) + 1 & (\text{for } n \geq 2). \end{aligned}\]

The problem is the extra \(+1\); that is not allowed in a homogeneous linear recurrence. In general, adding an extra function \(g(n)\) to the right side of a linear recurrence gives an *inhomogeneous linear recurrence*:

\[\nonumber f(n) = a_1 f(n - 1) + a_2 f(n - 2) + \cdots a_d f(n - d) + g(n).\]

Solving inhomogeneous linear recurrences is neither very different nor very difficult. We can divide the whole job into five steps:

- Replace \(g(n)\) by 0, leaving a homogeneous recurrence. As before, find roots of the characteristic equation.
- Write down the solution to the homogeneous recurrence, but do not yet use the boundary conditions to determine coefficients. This is called the
*homogeneous solution*. - Now restore \(g(n)\) and find a single solution to the recurrence, ignoring boundary conditions. This is called a
*particular solution*. We’ll explain how to find a particular solution shortly. - Add the homogeneous and particular solutions together to obtain the
*general solution*. - Now use the boundary conditions to determine constants by the usual method of generating and solving a system of linear equations.

As an example, let’s consider a variation of the Towers of Hanoi problem. Suppose that moving a disk takes time proportional to its size. Specifically, moving the smallest disk takes 1 second, the next-smallest takes 2 seconds, and moving the \(n\)th disk then requires \(n\) seconds instead of 1. So, in this variation, the time to complete the job is given by a recurrence with \(a + n\) term instead of \(a + 1\):

\[\begin{aligned} f(1) &= 1 \\ f(n) &= 2f(n - 1) + n & (\text{for } n \geq 2). \end{aligned}\]

Clearly, this will take longer, but how much longer? Let’s solve the recurrence with the method described above.

In Steps 1 and 2, dropping the \(+n\) leaves the homogeneous recurrence \(f(n) = 2f(n - 1)\). The characteristic equation is \(x = 2\). So the homogeneous solution is \(f(n) = c2^n\).

In Step 3, we must find a solution to the full recurrence \(f(n) = 2f(n - 1) + n\), without regard to the boundary condition. Let’s guess that there is a solution of the form \(f(n) = an + b\) for some constants \(a\) and \(b\). Substituting this guess into the recurrence gives

\[\begin{aligned} an + b &= 2(a(n-1) + b) + n \\ 0 &= (a + 1)n + (b - 2a). \end{aligned}\]

The second equation is a simplification of the first. The second equation holds for all \(n\) if both \(a + 1 = 0\) (which implies \(a = -1\)) and \(b - 2a = 0\) (which implies that \(b = -2\)). So \(f(n) = an + b = n - 2\) is a particular solution.

In the Step 4, we add the homogeneous and particular solutions to obtain the general solution

\[\nonumber f(n) = c2^n - n - 2.\]

Finally, in step 5, we use the boundary condition, \(f(1) = 1\), determine the value of the constant \(c\):

\[\begin{aligned} f(1) = 1 \quad &\text{IMPLIES} \quad c2^1 - 1 - 2 = 1 \\ &\text{IMPLIES} \quad c = 2. \end{aligned}\]

Therefore, the function \(f(n) = 2 \cdot 2^n - n - 2\) solves this variant of the Towers of Hanoi recurrence. For comparison, the solution to the original Towers of Hanoi problem was \(2^n - 1\). So if moving disks takes time proportional to their size, then the monks will need about twice as much time to solve the whole puzzle.

## How to Guess a Particular Solution

Finding a particular solution can be the hardest part of solving inhomogeneous recurrences. This involves guessing, and you might guess wrong.^{1} However, some rules of thumb make this job fairly easy most of the time.

- Generally, look for a particular solution with the same form as the inhomogeneous term \(g(n)\).
- If \(g(n)\) is a constant, then guess a particular solution \(f(n) = c\). If this doesn’t work, try polynomials of progressively higher degree: \(f(n) = bn + c\), then \(f(n) = an^2 + bn + c\), etc.
- More generally, if \(g(n)\) is a polynomial, try a polynomial of the same degree, then a polynomial of degree one higher, then two higher, etc. For example, if \(g(n) = 6n + 5\), then try \(f(n) = bn + c\) and then \(f(n) = an^2 + bn + c\).
- If \(g(n)\) is an exponential, such as \(3^n\), then first guess that \(f(n) = c3^n\). Failing that, try \(f(n) = bn3^n + c3^n\) and then \(an^2 3^n + bn3^n + c3^n\), etc.

The entire process is summarized on the following page.

^{1}Chapter 15 explains how to solve linear recurrences with generating functions—it’s a little more complicated, but it does not require guessing.