The Central Idea
Let \(a_n\) denote the number of valid objects of size \(n\).
A recursive counting argument expresses \(a_n\) using earlier values such as
\[ a_{n-1},\qquad a_{n-2},\qquad \ldots \]rather than counting size-\(n\) objects from scratch.
A typical recurrence looks like
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]The exact recurrence depends on the structure of the problem.
What Makes a Count Recursive?
A counting problem is naturally recursive when a valid object can be reduced to a smaller valid object after removing a first part, last part, or local feature.
The key question is:
After I fix one structural choice, is the remaining problem a smaller version of the original one?
Recurrence Relations
A recurrence relation defines terms of a sequence using earlier terms.
For example,
\[ a_n=2a_{n-1} \]says that each size-\(n\) count is twice the previous count.
A recurrence does not determine a sequence by itself. We also need starting values.
Base Cases
The starting values of a recursive count are called base cases or initial conditions.
For
\[ a_n=a_{n-1}+a_{n-2}, \]two initial values are typically required, such as
\[ a_0=1,\qquad a_1=1. \]Once the recurrence and base cases are known, later terms can be generated.
Why Base Cases Matter
The recurrence
\[ a_n=a_{n-1}+a_{n-2} \]is satisfied by many different sequences.
The base cases identify which sequence corresponds to the counting problem.
First-Step Decomposition
One common recursive strategy is to classify valid objects by their first choice.
If the first choice has several possible forms and each form leaves a smaller instance, then
\[ \boxed{\text{count} = \text{count after first option} + \text{count after second option} +\cdots}. \]The first-step cases must be disjoint and exhaustive.
Last-Step Decomposition
We can also classify objects by how they end.
If every valid object has exactly one possible final structural type, removing that ending may leave a smaller valid object.
First-step and last-step decompositions are often mathematically equivalent.
Example: Tiling a \(1\times n\) Board
Suppose a \(1\times n\) board is tiled using:
- monomers of length \(1\);
- dominoes of length \(2\).
Let \(a_n\) be the number of tilings.
We classify a tiling by its final tile.
Case 1: Final Tile Has Length \(1\)
If the last tile is a monomer, removing it leaves a valid tiling of a board of length
\[ n-1. \]Therefore, this case contributes
\[ a_{n-1} \]tilings.
Case 2: Final Tile Has Length \(2\)
If the last tile is a domino, removing it leaves a valid tiling of a board of length
\[ n-2. \]Therefore, this case contributes
\[ a_{n-2} \]tilings.
The Tiling Recurrence
Every tiling ends in exactly one of the two tile types, so the cases are disjoint and exhaustive.
Therefore,
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]The natural base cases are
\[ a_0=1,\qquad a_1=1. \]The empty board has one tiling: use no tiles.
Why the Empty Object Often Counts as One
In combinatorics, a size-zero object often has one valid empty configuration.
For the tiling problem,
\[ a_0=1 \]makes the recurrence work naturally.
This does not mean the empty object contains one physical item. It means there is exactly one way to make no choices.
Generating the First Tiling Counts
Starting from
\[ a_0=1,\qquad a_1=1, \]we obtain
\[ a_2=2, \] \[ a_3=3, \] \[ a_4=5, \] \[ a_5=8. \]These are Fibonacci-type counts.
Recursive Counting and Fibonacci Numbers
The recurrence
\[ a_n=a_{n-1}+a_{n-2} \]appears whenever an object can end in one of two structural pieces that reduce its size by \(1\) or \(2\).
The precise indexing depends on the chosen base cases.
Example: Climbing Stairs
Suppose a person climbs a staircase using steps of size \(1\) or \(2\).
Let \(s_n\) be the number of ways to reach step \(n\).
The final move is either:
- a \(1\)-step move from step \(n-1\);
- a \(2\)-step move from step \(n-2\).
Therefore,
\[ \boxed{s_n=s_{n-1}+s_{n-2}}. \]Base Cases for the Staircase
A natural convention is
\[ s_0=1, \]because there is one way to make no moves and remain at the starting point.
Also,
\[ s_1=1. \]These values determine the later counts.
Example: Binary Strings without Consecutive Ones
Let \(b_n\) be the number of binary strings of length \(n\) with no occurrence of
\[ 11. \]We classify valid strings by how they end.
Strings Ending in \(0\)
If a valid length-\(n\) string ends in \(0\), then the first \(n-1\) positions may be any valid string of length \(n-1\).
This contributes
\[ b_{n-1} \]strings.
Strings Ending in \(1\)
If a valid string ends in \(1\), then the preceding position cannot also be \(1\).
For \(n\ge2\), such a string must end in
\[ 01. \]Removing that ending leaves any valid string of length \(n-2\).
This contributes
\[ b_{n-2} \]strings.
The Restricted-Binary Recurrence
Therefore,
\[ \boxed{b_n=b_{n-1}+b_{n-2}}. \]The base cases are
\[ b_0=1 \]and
\[ b_1=2, \]because the length-\(1\) valid strings are \(0\) and \(1\).
State-Based Recursive Counting
Sometimes the total count \(a_n\) does not contain enough information to describe how the next step behaves.
Then we introduce several state counts.
For example:
\[ x_n=\text{valid strings of length }n\text{ ending in }0, \] \[ y_n=\text{valid strings of length }n\text{ ending in }1. \]Example: Two-State Recurrence
For binary strings with no consecutive \(1\)s:
\[ x_n=x_{n-1}+y_{n-1}, \]because either valid ending may be followed by \(0\).
Also,
\[ y_n=x_{n-1}, \]because a \(1\) may follow only a string ending in \(0\).
Recovering the Total from States
The total number of valid strings is
\[ b_n=x_n+y_n. \]Since
\[ x_n=b_{n-1} \]and
\[ y_n=b_{n-2}, \]we recover
\[ b_n=b_{n-1}+b_{n-2}. \]When State Tracking Is Necessary
State tracking is useful when legal future choices depend on a small amount of information about the past.
Typical states record:
- the last symbol;
- whether a required feature has appeared;
- how many restricted objects have been used;
- the current remainder modulo \(m\);
- the remaining capacity of a category.
Example: Strings with No Two Consecutive \(A\)s
Suppose strings use the alphabet
\[ \{A,B,C\} \]and may not contain \(AA\).
Let
\[ a_n=\text{number of valid strings of length }n. \]A valid string either ends in \(B\) or \(C\), or ends in \(A\).
Ending in \(B\) or \(C\)
Any valid string of length \(n-1\) can be followed by \(B\) or \(C\).
Therefore, these two endings contribute
\[ 2a_{n-1}. \]Ending in \(A\)
If a valid string ends in \(A\), the previous symbol cannot be \(A\).
For \(n\ge2\), the final two symbols must be
\[ BA \]or
\[ CA. \]Removing those two symbols leaves any valid string of length \(n-2\).
This contributes
\[ 2a_{n-2}. \]The Three-Symbol Recurrence
Therefore,
\[ \boxed{a_n=2a_{n-1}+2a_{n-2}}. \]Suitable base cases are
\[ a_0=1,\qquad a_1=3. \]The recurrence follows from a disjoint decomposition by the final symbol.
Recursive Counting by First Object
Some problems are easier to decompose by the first object rather than the last.
For example, if a valid arrangement begins either with a type-\(A\) object or a type-\(B\) object, and removing that first object leaves a smaller valid arrangement, then the first choice can define the recurrence.
Recursive Counting by Distinguished Element
A family of subsets may be divided by whether it contains one distinguished element.
This can produce recurrences such as Pascal's identity:
\[ \boxed{ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} }. \]Why Pascal's Identity Is Recursive
Fix one distinguished element \(x\) in an \(n\)-element set.
A \(k\)-element subset either:
- does not contain \(x\), leaving a \(k\)-subset of \(n-1\) elements;
- does contain \(x\), leaving a \((k-1)\)-subset of \(n-1\) elements.
Therefore,
\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}. \]Recursive Definitions versus Closed Forms
A recurrence describes how to generate counts from earlier counts.
A closed form gives the \(n\)th count directly as a formula in \(n\).
Recursive counting does not require a closed form to be useful.
In many applications, the recurrence is the clearest description of the structure.
Example: Powers of Two Recursively
Let \(a_n\) be the number of binary strings of length \(n\).
Every valid length-\((n-1)\) string can be extended by either \(0\) or \(1\).
Therefore,
\[ a_n=2a_{n-1} \]with
\[ a_0=1. \]This recurrence generates
\[ a_n=2^n. \]Not Every Recurrence Is Fibonacci-Type
The recurrence depends on the number and sizes of the allowed structural extensions.
If an object can end with pieces of sizes \(1\), \(2\), or \(3\), then a recurrence such as
\[ a_n=a_{n-1}+a_{n-2}+a_{n-3} \]may arise.
Example: Steps of Size 1, 2, or 3
Suppose a staircase can be climbed using steps of size \(1\), \(2\), or \(3\).
Let \(t_n\) count the ways to reach step \(n\).
The final move came from step \(n-1\), \(n-2\), or \(n-3\).
Therefore,
\[ \boxed{t_n=t_{n-1}+t_{n-2}+t_{n-3}}. \]Choosing Base Cases Carefully
For a recurrence involving
\[ a_{n-1},\quad a_{n-2},\quad a_{n-3}, \]enough initial values must be supplied to begin the computation.
These might be
\[ a_0,\qquad a_1,\qquad a_2, \]depending on the problem.
Recursive Counting and Dynamic Programming
A recurrence gives a mathematical dependency structure.
If many recursive calls would repeatedly solve the same smaller problems, we can store earlier values and reuse them.
This computational strategy is commonly called dynamic programming.
Memoization and Tabulation
Two common computational implementations are:
- memoization: compute recursively and store results as needed;
- tabulation: compute smaller values first and build upward.
Both use the same recurrence relation.
Recursive Counting Does Not Mean Guessing
A valid recurrence must come from a complete structural decomposition.
The argument should explain why:
- every valid object appears in one recursive case;
- no valid object appears in more than one case;
- each case corresponds to the claimed smaller problem.
Checking a Recurrence with Small Cases
Before trusting a recurrence, compute a few small values directly.
Then verify that the recurrence reproduces them.
Small-case checking often reveals missing cases, overlapping cases, or incorrect base conditions.
Example: Checking the No-Consecutive-Ones Count
For length \(0\),
\[ b_0=1. \]For length \(1\),
\[ 0,\ 1, \]so
\[ b_1=2. \]For length \(2\), the valid strings are
\[ 00,\ 01,\ 10, \]so
\[ b_2=3. \]The recurrence gives
\[ b_2=b_1+b_0=2+1=3. \]Common Error: No Base Cases
Writing
\[ a_n=a_{n-1}+a_{n-2} \]without initial conditions does not determine the counting sequence.
Base cases are part of the recursive specification.
Common Error: Overlapping Recursive Cases
If one object can belong to two recursive cases, adding the case counts overcounts.
The decomposition must be disjoint.
Common Error: Missing Recursive Cases
If some valid objects do not fit any case, the recurrence undercounts.
The cases must cover every valid structure.
Common Error: Removing Too Much or Too Little
After fixing an ending of size \(2\), the remaining instance should have size
\[ n-2, \]not \(n-1\).
The reduction in the recurrence must match the size of the structural piece removed.
Common Error: Forgetting State Information
Sometimes a single total \(a_n\) does not contain enough information to decide how many extensions are legal.
In that case, introduce state-specific counts rather than forcing an invalid one-variable recurrence.
Common Error: Confusing a Recurrence with Its Solution
A recurrence such as
\[ a_n=2a_{n-1} \]describes a relationship between terms.
The formula
\[ a_n=2^n \]is a closed-form solution for a particular base case.
They are related but not identical statements.
A Reliable Procedure
- Define \(a_n\) precisely.
- Choose a structural feature such as the first or last piece.
- Split valid objects into disjoint, exhaustive cases.
- Reduce each case to a smaller instance.
- Translate the reduction into a recurrence relation.
- Supply enough base cases.
- Check several small values directly.
- Introduce state variables if the total count alone is insufficient.
- Compute recursively or tabulate values as needed.
Example: Full Recursive Workflow
Count length-\(n\) binary strings containing no consecutive \(1\)s.
Define
\[ b_n=\#\{\text{valid binary strings of length }n\}. \]A valid string ends either in \(0\) or in \(01\).
Ending in \(0\):
\[ b_{n-1}. \]Ending in \(01\):
\[ b_{n-2}. \]Therefore,
\[ \boxed{b_n=b_{n-1}+b_{n-2}}. \]Base cases:
\[ b_0=1,\qquad b_1=2. \]Thus,
\[ b_2=3,\qquad b_3=5,\qquad b_4=8. \]Practice 1: Monomer-Domino Tilings
Let \(a_n\) count tilings of a \(1\times n\) board using tiles of lengths \(1\) and \(2\). Write the recurrence and base cases.
Practice 2: Staircase
Let \(s_n\) count ways to climb \(n\) steps using moves of size \(1\) or \(2\). Find \(s_4\).
Practice 3: Binary Strings
Let \(b_n\) count binary strings of length \(n\) with no consecutive \(1\)s. Find \(b_5\).
Practice 4: Three Step Sizes
Suppose steps of size \(1\), \(2\), or \(3\) are allowed. Write a recurrence for the number \(t_n\) of ways to reach step \(n\).
Practice 5: Binary Strings without Consecutive Zeros
Let \(c_n\) count binary strings of length \(n\) with no occurrence of \(00\). Write a recurrence and suitable base cases.
Practice 6: Powers of Two
Let \(d_n\) count unrestricted binary strings of length \(n\). Write a recurrence and base case.
Practice 7: Pascal Recurrence
Write the recursive identity relating
\[ \binom{n}{k} \]to binomial coefficients with top index \(n-1\).
Practice 8: First Terms
A sequence satisfies
\[ a_n=a_{n-1}+a_{n-2}, \]with
\[ a_0=2,\qquad a_1=3. \]Find \(a_2,a_3,a_4\).
Practice 9: State Tracking
For binary strings with no consecutive \(1\)s, let \(x_n\) count valid strings ending in \(0\) and \(y_n\) count valid strings ending in \(1\). Write the two state recurrences.
Practice 10: Identify the Error
A student says that tilings with tiles of lengths \(1\) and \(2\) satisfy
\[ a_n=2a_{n-1} \]because there are two tile types. Explain why this reasoning is incorrect.
Practice Answers
Practice 1
Classify by the final tile:
\[ \boxed{a_n=a_{n-1}+a_{n-2}} \]with
\[ \boxed{a_0=1,\qquad a_1=1}. \]Practice 2
Using
\[ s_0=1,\qquad s_1=1, \]we obtain
\[ s_2=2,\qquad s_3=3,\qquad s_4=5. \]Therefore,
\[ \boxed{s_4=5}. \]Practice 3
Using
\[ b_0=1,\qquad b_1=2, \]we obtain
\[ b_2=3,\quad b_3=5,\quad b_4=8,\quad b_5=13. \]Therefore,
\[ \boxed{b_5=13}. \]Practice 4
The final move has size \(1\), \(2\), or \(3\):
\[ \boxed{t_n=t_{n-1}+t_{n-2}+t_{n-3}}. \]Practice 5
By symmetry with the no-consecutive-\(1\) problem,
\[ \boxed{c_n=c_{n-1}+c_{n-2}} \]with
\[ \boxed{c_0=1,\qquad c_1=2}. \]Practice 6
Each valid length-\((n-1)\) string has two extensions:
\[ \boxed{d_n=2d_{n-1}} \]with
\[ \boxed{d_0=1}. \]Practice 7
\[ \boxed{ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} }. \]Practice 8
\[ a_2=3+2=5, \] \[ a_3=5+3=8, \] \[ a_4=8+5=13. \]Therefore,
\[ \boxed{a_2=5,\qquad a_3=8,\qquad a_4=13}. \]Practice 9
A \(0\) may follow either valid ending:
\[ \boxed{x_n=x_{n-1}+y_{n-1}}. \]A \(1\) may follow only a string ending in \(0\):
\[ \boxed{y_n=x_{n-1}}. \]Practice 10
A length-\(1\) tile leaves a problem of size \(n-1\), while a length-\(2\) tile leaves a problem of size \(n-2\).
The two tile types do not both extend every size-\((n-1)\) tiling.
The correct recurrence is
\[ \boxed{a_n=a_{n-1}+a_{n-2}}. \]What to Remember
Recursive counting reduces a large counting problem to smaller versions of the same problem.
- Define the counting sequence clearly.
- Split by a structural first step, last step, or distinguished feature.
- Make the recursive cases disjoint and exhaustive.
- Match each case to the correct smaller problem.
- Supply enough base cases.
- Check small values directly.
- Introduce states when future choices depend on limited past information.
- Remember that a recurrence can be useful even without a closed form.
The central habit is to look for self-similarity: how can a valid object be reduced to a smaller valid object?
Where We Go Next
Recursive counting generates totals from smaller instances. Those totals are often written compactly using finite sums and products, especially when counts accumulate across many cases or multiply across many stages.
The next lesson, Finite Sums and Products, develops sigma and product notation as compact tools for expressing repeated finite counting operations.