Combinatorics • Topic 14

Recursion

Recursion is the process of defining a sequence or function in terms of itself. It is the heart of induction and dynamic programming.

Building a Recursion

To solve a counting problem recursively:

Define the state: Let $a_{n}$ be the number of ways to do the task for size $n$ .
Find the relation: Express $a_{n}$ using previous terms ( $a_{n - 1}, a_{n - 2}$ , etc.) by considering the last step.
Base Cases: Calculate small values ( $a_{1}, a_{2}$ ) manually.

Example (Tiling a 2xn Board)

How many ways to tile a

2 \times n

board with

2 \times 1

dominoes?

Proof. Let $t_{n}$ be the number of ways. Consider the rightmost column(s):

Place one vertical domino: Remaining space is $2 \times (n - 1)$ , so $t_{n - 1}$ ways.
Place two horizontal dominoes stacked: Remaining space is $2 \times (n - 2)$ , so $t_{n - 2}$ ways.

Relation:

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

. Base cases:

t_{1} = 1, t_{2} = 2

. This is the Fibonacci sequence. ∎

To move

n

disks from peg A to peg C:

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

Solution:

H_{n} = 2^{n} - 1

Exercise (Problem 1)

Find a recurrence for the number of binary strings of length

n

that do not contain consecutive zeros.

Exercise (Problem 2)

A "derangement" is a permutation where no element appears in its original position. Derive the recurrence

D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})

Exercise (Problem 3)

Let

a_{n}

be the number of subsets of

{1, \dots, n}

that contain no consecutive integers. Find

a_{n}