Recursion

In one sentence

Let $a_{n}$ be the answer for size $n$ . Instead of counting $a_{n}$ head-on, ask: what happens to the last element? In each case, once it is removed, what is left is often the same problem of size $n - 1$ or $n - 2$ .

a_{n} = (case 1) + (case 2) = a_{n - 1} + a_{n - 2}

So there are four steps: ① express what you want as $a_{n}$ ; ② work out the initial values $a_{1}, a_{2}, \dots$ by hand; ③ set up the recurrence; ④ get $a_{n}$ from the recurrence (by iterating, by the characteristic equation, or by computing up to the term you need).

Predict first

How many subsets of ${1, 2, \dots, 10}$ (including the empty set) contain no two consecutive integers?

89

144

233

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

Example: subsets with no two consecutive numbers

Step 1 / 5

Name the unknown, count the start
Let $a_{n}$ be the number of subsets of ${1, \dots, n}$ with no two consecutive numbers. $a_{1} = 2$ : $\emptyset, {1}$ .

$a_{1} = 2$
The second initial value
Look at the last element
The recurrence
Solve it

Stop 1 · Counting finite sets: derangements (Vol. 1)

A rearrangement of $1, 2, \dots, n$ in which no number stays in its original place is called a derangement. Again, look at where the last number $n$ goes, and who comes to position $n$ .

Example: the recurrence for the derangement numbers Dₙ

Step 1 / 5

Small cases
$D_{1} = 0$ , $D_{2} = 1$ ( $21$ ), $D_{3} = 2$ ( $231, 312$ ).

$D_{1} = 0, D_{2} = 1, D_{3} = 2$
Split by where n goes
The swapping case
The non-swapping case
The recurrence

Stop 2 · Linear recurrences and the characteristic equation (Vol. 5)

Once the recurrence is set up, if it is linear with constant coefficients, the characteristic equation gives the general term directly.

Example: how many strings of length n made of 0, 1, 2 have no two adjacent 0s?

Step 1 / 4

Look at the last digit
Call the number $b_{n}$ . If the last digit is $1$ or $2$ , the rest can be any good string: $2 b_{n - 1}$ . If the last digit is $0$ , the one before it must be $1$ or $2$ : $2 b_{n - 2}$ .

$b_{n} = 2 b_{n - 1} + 2 b_{n - 2}$
Initial values
Characteristic equation
Find the constants

Stop 3 · Iteration of a function (Vol. 2)

$f^{(n)} (x) = f (f^{(n - 1)} (x))$ is itself a recursion. The key is to find a quantity that makes this recursion simple.

One problem, several solutions

Let $f (x) = \frac{x}{1 + x}$ ( $x > 0$ ). Find $f^{(n)} (x)$ .

Guess, then prove

$f^{(2)} (x) = \frac{x / ( 1 + x )}{1 + x / ( 1 + x )} = \frac{x}{1 + 2 x}$ and $f^{(3)} (x) = \frac{x}{1 + 3 x}$ . Guess $f^{(n)} (x) = \frac{x}{1 + n x}$ . If it holds for $n$ , then $f^{(n + 1)} (x) = \frac{x / ( 1 + n x )}{1 + x / ( 1 + n x )} = \frac{x}{1 + ( n + 1 ) x}$ .

CostYou need a few terms to see the pattern, then one induction.

Take reciprocals: an arithmetic recursion

Let $u_{n} = \frac{1}{f ^{(n)} ( x )}$ . Since $\frac{1}{f ( y )} = \frac{1}{y} + 1$ , we get $u_{n} = u_{n - 1} + 1$ with $u_{0} = \frac{1}{x}$ . So $u_{n} = \frac{1}{x} + n$ and $f^{(n)} (x) = \frac{x}{1 + n x}$ .

CostSee through it at once, no guessing.

Stop 4 · Functional equations by recursion (Vol. 2)

For a functional equation on the positive integers, set one variable equal to $1$ and you get a recurrence for $f (n)$ .

Example: f: N⁺ → R, f(1) = 1, f(m + n) = f(m) + f(n) + mn. Find f(n)

Step 1 / 3

Set one variable to 1
Put $m = 1$ : $f (n + 1) = f (n) + f (1) + n = f (n) + n + 1$ .

$f (n + 1) - f (n) = n + 1$
Add them up
Check

Practice

Exercise 1Basic

How many subsets of ${1, 2, \dots, 8}$ (including the empty set) contain no two consecutive integers?

Exercise 2Basic

$5$ people each write a greeting card. The cards are put together, and each person takes one at random. In how many ways can this happen so that nobody gets the card they wrote?

Exercise 3Advanced

How many strings of length $5$ made of $0, 1, 2$ (the first digit may be $0$ ) contain no two adjacent $0$ s?

Exercise 4Challenge

There are $6$ circles in the plane; every two of them meet in two points, and no three pass through the same point. Into how many regions do they divide the plane?

In one sentence

Example: subsets with no two consecutive numbers

Stop 1 · Counting finite sets: derangements (Vol. 1)

Example: the recurrence for the derangement numbers Dₙ

Stop 2 · Linear recurrences and the characteristic equation (Vol. 5)

Example: how many strings of length n made of 0, 1, 2 have no two adjacent 0s?

Stop 3 · Iteration of a function (Vol. 2)

Guess, then prove

Take reciprocals: an arithmetic recursion

Stop 4 · Functional equations by recursion (Vol. 2)

Example: f: N⁺ → R, f(1) = 1, f(m + n) = f(m) + f(n) + mn. Find f(n)

Practice

Mistake Museum · Exhibits from this stop

The right recurrence with the wrong initial values

A case left out of the split

Stops on this line