7.2 Linear Recurrence Relations

Section 7.1 used recursive rules to build strings and expressions. We now apply the same idea to a sequence, an ordered list of numbers indexed by integers.

We write a sequence as

a_0,a_1,a_2,a_3,\ldots

The symbol $a_n$ means “the term whose index is $n$ .” The subscript is a position label, not multiplication: $a_3$ is the term at index $3$ .

A recurrence connects a term to earlier terms

A recurrence relation is an equation that defines $a_n$ using one or more earlier terms. For example,

a_n=a_{n-1}+3 \qquad(n\ge1)

says that each term is $3$ more than the preceding term.

The recurrence alone is not enough. We also need an initial condition, such as

a_0=2.

Now every term is determined:

\begin{aligned} a_1&=a_0+3=2+3=5,\\ a_2&=a_1+3=5+3=8,\\ a_3&=a_2+3=8+3=11. \end{aligned}

Thus the sequence begins

2,5,8,11,\ldots

If we changed only the initial value to $a_0=10$ , the same recurrence would produce a different sequence. A recurrence is like a machine rule; the initial conditions determine where the machine starts.

Order tells us how much history is required

The order of a recurrence is the greatest distance it looks backward.

The recurrence

a_n=2a_{n-1}+1

is first order because it uses only the immediately preceding term.

The recurrence

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

is second order because it reaches back two positions. It normally needs two initial values, such as $a_0$ and $a_1$ .

For example, with

a_0=1,qquad a_1=1,qquad a_n=a_{n-1}+a_{n-2}\quad(n\ge2),

we obtain

1,1,2,3,5,8,\ldots

At $n=2$ , both $a_1$ and $a_0$ are available. If only $a_0$ were supplied, $a_1$ would remain unknown and the machine could not begin.

Generating terms is not yet a closed formula

A recurrence gives a local rule. To find $a_{100}$ , it may require all preceding terms. A closed form expresses $a_n$ directly in terms of $n$ , without referring to earlier sequence values.

For the recurrence

a_0=2,qquad a_n=a_{n-1}+3,

repeated substitution gives

\begin{aligned} a_n &=a_{n-1}+3\\ &=(a_{n-2}+3)+3\\ &=a_{n-2}+2\cdot3\\ &=\cdots\\ &=a_0+n\cdot3\\ &=2+3n. \end{aligned}

The ellipsis represents the same substitution repeated until the index reaches $0$ . We can verify the formula by checking the base value and recurrence:

a_0=2+3(0)=2,

and

(2+3n)-[2+3(n-1)]=3.

Multiplicative growth unfolds into a product

Consider

b_0=5,qquad b_n=2b_{n-1}.

Unfolding gives

b_n=2b_{n-1}=2^2b_{n-2}=\cdots=2^n b_0=5\cdot2^n.

This is a geometric sequence. More generally,

b_0=c,qquad b_n=r b_{n-1}

has the closed form

b_n=cr^n.

Here $r$ is the fixed multiplication factor. The exponent $n$ counts how many times the recurrence multiplies by $r$ before reaching the base value.

Loading interactive lab...

Run a recurrence time machine. Configure first- or second-order dependencies, reveal terms one at a time, and scrub backward through the exact substitutions supporting a selected value. Removing a required seed breaks the dependency track at the first undefined term instead of silently inventing a number.

Loading concept check...

Loading practice...

Counting creates recurrences naturally

Chapter 6 counted disjoint cases by addition. If objects of size $n$ can be divided into disjoint classes whose remaining parts have smaller sizes, their counts satisfy a recurrence.

Example: tiling a board

Let $t_n$ be the number of ways to tile a board of length $n$ using:

a square tile of length $1$ ;
a domino of length $2$ .

Tiles may not overlap and must cover the board exactly.

We begin with two initial counts:

t_0=1,qquad t_1=1.

Why is $t_0=1$ instead of $0$ ? There is exactly one way to tile an empty board: use no tiles. This empty construction lets the recurrence work correctly at the boundary.

For $n\ge2$ , classify every tiling by its last tile.

If the last tile is a square, removing it leaves any tiling of length $n-1$ . This class has $t_{n-1}$ outcomes.
If the last tile is a domino, removing it leaves any tiling of length $n-2$ . This class has $t_{n-2}$ outcomes.

The two classes are disjoint because a tiling cannot end with both tile types. They cover all tilings because every nonempty tiling has a last tile. The sum principle therefore gives

t_n=t_{n-1}+t_{n-2}.

Now compute:

\begin{aligned} t_2&=t_1+t_0=1+1=2,\\ t_3&=t_2+t_1=2+1=3,\\ t_4&=t_3+t_2=3+2=5,\\ t_5&=t_4+t_3=5+3=8. \end{aligned}

Notice the logical chain:

\text{partition by the last construction step} \longrightarrow \text{bijections with smaller objects} \longrightarrow \text{add the class counts} \longrightarrow \text{recurrence}.

The recurrence is not a guessed numerical pattern. It records a structural counting argument.

What “linear” means

A recurrence is linear when earlier terms appear only to the first power and are not multiplied by one another.

For example,

a_n=5a_{n-1}-6a_{n-2}

is linear. In contrast,

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

is nonlinear because two earlier terms are multiplied.

A linear recurrence is homogeneous when there is no additional term depending only on $n$ . Thus

a_n=5a_{n-1}-6a_{n-2}

is homogeneous, while

a_n=5a_{n-1}-6a_{n-2}+n

is nonhomogeneous because of the extra $n$ .

The recurrence has constant coefficients when the multipliers of earlier terms, such as $5$ and $-6$ , do not change with $n$ .

Solving a second-order homogeneous recurrence

Consider

a_n=5a_{n-1}-6a_{n-2} \qquad(n\ge2).

We first look for a geometric solution $a_n=r^n$ . Substitution gives

r^n=5r^{n-1}-6r^{n-2}.

For $r\ne0$ , divide by $r^{n-2}$ :

r^2=5r-6.

Move every term to one side:

r^2-5r+6=0.

This is the characteristic equation. Factoring gives

(r-2)(r-3)=0,

so its distinct roots are $r=2$ and $r=3$ .

Each root produces a geometric solution. Any linear combination is also a solution:

a_n=A2^n+B3^n.

The constants $A$ and $B$ are determined by the two initial conditions. Suppose

a_0=2,qquad a_1=5.

At $n=0$ ,

A+B=2.

At $n=1$ ,

2A+3B=5.

Subtracting twice the first equation from the second gives $B=1$ , and then $A=1$ . Therefore

\boxed{a_n=2^n+3^n}.

We can verify it directly:

5a_{n-1}-6a_{n-2} =5(2^{n-1}+3^{n-1})-6(2^{n-2}+3^{n-2}) =2^n+3^n.

Repeated characteristic roots

If the characteristic equation has the same root $r$ twice, the two independent building blocks are

r^n \qquad\text{and}\qquad nr^n.

Therefore the general form is

a_n=(A+Bn)r^n.

For example, the recurrence

a_n=6a_{n-1}-9a_{n-2}

has characteristic equation

r^2-6r+9=(r-3)^2=0,

so its solutions have the form

a_n=(A+Bn)3^n.

The initial conditions still determine $A$ and $B$ .

Loading interactive lab...

Tile boards by dragging squares and dominoes into place, then collapse the full gallery into “last square” and “last domino” families. Remove the final tile to reveal the reversible maps to sizes $n-1$ and $n-2$ , and watch the recurrence ledger update from actual constructions.

Loading concept check...

Loading practice...

Note

Initial conditions start a recurrence, its order tells how many earlier values it needs, and a counting recurrence must come from disjoint exhaustive classes—not merely from matching the first few numbers.

Section bridge

The recurrences above depend on a fixed number of immediately preceding terms. Recursive algorithms create another important shape: one problem of size $n$ becomes several subproblems of size $n/b$ . Section 7.3 will turn that execution pattern into divide-and-conquer recurrences and recursion trees.

7.2 Linear Recurrence Relations

Section 7.1 used recursive rules to build strings and expressions. We now apply the same idea to a sequence, an ordered list of numbers indexed by integers.

We write a sequence as

a_0,a_1,a_2,a_3,\ldots

The symbol $a_n$ means “the term whose index is $n$ .” The subscript is a position label, not multiplication: $a_3$ is the term at index $3$ .

A recurrence connects a term to earlier terms

A recurrence relation is an equation that defines $a_n$ using one or more earlier terms. For example,

a_n=a_{n-1}+3 \qquad(n\ge1)

says that each term is $3$ more than the preceding term.

The recurrence alone is not enough. We also need an initial condition, such as

a_0=2.

Now every term is determined:

\begin{aligned} a_1&=a_0+3=2+3=5,\\ a_2&=a_1+3=5+3=8,\\ a_3&=a_2+3=8+3=11. \end{aligned}

Thus the sequence begins

2,5,8,11,\ldots

Order tells us how much history is required

The order of a recurrence is the greatest distance it looks backward.

The recurrence

a_n=2a_{n-1}+1

is first order because it uses only the immediately preceding term.

The recurrence

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

is second order because it reaches back two positions. It normally needs two initial values, such as $a_0$ and $a_1$ .

For example, with

a_0=1,qquad a_1=1,qquad a_n=a_{n-1}+a_{n-2}\quad(n\ge2),

we obtain

1,1,2,3,5,8,\ldots

At $n=2$ , both $a_1$ and $a_0$ are available. If only $a_0$ were supplied, $a_1$ would remain unknown and the machine could not begin.

Generating terms is not yet a closed formula

A recurrence gives a local rule. To find $a_{100}$ , it may require all preceding terms. A closed form expresses $a_n$ directly in terms of $n$ , without referring to earlier sequence values.

For the recurrence

a_0=2,qquad a_n=a_{n-1}+3,

repeated substitution gives

\begin{aligned} a_n &=a_{n-1}+3\\ &=(a_{n-2}+3)+3\\ &=a_{n-2}+2\cdot3\\ &=\cdots\\ &=a_0+n\cdot3\\ &=2+3n. \end{aligned}

The ellipsis represents the same substitution repeated until the index reaches $0$ . We can verify the formula by checking the base value and recurrence:

a_0=2+3(0)=2,

and

(2+3n)-[2+3(n-1)]=3.

Multiplicative growth unfolds into a product

Consider

b_0=5,qquad b_n=2b_{n-1}.

Unfolding gives

b_n=2b_{n-1}=2^2b_{n-2}=\cdots=2^n b_0=5\cdot2^n.

This is a geometric sequence. More generally,

b_0=c,qquad b_n=r b_{n-1}

has the closed form

b_n=cr^n.

Here $r$ is the fixed multiplication factor. The exponent $n$ counts how many times the recurrence multiplies by $r$ before reaching the base value.

Loading interactive lab...

Loading concept check...

Loading practice...

Counting creates recurrences naturally

Chapter 6 counted disjoint cases by addition. If objects of size $n$ can be divided into disjoint classes whose remaining parts have smaller sizes, their counts satisfy a recurrence.

Example: tiling a board

Let $t_n$ be the number of ways to tile a board of length $n$ using:

a square tile of length $1$ ;
a domino of length $2$ .

Tiles may not overlap and must cover the board exactly.

We begin with two initial counts:

t_0=1,qquad t_1=1.

Why is $t_0=1$ instead of $0$ ? There is exactly one way to tile an empty board: use no tiles. This empty construction lets the recurrence work correctly at the boundary.

For $n\ge2$ , classify every tiling by its last tile.

If the last tile is a square, removing it leaves any tiling of length $n-1$ . This class has $t_{n-1}$ outcomes.
If the last tile is a domino, removing it leaves any tiling of length $n-2$ . This class has $t_{n-2}$ outcomes.

The two classes are disjoint because a tiling cannot end with both tile types. They cover all tilings because every nonempty tiling has a last tile. The sum principle therefore gives

t_n=t_{n-1}+t_{n-2}.

Now compute:

\begin{aligned} t_2&=t_1+t_0=1+1=2,\\ t_3&=t_2+t_1=2+1=3,\\ t_4&=t_3+t_2=3+2=5,\\ t_5&=t_4+t_3=5+3=8. \end{aligned}

Notice the logical chain:

\text{partition by the last construction step} \longrightarrow \text{bijections with smaller objects} \longrightarrow \text{add the class counts} \longrightarrow \text{recurrence}.

The recurrence is not a guessed numerical pattern. It records a structural counting argument.

What “linear” means

A recurrence is linear when earlier terms appear only to the first power and are not multiplied by one another.

For example,

a_n=5a_{n-1}-6a_{n-2}

is linear. In contrast,

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

is nonlinear because two earlier terms are multiplied.

A linear recurrence is homogeneous when there is no additional term depending only on $n$ . Thus

a_n=5a_{n-1}-6a_{n-2}

is homogeneous, while

a_n=5a_{n-1}-6a_{n-2}+n

is nonhomogeneous because of the extra $n$ .

The recurrence has constant coefficients when the multipliers of earlier terms, such as $5$ and $-6$ , do not change with $n$ .

Solving a second-order homogeneous recurrence

Consider

a_n=5a_{n-1}-6a_{n-2} \qquad(n\ge2).

We first look for a geometric solution $a_n=r^n$ . Substitution gives

r^n=5r^{n-1}-6r^{n-2}.

For $r\ne0$ , divide by $r^{n-2}$ :

r^2=5r-6.

Move every term to one side:

r^2-5r+6=0.

This is the characteristic equation. Factoring gives

(r-2)(r-3)=0,

so its distinct roots are $r=2$ and $r=3$ .

Each root produces a geometric solution. Any linear combination is also a solution:

a_n=A2^n+B3^n.

The constants $A$ and $B$ are determined by the two initial conditions. Suppose

a_0=2,qquad a_1=5.

At $n=0$ ,

A+B=2.

At $n=1$ ,

2A+3B=5.

Subtracting twice the first equation from the second gives $B=1$ , and then $A=1$ . Therefore

\boxed{a_n=2^n+3^n}.

We can verify it directly:

5a_{n-1}-6a_{n-2} =5(2^{n-1}+3^{n-1})-6(2^{n-2}+3^{n-2}) =2^n+3^n.

Repeated characteristic roots

If the characteristic equation has the same root $r$ twice, the two independent building blocks are

r^n \qquad\text{and}\qquad nr^n.

Therefore the general form is

a_n=(A+Bn)r^n.

For example, the recurrence

a_n=6a_{n-1}-9a_{n-2}

has characteristic equation

r^2-6r+9=(r-3)^2=0,

so its solutions have the form

a_n=(A+Bn)3^n.

The initial conditions still determine $A$ and $B$ .

Loading interactive lab...

Loading concept check...

Loading practice...

Note