Linear recurrences, generating functions and inclusion-exclusion

This week you learn to solve the recurrences (recurrence relations) you set up last week: instead of writing $a_n$ in terms of earlier terms, you find a formula directly in terms of $n$. This topic is not on the midterm, it is a final exam topic. The final question is usually like this: “Solve the recurrence … with initial conditions …”. Then comes a generating function or inclusion-exclusion question.

Golden rules:

1. Characteristic equation: substitute $a_n = r^n$ and solve the equation in $r$.
2. Distinct roots $r_1 \neq r_2$: $a_n = \alpha r_1^n + \beta r_2^n$.
3. Double root $r$: $a_n = (\alpha + \beta n) r^n$. Whoever forgets the factor $n$ loses marks.
4. Find the constants with $a_0$, $a_1$. Compute one more term and check.
5. If it is not homogeneous: general solution = homogeneous solution + particular solution. Apply the initial condition last.

What is a linear homogeneous recurrence?

A linear homogeneous recurrence relation of degree $k$ with constant coefficients:

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k}, \qquad c_k \neq 0.$

Word by word:

If the degree is $k$, then $k$ initial conditions determine the sequence uniquely. On the final the degree is almost always 2.

Intuition: why $r^n$?

A first-order recurrence like $a_n = 2a_{n-1}$ multiplies by 2 at each step, and the solution is $a_n = a_0 2^n$. For second order too we expect the solution to be “exponential”. Write $a_n = r^n$ and put it into the recurrence:

$r^n = c_1 r^{n-1} + c_2 r^{n-2} \;\Longrightarrow\; r^2 - c_1 r - c_2 = 0.$

This is the characteristic equation, and its roots are the characteristic roots. Each root gives a basic solution; because the recurrence is linear, every linear combination of the basic solutions is also a solution.

Rule 1: distinct roots

If $r^2 - c_1 r - c_2 = 0$ gives two distinct roots $r_1, r_2$:

$a_n = \alpha_1 r_1^n + \alpha_2 r_2^n.$

Example. $a_n = a_{n-1} + 2a_{n-2}$, $a_0 = 2$, $a_1 = 7$.

1) r^2 = r + 2  ->  r^2 - r - 2 = 0  ->  (r - 2)(r + 1) = 0  ->  r = 2, r = -1
2) a_n = A 2^n + B (-1)^n
3) n = 0:  A + B = 2
   n = 1:  2A - B = 7
   add:    3A = 9  ->  A = 3,  B = -1
4) a_n = 3 * 2^n - (-1)^n
5) check: a_2 = 7 + 2*2 = 11 ;  formula 12 - 1 = 11

TIP · always check one term. Compute $a_2$ from the recurrence and from the formula. If they are not equal, there is a sign error in the system. On the exam it takes 20 seconds and saves your marks.

Rule 2: double root

If the characteristic equation has a single root ($r_0$, of multiplicity two), $r_0^n$ alone is not enough to satisfy two conditions. The second basic solution is $n r_0^n$:

$a_n = (\alpha_1 + \alpha_2 n)\, r_0^n.$

Example. $a_n = 4a_{n-1} - 4a_{n-2}$, $a_0 = 1$, $a_1 = 6$.

r^2 - 4r + 4 = (r - 2)^2 = 0   ->  r = 2 (double root)
a_n = (A + B n) 2^n
n = 0:  A = 1
n = 1:  (1 + B) * 2 = 6  ->  B = 2
a_n = (1 + 2n) 2^n
check: a_3 = 4*20 - 4*6 = 56 ;  formula 7 * 8 = 56

PITFALL · Writing $\alpha 2^n + \beta 2^n$ for a double root. This is really $(\alpha+\beta)2^n$, a single constant. It cannot satisfy both initial conditions. For a double root the second term must be $\beta n r^n$.

Verifying a solution by proof

On the final you are sometimes asked “Show that $a_n = \dots$ is a solution”. This is a direct proof: plug the formula into the right side and obtain the left side.

Claim. $a_n = 3\cdot 2^n - (-1)^n$ satisfies $a_n = a_{n-1} + 2a_{n-2}$ for all $n \ge 2$, with $a_0 = 2$, $a_1 = 7$.

Proof. For $n \ge 2$,

$a_{n-1} + 2a_{n-2} = 3\cdot 2^{n-1} - (-1)^{n-1} + 2\left(3\cdot 2^{n-2} - (-1)^{n-2}\right) = 3\cdot 2^{n-1} + 3\cdot 2^{n-1} - (-1)^{n-1} - 2(-1)^{n-2}.$

The first two terms give $3\cdot 2^n$. Since $(-1)^{n-1} = -(-1)^{n-2}$, the last two terms give $(-1)^{n-2} - 2(-1)^{n-2} = -(-1)^{n-2} = -(-1)^n$. Hence $a_{n-1} + 2a_{n-2} = 3\cdot 2^n - (-1)^n = a_n$. Also $a_0 = 3 - 1 = 2$ and $a_1 = 6 + 1 = 7$. $\blacksquare$

In plain words: add the two exponential parts separately. Use the trick $2^{n-1} + 2^{n-1} = 2^n$, and the fact that the sign changes when you shift the power of $(-1)$ by one.

Nonhomogeneous recurrences

Of the form $a_n = c_1 a_{n-1} + \dots + c_k a_{n-k} + F(n)$, with $F(n) \neq 0$. The solution:

$a_n = a_n^{(h)} + a_n^{(p)}$

$a_n^{(h)}$: the general solution of the homogeneous recurrence you get by deleting $F(n)$. $a_n^{(p)}$: any particular solution of the recurrence. A guessing table for the particular solution:

Example. $a_n = 3a_{n-1} + 4$, $a_0 = 1$.

homogeneous:  a_n = 3 a_{n-1}            ->  a_n(h) = A 3^n
particular:   a_n(p) = C  (try constant) ->  C = 3C + 4  ->  C = -2
general:      a_n = A 3^n - 2
condition:    a_0 = A - 2 = 1  ->  A = 3
result:       a_n = 3^(n+1) - 2      check: a_1 = 3 + 4 = 7 = 9 - 2

PITFALL · applying the initial condition to the homogeneous part. If you apply $a_0 = 1$ to $\alpha 3^n$ and then add $-2$, it comes out wrong. First write the full general solution ($a^{(h)} + a^{(p)}$), and apply the condition last.

Divide-and-conquer recurrences

For algorithms that split the problem into $a$ subproblems, each of size $n/b$, with combining taking $g(n)$ (binary search, merge sort):

$f(n) = a f(n/b) + g(n).$

Binary search: $f(n) = f(n/2) + 2$. Merge sort: $M(n) = 2M(n/2) + n$.

Master theorem. If $f(n) = a f(n/b) + cn^d$ with $a \ge 1$, $b > 1$, $c > 0$, $d \ge 0$, then:

$f(n) \text{ is } \begin{cases} O(n^d) & a < b^d \\ O(n^d \log n) & a = b^d \\ O(n^{\log_b a}) & a > b^d \end{cases}$

How to read it: compare $a$ (the number of branches) with $b^d$ (the rate at which the work at one level shrinks).

You can also compute small values by hand: if $f(n) = 2f(n/2) + 3$, $f(1) = 1$ then $f(2) = 5$, $f(4) = 13$, $f(8) = 29$.

Generating functions

The generating function of a sequence is the power series that carries the terms as coefficients:

$G(x) = a_0 + a_1 x + a_2 x^2 + \dots = \sum_{k=0}^{\infty} a_k x^k.$

Intuition: $x^k$ is a “shelf label”, and the coefficient says how many things are on that shelf. When you multiply polynomials, the exponents add; this matches exactly the job of “count the selections whose total is $k$”.

Expansions to memorize:

Counting example. You will buy 8 pastries of three kinds, with at least 2 of the cheese kind. How many different selections are there?

cheese:      x^2 + x^3 + ...  = x^2 / (1 - x)
other two:   1 + x + x^2 + ... = 1 / (1 - x)   (each)
G(x) = x^2 / (1 - x)^3
coefficient of x^8 = coefficient of x^6 in 1/(1-x)^3 = C(3+6-1, 6) = C(8, 6) = 28

For bounded variables (when there is an upper bound), write the series as a finite polynomial and find the coefficient by multiplying. This is what is done in the $e_1 + e_2 + e_3 = 6$ example in the questions.

You can also solve recurrences with generating functions: for $a_k = 3a_{k-1}$, $a_0 = 1$, we get $G(x) - 3xG(x) = 1$, $G(x) = \frac{1}{1-3x}$, so $a_k = 3^k$. On the final this method is rarer; the characteristic root method is what is mainly expected.

Inclusion-exclusion

For two sets $|A \cup B| = |A| + |B| - |A\cap B|$. For three sets:

$|A\cup B\cup C| = |A| + |B| + |C| - |A\cap B| - |A\cap C| - |B\cap C| + |A\cap B\cap C|.$

Intuition: when you add them one by one, you counted those in two sets twice, so subtract. But those in all three were added 3 times and then subtracted 3 times, so not counted at all: add them back once.

Example. How many numbers from $1..100$ are divisible by 2, 3 or 7?

|A| = floor(100/2) = 50     |B| = floor(100/3) = 33     |C| = floor(100/7) = 14
|AB| = floor(100/6) = 16    |AC| = floor(100/14) = 7    |BC| = floor(100/21) = 4
|ABC| = floor(100/42) = 2
|A u B u C| = 50 + 33 + 14 - 16 - 7 - 4 + 2 = 72

If “divisible by none” is asked, it is $100 - 72 = 28$. Forgetting this complement step is the most common loss.

Common mistakes