Recursive Sequences

What this move does

In a recursive sequence of order $k$ , each term is determined by the $k$ terms before it. The most common, and the most systematic, kind is the linear recurrence with constant coefficients

a_{n + 2} = p a_{n + 1} + q a_{n} .

The key observation: if a geometric sequence $λ^{n}$ satisfies the recurrence, then $λ^{n + 2} = p λ^{n + 1} + q λ^{n}$ , that is,

λ^{2} = p λ + q (the characteristic equation) .

Moreover, any linear combination of sequences satisfying the recurrence satisfies it too. So:

Write down the characteristic equation and find the characteristic roots $λ_{1}, λ_{2}$ .
If the roots are different, put $a_{n} = A λ_{1}^{n} + B λ_{2}^{n}$ ; if they are equal, put $a_{n} = (A + B n) λ^{n}$ .
Use the two initial values to set up equations and solve for $A, B$ ; then substitute back to check.

Predict first

$a_{0} = 1, a_{1} = 3, a_{n + 2} = 3 a_{n + 1} - 2 a_{n}$ . Find $a_{10}$ .

Choose an answer first; then you can see the result.

Work through one

Example: a₀ = 1, a₁ = 4, a_{n+2} = 5a_{n+1} − 6aₙ

Step 1 / 5

Compute a few terms
$1, 4, 14, 46, 146, \dots$ grows fast. The ratio column gets closer and closer to $3$ , a hint that the “main part” of the sequence is $3^{n}$ .

$a_{2} = 5 \cdot 4 - 6 \cdot 1 = 14$
The characteristic equation
The shape of the general term
Fit the initial values
Check

The first-order case: subtract the fixed point

$a_{n + 1} = p a_{n} + r$ ( $p \neq = 1$ ) is not a geometric sequence, but it is one up to a constant. Find the fixed point $x^{*} = p x^{*} + r$ and subtract the two equations:

a_{n + 1} - x^{*} = p (a_{n} - x^{*}),

so ${a_{n} - x^{*}}$ is a geometric sequence with common ratio $p$ .

a_{n + 1} = 3 a_{n} - 4

: the fixed point is

x^{*} = 2

and

a_{n} = 2 + 3 \cdot 3^{n}

. Drag

p

1

: the fixed point disappears and the sequence becomes arithmetic.

Double roots and complex roots

When the two roots are equal, $λ^{n}$ gives only one solution and we need another: it is $n λ^{n}$ . When the roots are complex conjugates, $i$ appears in the formula, but the sequence itself is still made of integers, and it may swing back and forth periodically.

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

: the characteristic roots

\frac{1 \pm 3 i}{2}

have modulus

1

and argument

6 0^{\circ}

. Six turns bring them back to the start, so the sequence has period

6

. That is the star of the next stop.

When it fails

Break it

Counterexample lab: remove one condition

Conclusion: $a_{n} = A λ_{1}^{n} + B λ_{2}^{n}$ can match any initial values

$a_{n + 2} = 5 a_{n + 1} - 6 a_{n}$ , with different roots $2, 3$ : two initial values, two unknowns, always solvable.

Practice

Exercise 1Basic

$a_{0} = 1, a_{n + 1} = 2 a_{n} + 3$ . Find $a_{5}$ and write down the general term.

Exercise 2Basic

$a_{0} = 2, a_{1} = 1, a_{n + 2} = a_{n + 1} + 6 a_{n}$ . Find $a_{6}$ .

Exercise 3Advanced

$a_{0} = 1, a_{1} = 6, a_{n + 2} = 6 a_{n + 1} - 9 a_{n}$ . Find the general term and $a_{4}$ .

Exercise 4Challenge

Let $f (n)$ be the number of strings of length $n$ made of the digits $0, 1, 2$ in which no two $0$ s are adjacent. Find $f (5)$ , and write down the recurrence that $f (n)$ satisfies and its characteristic roots.

What this move does

Work through one

Example: a₀ = 1, a₁ = 4, a_{n+2} = 5a_{n+1} − 6aₙ

The first-order case: subtract the fixed point

Double roots and complex roots

When it fails

Counterexample lab: remove one condition

Practice

Mistake Museum · Exhibits from this stop

The initial values are a₁, a₂, but the constants are solved as if they were a₀, a₁