Combinatorics · step 9 of 13

Setting up & solving counting recurrences

Many counting problems are easiest to attack recursively: express the count for size n in terms of smaller sizes by conditioning on a first choice. The hard part is the setup — you must argue that the cases are exhaustive and disjoint — after which characteristic roots or iteration produce the closed form.

Practise setting up & solving counting recurrences free → All Combinatorics subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Condition on a first decisionWhat happens at the first position, or whether a particular element is included. This splits the count into cases.
Check the cases are disjoint and exhaustiveEvery object must fall into exactly one case, or the recurrence overcounts or misses.
Write the recurrence with base casesInclude enough bases to cover every value the recurrence cannot reach.
SolveUse characteristic roots for linear recurrences, or iterate and telescope for first-order ones.

Worked example

How many binary strings of length n contain no two consecutive 1s?

Condition on the first character. If it is 0, the rest is any valid string of length n−1: aₙ₋₁ ways.
If it is 1, the next must be 0, and the rest is any valid string of length n−2: aₙ₋₂ ways.
These cases are disjoint and cover everything, so aₙ = aₙ₋₁ + aₙ₋₂.
Bases: a₁ = 2 (strings 0, 1) and a₂ = 3 (00, 01, 10).

Answer. aₙ = aₙ₋₁ + aₙ₋₂ with a₁ = 2, a₂ = 3 — the Fibonacci numbers shifted, giving aₙ = Fₙ₊₂.

Where marks get dropped

These are the specific errors that cost credit on setting up & solving counting recurrences questions — QED's rubric penalises each of them separately.

Setting up cases that overlap, which counts some objects twice.
Giving one base case for a two-step recurrence, leaving it undetermined.
Not justifying that the cases are exhaustive. The recurrence is only as good as that argument.

Practise this until it is automatic

Unlimited fresh questions

QED generates new setting up & solving counting recurrences problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.

Setting up & solving counting recurrences — frequently asked questions

How do I know what to condition on?

Look for a decision that reduces the problem to the same problem on a smaller input — the first symbol, the largest element, or whether a specific item is used.

Why do Fibonacci numbers appear so often?

Because "one step or two steps" decompositions are ubiquitous: tilings, no-two-consecutive constraints, and staircase climbing all reduce to aₙ = aₙ₋₁ + aₙ₋₂.

When should I use generating functions instead?

When the recurrence is inhomogeneous or the structure is a convolution — generating functions turn convolution into multiplication and handle Catalan-style recurrences cleanly.

The rest of Combinatorics

Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make setting up & solving counting recurrences exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →