Recurrence Relations for Combinatorial Problems

The Essence of Recurrence Relations

At its core, a recurrence relation is a recipe for generating the terms of a sequence. It tells you how to find the n-th term, $a_n$, if you know the previous terms, like $a_{n-1}$, $a_{n-2}$, and so on. To get started, a recurrence also needs one or more initial conditions or base cases, which are the first few terms of the sequence given explicitly.

The general strategy to find a recurrence relation for a counting problem is to:

1. Define $a_n$ as the quantity you want to count for a problem of "size" $n$.
2. Analyze how a problem of size $n$ can be constructed from solutions to smaller problems (size $n-1$, $n-2$, etc.). This often involves considering the last object added, the first choice made, or partitioning the set of solutions into disjoint cases.
3. Use the sum and product rules to write an equation for $a_n$ in terms of earlier terms in the sequence.

Let's see this strategy in action with a classic example.

Example: Binary Strings with Restrictions

How many binary strings of length n are there that do not contain two consecutive 1s? Let's call this number $a_n$.

A direct counting approach is difficult because the placement of a 1 depends on its neighbors. Instead, let's build the solution for size n from smaller sizes. A valid string of length n must end in either a 0 or a 1.

• Case 1: The string ends in a 0.
  If the last digit is 0, the first $n-1$ digits can form any valid binary string of length $n-1$ without consecutive 1s. By definition, there are $a_{n-1}$ such strings.

• Case 2: The string ends in a 1.
  If the last digit is 1, the (n-1)-th digit must be 0 to avoid having "11". So the string must look like ...01. The first $n-2$ digits can form any valid string of length $n-2$. There are $a_{n-2}$ such strings.

Since these two cases are disjoint, we can use the sum rule to get our recurrence relation:
$a_n=a_{n-1}+a_{n-2}$
This is the famous Fibonacci recurrence! To complete it, we need base cases.

• For $n=1$, the valid strings are "0" and "1". So, $a_1=2$.
• For $n=2$, the valid strings are "00", "01", and "10". So, $a_2=3$.

The following resources walk through this exact reasoning. The video provides a nice visual walkthrough of the logic.

The Plane Division Problem

You mentioned being interested in the "pizza cutting problem." This is formally known as the plane division problem. The question is: what is the maximum number of regions, $L_n$, that a plane can be divided into by n straight lines?

To find the maximum, we must ensure that no two lines are parallel and no three lines intersect at the same point.

Let's start by exploring small cases, which is almost always a good idea in combinatorics.

From the image and some thought, we can tabulate the first few values:

• $L_0=1$ (the plane itself)
• $L_1=2$
• $L_2=4$
• $L_3=7$
• If you draw it carefully, you'll find $L_4=11$.

The sequence is $1,2,4,7,11,\dots$. The differences between consecutive terms are $1,2,3,4,\dots$. This pattern strongly suggests a recurrence. Let's formalize it.

Suppose we have already drawn $n-1$ lines, creating $L_{n-1}$ regions. Now, we add the n-th line. To maximize the new regions created, this new line must intersect all n-1 of the previous lines, and it must do so at distinct points.

When the n-th line crosses the n-1 existing lines, it gets divided into n segments. Each of these n segments cuts through one of the old regions, splitting it into two. This adds exactly n new regions to our total.

Therefore, the recurrence relation is:
$L_n=L_{n-1}+n$
with the base case $L_0=1$.

The following resources provide a great walkthrough and formal derivation of this result.

Generalizing to 3D: The Space Division Problem

For a challenge worthy of Olympiad preparation, let's extend this to three dimensions. What is the maximum number of regions, $P_n$, that 3D space can be divided into by n planes?

The logic is analogous. Let's assume we have already placed $n-1$ planes, creating $P_{n-1}$ regions. We now add the n-th plane. To maximize the new regions, this new plane must intersect all n-1 previous planes.

What does the intersection look like? The intersection of our new n-th plane with the n-1 old planes is a set of n-1 lines on the new plane. To maximize everything, these n-1 lines must also be in "general position" (no two parallel, no three concurrent).

These n-1 lines on the new plane divide it into $L_{n-1}$ planar regions (our previous problem!). Each of these planar regions on the new plane acts as a blade, slicing through one of the existing 3D regions and dividing it into two.

This means that adding the n-th plane creates $L_{n-1}$ new 3D regions. Thus, the recurrence relation is:
$P_n=P_{n-1}+L_{n-1}$
with the base case $P_0=1$. Notice how we've defined the solution to a 3D problem in terms of the solution to a 2D problem!

Practice Problems

Now it's your turn to formulate recurrences. For each problem, define your sequence $a_n$ and find the relation and its base cases. You don't need to solve for a closed-form solution.

1. The Tower of Hanoi: You have three pegs and n disks of different sizes. Initially, all disks are on the first peg in order of size, smallest on top. You can move one disk at a time, and you can never place a larger disk on top of a smaller one. Let $H_n$ be the minimum number of moves required to transfer all n disks from the first peg to the third peg. Find a recurrence for $H_n$.

2. Ternary Numbers without Double Zeros: Let $a_n$ be the number of n-digit ternary strings (using digits 0, 1, 2) that do not contain "00" as a substring. Find a recurrence for $a_n$. (Hint: Condition on the last digit. If the last digit is 0, what must the (n-1)-th digit be?)

3. Ordered Sums of Odd Integers: For $n\ge 1$, let $a_n$ be the number of ways to write n as an ordered sum of odd positive integers. For example, $a_4=3$ because $4=3+1$, $4=1+3$, and $4=1+1+1+1$. Find a recurrence for $a_n$. (Hint: Consider the last number in the sum. What if it's 1? What if it's greater than 1?)

These problems will help you solidify the core skill of recursive thinking. The logic you develop here is fundamental to a huge portion of advanced combinatorics.

Conclusion

Today, we've taken our first major step into the world of enumerative combinatorics by learning how to frame problems recursively. The key takeaway is the strategy of decomposition: breaking a large problem into smaller, self-similar instances. We saw this in action with restricted binary strings and, most notably, in the plane and space division problems. By considering the effect of adding just one more element—one more digit, one more line, one more plane—we were able to define the solution for size n in terms of solutions for smaller sizes.

We have focused exclusively on formulating these relations. In our next lesson, we will learn how to solve them. Specifically, we'll cover the characteristic equation method, a powerful algebraic technique for finding a closed-form solution (like $L_n=\frac{n^2+n+2}{2}$) directly from a recurrence relation like $L_n=L_{n-1}+n$. This will complete the journey from a recursive definition to an explicit formula.