Overview
A recurrence relation defines a sequence using earlier terms.
In counting problems, recurrences are useful when a large object can be built from smaller objects.
For example, the Fibonacci numbers satisfy
This type of recurrence appears naturally in tiling problems, stair climbing problems, and arrangements with restrictions.
The key idea is:
Count the final object by looking at how it could have ended.
Motivation
Suppose we want to tile a board of length using:
- Squares of length ,
- Dominoes of length .
Let
be the number of ways to tile a board of length .
Look at the last tile.
If the last tile is a square, then the first positions can be tiled in
ways.
If the last tile is a domino, then the first positions can be tiled in
ways.
Therefore,
This is the Fibonacci recurrence.
Base Cases
A recurrence is incomplete without base cases.
For the tiling example:
and
The value
means there is exactly one way to tile an empty board, use no tiles.
This convention often makes recurrence formulas work cleanly.
Using
we get
and so on.
Building a Recurrence
To build a recurrence, ask:
- What quantity should the sequence count?
- What is the last step or final piece?
- What smaller problem remains after removing it?
- What are the base cases?
The hardest part is choosing the right cases so that they do not overlap and do not miss anything.
Tiling With Squares and Dominoes
Example 1
How many ways are there to tile a board using squares and dominoes?
Let
be the number of tilings of a board.
As above,
The base cases are
Now compute:
So there are
tilings.
Stair-Climbing Problems
Recurrences also appear in stair problems.
Suppose a person can climb either step or steps at a time.
Let
be the number of ways to climb steps.
The final move is either:
- A -step move from step
- A -step move from step
So
Again, the Fibonacci recurrence appears.
Tiling With More Tile Sizes
If more tile sizes are allowed, the recurrence changes.
Example 2
How many ways are there to tile a board using tiles of lengths , , and ?
Let
be the number of tilings.
The last tile can have length , , or .
Therefore,
The base cases are
and
Avoiding Consecutive Objects
Recurrences can count arrangements with restrictions.
Example 3
How many binary strings of length have no two consecutive 's?
Let
be the number of valid strings of length .
Look at the end of the string.
If the string ends in , then the first digits can be any valid string. This gives
strings.
If the string ends in , then the previous digit must be . So the string ends in
The first digits can be any valid string. This gives
strings.
Therefore,
The base cases are
and
Recurrences With Several States
Sometimes one sequence is not enough.
If a problem has different ending types, it may be useful to define multiple states.
Example 4
How many length- strings made from and have no three consecutive 's?
Let
be the number of valid strings of length ending in .
Let
be the number ending in exactly one .
Let
be the number ending in exactly two consecutive 's.
Then
because we may add to any valid string.
Also,
because to end in exactly one , the previous character must be .
Finally,
because to end in exactly two consecutive 's, the previous string must have ended in exactly one .
The total number of valid strings is
This state method is often cleaner than trying to force one recurrence too early.
Solving Simple Linear Recurrences
Some recurrences can be solved exactly.
For example,
has a closed form, but in most contest counting problems we only need to compute terms up to a certain value.
For recurrences like
the solution is exponential.
If
then
If
with
then
The form of the recurrence reflects the growth of the counting process.
Worked Examples
Example 5
A rabbit can jump either , , or spaces at a time. How many ways can it reach space ?
Let
be the number of ways to reach space .
The last jump could have size , , or , so
Use base cases:
Then
So there are
ways.
Example 6
How many ways are there to tile a board using only dominoes of length and trominoes of length ?
Let
be the number of tilings of length .
The last tile has length or , so
We use
and
Then
So there are
tilings.
Key Contest Insight
Recurrence problems are usually solved by looking at the last step.
If the final choice leaves a smaller version of the same problem, a recurrence is likely useful.
The most important part is choosing cases that are:
- Complete
- Non-overlapping
- Easy to translate into smaller subproblems
Strategy Tips
- Define the sequence clearly
- Decide what counts
- Look at the last tile, last step, or last symbol
- Write the recurrence from smaller cases
- Choose base cases carefully
- Use when counting empty constructions
- If one sequence is not enough, introduce multiple states
- Compute terms patiently and check small cases
Common Pitfalls
- Forgetting base cases
- Using the wrong value for the empty case
- Double-counting overlapping cases
- Missing a possible final step
- Defining vaguely
- Trying to solve a recurrence before setting it up correctly
Practice Problems
| Status | Source | Problem Name | Difficulty | Tags | ||
|---|---|---|---|---|---|---|
Module Progress:
Join the Discord Community!
Stuck on a problem, or don't understand a module? Join the Discord and get help with your doubts while making more math friends.
