For many students preparing for the British Mathematical Olympiad (BMO), combinatorics presents a specific hurdle: the temptation to count cases directly often leads to missed configurations or double-counting. Parity, invariants, the pigeonhole principle, and modular arithmetic are essential tools, but there is another technique that frequently unlocks complex counting problems: recurrence relations. A Hanlin course note published on 15 October 2026, originally in Chinese, states: ‘For BMO2 combinatorics, understanding the concept of recursive relations in the construction of counting methods is very helpful.’ That is not a rule about every BMO combinatorics problem. It is a preparation warning: when a count becomes complicated, the intended structure may be a recurrence, not a larger table of cases.
This article outlines a recurrence-first method for BMO combinatorics. The aim is not to memorise Fibonacci numbers or to force every counting problem into a recurrence. The aim is to recognise when a recurrence is the right tool, define the state precisely, justify the case split, and then solve or bound the resulting relation.
When Direct Counting Fails
In competition mathematics, direct counting usually means partitioning the set of objects into disjoint cases and summing their sizes. This works well when the objects have simple structure or when symmetry reduces the number of distinct cases. However, BMO-style problems often involve sequences, tilings, paths, subsets, or arrangements where local choices affect global validity. When you find yourself creating dozens of sub-cases that still do not cover all possibilities, or when the constraints depend on previous steps, direct enumeration becomes fragile.
At that point, shift perspective from ‘how many total objects?’ to ‘how does the number of valid objects grow as we extend the structure?’ The goal is not just to get a number. The goal is to define a sequence a_n that captures the problem’s essential state. A recurrence is useful when the same kind of choice appears at the boundary of every valid object.
Recurrences also sit beside other BMO tools rather than replacing them. For a wider toolkit covering parity, invariants, pigeonhole, and modular choices, see The BMO1 Number Theory and Combinatorics Toolkit: Parity, Invariants, Pigeonhole and the Right Modulus. That article helps you choose the right first tool. This article focuses on what to do when the chosen tool must track a growing structure.
Define the State Clearly
The first step in building a recurrence is defining the state variable n. What changes when you extend the object by one step? In tiling problems, n might be the length of the board. In path problems, it might be the number of steps taken. In subset problems, it might be the size of the set being considered. In string or colouring problems, n might be the number of positions filled so far.
Crucially, the state must contain enough information to determine future possibilities without remembering the entire history. If your definition of a_n is vague, such as ‘the number of ways to do something’, you will struggle to write a precise equation. Instead, define a_n as ‘the number of valid configurations of size n satisfying condition X’. This precision ensures that every term in your recurrence has a clear combinatorial meaning.
A good test is to ask whether two configurations with the same n but different internal histories should be counted separately in the next step. If not, your state may be too fine. If the future depends on hidden information, your state may be too coarse. Good state definition is the difference between a clean recurrence and an endless case chase.
Identify the First or Last Move
Once the state is defined, look at the boundary of the object. Consider the first element, such as the leftmost tile, or the last element, such as the final step in a path. By classifying the possible choices for this boundary element, you can break the problem into smaller instances.
For instance, if the first tile is vertical, the remaining space is a board of size n minus 1. If the first two tiles form a horizontal pair, the remaining space is a board of size n minus 2. This decomposition relies on the fact that the choice at the boundary determines the size of the remaining sub-problem. It is vital to ensure these cases are mutually exclusive and exhaustive. If a configuration does not fit into any case, your state definition was incomplete. If a configuration fits into multiple cases, your classification was not disjoint.
The boundary method is powerful because it turns a global question into a local decision. You do not need to understand every possible tiling, path, or subset at once. You only need to understand the first unavoidable choice and the smaller object that remains.
Write the Recurrence and Initial Values
Translate the case analysis into an algebraic equation. Using the tiling example above, if a_n is the number of ways to tile a 2-by-n board, then a_n = a_{n-1} + a_{n-2}. This is because every valid tiling starts either with a vertical domino, leaving a 2-by-(n-1) board, or with two horizontal dominoes, leaving a 2-by-(n-2) board. No other options exist.
To solve this recurrence, you need initial values. Calculate a_0 and a_1 manually. Often, a_0 = 1 represents the empty board having exactly one way to be tiled, namely doing nothing. This convention makes the recurrence work for small n. Always verify that the recurrence holds for the smallest non-trivial cases before proceeding.
The recurrence is not yet the final proof. It is the structural core. The final proof must include the state definition, the case split, the exhaustiveness argument, and the initial values. A recurrence without those pieces is just a guessed pattern.
Teaching Illustration: 2-by-n Domino Tilings
Note: This is a labelled teaching illustration, not an actual contest problem.
Consider the problem of tiling a 2-by-n rectangle with 1-by-2 dominoes, where each domino covers exactly two adjacent unit squares. Let a_n be the number of valid tilings. We build the recurrence by looking at the leftmost column.
Case 1: The leftmost column is covered by a single vertical domino. The remaining area is a 2-by-(n-1) rectangle, which can be tiled in a_{n-1} ways.
Case 2: The top-left square is covered by a horizontal domino extending into column 2. Then the bottom-left square cannot be covered by a vertical domino, because the top-left square is already occupied. Therefore the bottom-left square must also be covered by a horizontal domino extending into column 2. The leftmost two columns are now filled by two stacked horizontal dominoes. The remaining area is a 2-by-(n-2) rectangle, which can be tiled in a_{n-2} ways.
Are there other cases? No. The top-left square must be covered either by a vertical domino or by a horizontal domino. If it is covered by a horizontal domino, the bottom-left square is forced into the second case. Thus every tiling falls into exactly one of these two cases. Therefore a_n = a_{n-1} + a_{n-2} for n at least 2.
For initial values, a_0 = 1 by the empty-board convention, and a_1 = 1 because a 2-by-1 board has exactly one tiling by a vertical domino. Then a_2 = 2, a_3 = 3, a_4 = 5, and so on. This is the Fibonacci sequence shifted by one index. The illustration shows how a simple structural constraint forces a linear recurrence.
Check Exhaustiveness Rigorously
A common error in BMO proofs is assuming the recurrence covers all cases without proof. You must explicitly argue that every valid object falls into exactly one of the classified cases. In the tiling example, we argued that the leftmost part of the board must be covered by either a vertical domino or a pair of horizontal dominoes. Why? Because the height is 2. A vertical domino fills the height of the first column. Two horizontal dominoes fill the width of two columns and the height of two rows. There is no other way to cover the top-left cell without overlapping or leaving a hole.
If the problem were more complex, such as tiling a 3-by-n board, the state would need to track partial overlaps, requiring a system of recurrences rather than a single one. Always ask: ‘Is there any configuration I have not accounted for?’ If yes, refine your state definition. If no, write the exhaustiveness sentence explicitly in your solution.
This discipline is similar to the pigeonhole principle: before counting objects, define the boxes. For a dedicated treatment of that habit, see BMO Pigeonhole Principle: Define the Boxes Before Counting the Objects. Recurrence problems need the same care, but the boxes are replaced by state categories.
Diagnostic: Enlarging the State Space
Sometimes a simple recurrence such as a_n = f(a_{n-1}) fails because the future depends on more than just the immediate past. For example, if certain patterns are forbidden, knowing only the last tile may not be enough. You might need to know the last two tiles. In such cases, enlarge the state space.
Define b_n as the number of valid sequences ending in one specific pattern, and c_n as the number ending in another. Then write a system of equations linking b_n and c_n to b_{n-1}, c_{n-1}, and possibly earlier terms. This technique converts a complex dependency into a linear system. Recognising when to split the state is a key skill in advanced combinatorics. If your current recurrence yields incorrect counts for small n, suspect that your state is too coarse.
A practical diagnostic is to list all valid configurations for n = 1, 2, 3, 4 by hand. Then compare those counts with the values produced by your recurrence. If the first mismatch occurs early, the state definition is usually wrong. If the first mismatch occurs late, the case split may be incomplete.
Solve or Bound the Recurrence
Once the correct recurrence is established, the final step is to answer the original question. For BMO-style work, this might mean solving the recurrence explicitly using characteristic equations, proving bounds, or finding a closed form via induction. Sometimes the question asks for a_n mod m, in which case you can compute terms iteratively until a cycle appears. Other times, you need to compare growth rates or prove that one sequence dominates another.
Regardless of the solution method, the logical core of the argument remains the derivation of the recurrence itself. Ensure your write-up clearly defines the state, justifies the case breakdown, proves exhaustiveness, and then solves the resulting mathematical relation. If you need to strengthen an inductive claim after finding the recurrence, see BMO Induction: Choosing a Statement Strong Enough to Prove. A recurrence often supplies the inductive step, but only a carefully chosen statement makes the induction complete.
This structure provides clarity because a marker can follow your reasoning from state definition to final answer. It also protects you from the most common failure mode: a correct-looking formula that counts configurations you never explicitly considered.
Course-Fit and Resource Preparation
If you are struggling to transition from direct counting to recurrence-based reasoning, seek targeted feedback rather than more random practice. A diagnostic session can help identify whether your difficulty lies in state definition, case classification, algebraic manipulation, or proof writing. For independent study, review standard treatments of generating functions and linear recurrences. When preparing for consultation, bring specific examples where you attempted a recurrence but failed to match manual counts for small n. That allows an advisor to pinpoint exactly where your logic breaks down.
Remember that BMO combinatorics rewards complete arguments. A recurrence is not a shortcut around proof. It is a way of organising the proof. Define the state, choose the boundary, prove the cases are exhaustive, compute the initial values, and only then solve or bound the recurrence. That sequence turns a vague count into a defensible solution.
This is an independent BMO preparation guide and is not affiliated with UKMT.
Frequently Asked Questions
How do I know if a problem requires a recurrence?
If direct counting leads to many overlapping cases, or if the validity of a configuration depends heavily on its prefix or suffix, try defining a state based on size and analysing the boundary elements.
What if my recurrence gives wrong answers for small n?
This usually indicates that your state definition is insufficient. You may need to enlarge the state space by tracking additional features, such as the last few elements or specific patterns, leading to a system of recurrences.
Is solving the recurrence always necessary for BMO?
Not always. Sometimes proving properties of the sequence, such as divisibility or bounds, by induction on the recurrence is sufficient. However, deriving the recurrence correctly is the critical first step.