Linear recurrences

Fibonacci's recurrence $F_{n} = F_{n - 1} + F_{n - 2}$ is easy to run and hard to solve: unrolling it doubles the work at every step, and its values suggest no formula to guess.

The previous lesson set up recurrences, rules that give each term of a sequence from earlier ones, and solved the simple ones by unrolling, or by guessing a formula and proving it by induction. Both methods stalled on the Fibonacci numbers $0, 1, 1, 2, 3, 5, 8, 13, \dots$ , which also count the bit strings with no two consecutive 1s, and left one clue: the ratio of consecutive terms settles near $1.618$ , as if the sequence grew like a power. This lesson follows the clue to a method that solves every recurrence of that shape, then extends it to recurrences with an extra term, the Tower of Hanoi's among them.

Trying a power

A recurrence is linear with constant coefficients if each term is a fixed combination of the $k$ terms before it, $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ , where the numbers $c_{i}$ do not depend on $n$ . The number $k$ is the order, and it is also how many initial conditions are needed. It is homogeneous, meaning nothing is added beyond the combination; a later section adds something.

Geometric sequences reproduce themselves under a shift: $r^{n}$ shifted back by one is $r^{n - 1}$ , the same sequence divided by $r$ . So try $a_{n} = r^{n}$ with $r \neq 0$ in the order $2$ recurrence $a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2}$ . It needs $r^{n} = c_{1} r^{n - 1} + c_{2} r^{n - 2}$ for every $n$ , and dividing by $r^{n - 2}$ removes $n$ altogether:

r^{2} = c_{1} r + c_{2}

This is the characteristic equation. For order $k$ it reads $r^{k} = c_{1} r^{k - 1} + \dots + c_{k}$ , and each root gives a solution $r^{n}$ , though not yet one that meets the initial conditions.

For $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ the equation is $r^{2} - 5 r + 6 = (r - 2) (r - 3) = 0$ , so $2^{n}$ and $3^{n}$ both satisfy the recurrence. Check one: $5 \times 3^{n - 1} - 6 \times 3^{n - 2} = 3^{n - 2} (15 - 6) = 3^{n}$ .

Two roots, two constants

The recurrence is linear, and that supplies the second ingredient. If $x_{n}$ and $y_{n}$ both satisfy it, so does $A x_{n} + B y_{n}$ for any constants $A$ and $B$ : multiply the equation for $x_{n}$ by $A$ , the one for $y_{n}$ by $B$ , and add. So when the characteristic equation has distinct roots $r_{1}$ and $r_{2}$ , every sequence

a_{n} = A r_{1}^{n} + B r_{2}^{n}

satisfies the recurrence, and the constants are free to meet the initial conditions. Setting $n = 0$ and $n = 1$ gives $A + B = a_{0}$ and $A r_{1} + B r_{2} = a_{1}$ . Subtracting $r_{1}$ times the first from the second leaves $B (r_{2} - r_{1}) = a_{1} - r_{1} a_{0}$ , solvable precisely because $r_{1} \neq r_{2}$ , and then $A = a_{0} - B$ .

That settles every such recurrence, not just some. The fitted formula and the true sequence agree at $n = 0$ and $n = 1$ , and both compute each term from the two before it by the same rule, so by induction they agree forever. The formula is the solution, and the characteristic equation has missed nothing. Always check a fitted formula against the first few terms, since that catches almost every slip in the fit.

Example. A path $1$ unit wide and $n$ units long is paved with square tiles in $2$ colours and dominoes, $1$ by $2$ , in $3$ colours. Find a formula for the number of pavings, and the number for length $6$ .

Sort the pavings by the last tile. A square, in $2$ colours, leaves any paving of length $n - 1$ ; a domino, in $3$ colours, leaves any paving of length $n - 2$ . So $a_{n} = 2 a_{n - 1} + 3 a_{n - 2}$ , with $a_{0} = 1$ (the empty path has one paving) and $a_{1} = 2$ . The characteristic equation $r^{2} - 2 r - 3 = (r - 3) (r + 1) = 0$ has roots $3$ and $- 1$ , so $a_{n} = A \times 3^{n} + B (- 1)^{n}$ . The conditions $A + B = 1$ and $3 A - B = 2$ give $A = \frac{3}{4}$ and $B = \frac{1}{4}$ :

a_{n} = \frac{3^{n + 1} + (- 1)^{n}}{4}

Check: the recurrence gives $a_{2} = 4 + 3 = 7$ and $a_{3} = 14 + 6 = 20$ , and the formula gives $\frac{27 + 1}{4} = 7$ and $\frac{81 - 1}{4} = 20$ . So $a_{6} = \frac{2187 + 1}{4} = 547$ . Fractional constants are normal: the recurrence guarantees integers.

Now you. Solve $a_{n} = a_{n - 1} + 6 a_{n - 2}$ with $a_{0} = 3$ and $a_{1} = 4$ , check against $a_{2}$ and $a_{3}$ , and find $a_{10}$ .

Answer

The equation $r^{2} - r - 6 = (r - 3) (r + 2) = 0$ has roots $3$ and $- 2$ . Then $A + B = 3$ and $3 A - 2 B = 4$ give $A = 2$ , $B = 1$ , so $a_{n} = 2 \times 3^{n} + (- 2)^{n}$ . The recurrence gives $a_{2} = 22$ and $a_{3} = 46$ ; the formula gives $18 + 4$ and $54 - 8$ . So $a_{10} = 2 \times 59 049 + 1024 = 119 122$ .

Binet's formula

For $F_{n} = F_{n - 1} + F_{n - 2}$ the characteristic equation is $r^{2} = r + 1$ , with roots

φ = \frac{1 + \sqrt{5}}{2} \approx 1.618, ψ = \frac{1 - \sqrt{5}}{2} \approx - 0.618

The first is the golden ratio, the $1.618$ the ratios were approaching (the letter has nothing to do with the totient of an earlier lesson). Their difference is $φ - ψ = \sqrt{5}$ .

The roots are distinct, so $F_{n} = A φ^{n} + B ψ^{n}$ . The condition $F_{0} = 0$ gives $B = - A$ , and then $F_{1} = 1$ gives $A (φ - ψ) = 1$ , so $A = \frac{1}{\sqrt{5}}$ . Therefore

F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}

This is Binet's formula, published by Jacques Binet in 1843, though Abraham de Moivre and Daniel Bernoulli had it more than a century before. A formula full of $\sqrt{5}$ that returns an integer for every $n$ looks miraculous, but expanding $(1 + \sqrt{5})^{n}$ and $(1 - \sqrt{5})^{n}$ by the binomial theorem shows why: the terms with even powers of $\sqrt{5}$ cancel in the difference, and each survivor carries exactly one $\sqrt{5}$ to cancel the denominator.

The formula also finishes a count from the previous lesson. Bit strings of length $n$ with no two consecutive 1s number $F_{n + 2}$ , so length $20$ has $F_{22} = 17 711$ of them among $1 048 576$ strings, and each extra bit multiplies the count by about $1.618$ , where unrestricted strings double.

The nearest integer

Since $| ψ | < 1$ , the powers $ψ^{n}$ shrink towards zero, alternating in sign: $ψ^{10} \approx 0.008$ . So the second term of Binet's formula, $\frac{ψ^{n}}{\sqrt{5}}$ , has size at most $\frac{1}{\sqrt{5}} \approx 0.447$ for every $n \geq 0$ , which is less than $\frac{1}{2}$ . The number $\frac{φ^{n}}{\sqrt{5}}$ is therefore within a half of the integer $F_{n}$ :

F_{n} is the nearest integer to \frac{φ^{n}}{\sqrt{5}}

This holds even at $n = 0$ , where $0.447$ rounds to $0$ , and the approximation tightens fast: $\frac{φ^{10}}{\sqrt{5}} \approx 55.0036$ against $F_{10} = 55$ , and $\frac{φ^{30}}{\sqrt{5}} \approx 832 040.0000002$ against $F_{30} = 832 040$ . It is the same shape as the derangement count of an earlier lesson, an exact count equal to a simple expression rounded, and for the same reason: an error term known to be below a half.

The fading term also explains the ratios. In $F_{n + 1} / F_{n}$ the $ψ$ terms vanish in the limit, so the ratio tends to $φ$ , overshooting and undershooting in turn as $ψ^{n}$ changes sign: $\frac{89}{55} \approx 1.61818$ , then $\frac{144}{89} \approx 1.61798$ . In any order $2$ recurrence with distinct real roots, the root of larger size sets the growth and the other only decides the rounding.

A repeated root

The fit needed $r_{1} \neq r_{2}$ . The recurrence $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ has characteristic equation $(r - 3)^{2} = 0$ and the single root $3$ , so $A \times 3^{n}$ is the only family on offer, and one constant cannot meet two initial conditions. A second solution is missing.

Nearby recurrences show where it hides. With distinct roots $r$ and $s$ , linearity makes $\frac{s^{n} - r^{n}}{s - r}$ a solution. As $s$ approaches $r$ the recurrence approaches the one with a double root, and this solution approaches the derivative of $x^{n}$ at $r$ , which is $n r^{n - 1}$ . Dividing by the constant $r$ gives the candidate $n r^{n}$ : the old solution with an extra factor $n$ .

The limit only suggests it, so check. A double root means $x^{2} - c_{1} x - c_{2} = (x - r)^{2}$ , so $c_{1} = 2 r$ and $c_{2} = - r^{2}$ , and then

c_{1} (n - 1) r^{n - 1} + c_{2} (n - 2) r^{n - 2} = r^{n} (2 n - 2 - n + 2) = n r^{n}

So the general solution is $a_{n} = (A + B n) r^{n}$ , fitted by $A = a_{0}$ and $(A + B) r = a_{1}$ , and the induction argument shows it is every solution. At higher orders a root of multiplicity $m$ contributes $r^{n}, n r^{n}, \dots, n^{m - 1} r^{n}$ .

Example. Solve $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ with $a_{0} = 1$ and $a_{1} = 6$ .

The double root is $3$ , so $a_{n} = (A + B n) 3^{n}$ . From $a_{0} = 1$ , $A = 1$ ; from $a_{1} = 6$ , $3 (1 + B) = 6$ , so $B = 1$ and $a_{n} = (n + 1) 3^{n}$ . The recurrence gives $a_{2} = 36 - 9 = 27$ and $a_{3} = 162 - 54 = 108$ , and the formula gives $3 \times 9 = 27$ and $4 \times 27 = 108$ .

Now you. Solve $a_{n} = 10 a_{n - 1} - 25 a_{n - 2}$ with $a_{0} = 2$ and $a_{1} = 15$ , and find $a_{6}$ .

Answer

The equation $r^{2} - 10 r + 25 = (r - 5)^{2}$ has the double root $5$ , so $a_{n} = (A + B n) 5^{n}$ with $A = 2$ and $5 (2 + B) = 15$ , so $B = 1$ and $a_{n} = (n + 2) 5^{n}$ . Check: the recurrence gives $a_{2} = 150 - 50 = 100 = 4 \times 25$ . So $a_{6} = 8 \times 15 625 = 125 000$ .

Adding a forcing term

The Tower of Hanoi recurrence $T_{n} = 2 T_{n - 1} + 1$ , the fewest moves for $n$ discs, is not homogeneous: the $+ 1$ is a forcing term, added whatever the earlier terms are. In general $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k} + f (n)$ , and linearity still does the work. If $p_{n}$ is one solution, a particular solution, and $a_{n}$ is any other, subtracting their recurrences cancels $f (n)$ , so $a_{n} - p_{n}$ solves the homogeneous recurrence. Every solution is therefore $p_{n}$ plus the general homogeneous solution, with the constants fitted last, to the whole formula.

A particular solution is guessed from the shape of the forcing term, with unknown coefficients: a constant for a constant, a polynomial of degree $d$ for a polynomial of degree $d$ . For Hanoi, $p = 2 p + 1$ gives $p = - 1$ , the homogeneous part has root $2$ , so $T_{n} = A \times 2^{n} - 1$ , and $T_{0} = 0$ gives $A = 1$ . That is $T_{n} = 2^{n} - 1$ , as unrolling found, with no series to sum.

Example. A procedure given an input of size $n$ does $n$ steps of work and then calls itself twice on size $n - 1$ ; size $0$ costs nothing. Find the total work $a_{n}$ .

The recurrence is $a_{n} = 2 a_{n - 1} + n$ with $a_{0} = 0$ . The forcing term has degree $1$ , so try $p_{n} = α n + β$ . Substituting, $α n + β = 2 α (n - 1) + 2 β + n$ , and matching coefficients gives $α = 2 α + 1$ and $β = 2 β - 2 α$ , so $α = - 1$ and $β = - 2$ . Then $a_{n} = A \times 2^{n} - n - 2$ , and $a_{0} = 0$ gives $A = 2$ :

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

Check: the recurrence gives $1, 4, 11$ for $n = 1, 2, 3$ , and the formula gives $4 - 3$ , $8 - 4$ and $16 - 5$ . At size $10$ the work is $2036$ steps.

Now you. Solve $a_{n} = a_{n - 1} + 2 a_{n - 2} + 4$ with $a_{0} = a_{1} = 1$ , and find $a_{10}$ .

Answer

A constant $p$ needs $p = 3 p + 4$ , so $p = - 2$ . The roots of $r^{2} - r - 2 = 0$ are $2$ and $- 1$ , so $a_{n} = A \times 2^{n} + B (- 1)^{n} - 2$ . The conditions give $A + B = 3$ and $2 A - B = 3$ , so $A = 2$ , $B = 1$ and $a_{n} = 2^{n + 1} + (- 1)^{n} - 2$ . Check: the recurrence gives $a_{2} = 7$ and $a_{3} = 13$ , as does the formula. So $a_{10} = 2048 + 1 - 2 = 2047$ .

The guess fails in one case, for the reason the double root did. The regions cut by $n$ lines in general position satisfy $R_{n} = R_{n - 1} + n$ , whose homogeneous part has root $1$ , so constants already solve it and $α n + β$ cannot produce the $+ n$ . Multiply the guess by $n$ , as with a repeated root: $p_{n} = n (α n + β)$ gives $2 α n - α + β = n$ , so $α = β = \frac{1}{2}$ and $R_{n} = 1 + \frac{n (n + 1)}{2}$ , the formula the previous lesson reached by guessing.

How far the method reaches

At any order the steps are the same: find the $k$ roots of the characteristic equation, write one term per root (with extra factors of $n$ for a repeated one), add a particular solution if there is a forcing term, and fit $k$ initial conditions. Bit strings with no three consecutive 1s obey $c_{n} = c_{n - 1} + c_{n - 2} + c_{n - 3}$ , whose cubic has one real root near $1.839$ and two complex ones of size below $1$ , so those counts grow like ${1.839}^{n}$ . Complex roots need no new idea; the answer comes out real.

The method needs both halves of its name. The derangement recurrence $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ has a coefficient that grows with $n$ , and trying $r^{n}$ leaves $n$ in the equation. The Catalan numbers, which count the ways to bracket a product, obey a recurrence in which terms multiply each other, so superposition fails. A tool that turned the counting argument itself into algebra would reach further, and the next lesson builds one: the generating function.