Counting using recursion (intro) - Discrete Math

SECTION 1

Historical Context & Motivation

Counting problems lie at the heart of combinatorics, yet many natural structures resist direct enumeration through closed-form expressions alone. The idea of defining a quantity in terms of smaller instances of itself — recursive counting — arose independently across several branches of mathematics and has since become one of the most versatile tools in the combinatorialist's repertoire. From the enumeration of partitions in number theory to the analysis of data structures in computer science, recursion provides a systematic strategy for attacking problems that would otherwise be intractable. The central insight is deceptively simple: if you can express the number of objects of size n in terms of counts at smaller sizes, you obtain a recurrence relation that can be solved iteratively, generating-functionally, or sometimes in closed form.

1202 • Fibonacci's Liber Abaci

Leonardo of Pisa introduces the rabbit-breeding problem, yielding the sequence F(n) = F(n−1) + F(n−2) — one of the earliest explicit recurrence relations in Western mathematics.

1655 • Pascal's Traité du Triangle Arithmétique

Blaise Pascal formalizes the recursive identity C(n, k) = C(n−1, k−1) + C(n−1, k) for binomial coefficients, establishing a foundational recursive counting tool.

1838 • Catalan Numbers Enumerated

Eugène Catalan systematically studies the number of ways to triangulate polygons, deriving a recurrence that now bears his name and appears in hundreds of combinatorial contexts.

1960s • Recursion in Computer Science

The formalization of recursive algorithms and dynamic programming by Bellman, Dijkstra, and others transforms recursive counting into a computational paradigm with practical applications in optimization and data structure analysis.

The motivating question behind recursive counting is straightforward: when a combinatorial object of size n naturally decomposes into smaller substructures, can we exploit that decomposition to derive a formula for the total count? This section introduces the conceptual machinery needed to answer that question rigorously.

SECTION 2

Core Principles & Definitions

Before diving into specific recurrences, it is essential to understand the logical architecture that supports recursive counting. Every recurrence relation rests on two pillars: a base case that anchors the recursion at a known value, and a recursive step that expresses the count for a larger instance in terms of counts for smaller instances. Together, these ensure that the recursion terminates and that every value in the sequence is well-defined. The following principles formalize this framework.

Structural Decomposition

Identify a decision point in the object's construction — often the first element, the last element, or a boundary — and classify all objects of size n by the choice made at that point.

Base Case(s)

Establish the count for the smallest meaningful instance(s). Without a base case, the recursion never terminates. Common base cases include a(0) = 1 (the empty object) or a(1) = 1.

Recurrence Relation

Write a(n) as a function of a(n−1), a(n−2), …, or more generally a sum or product of terms involving smaller indices, reflecting the structural decomposition.

Well-Ordering & Termination

Every recursive call must strictly decrease the problem size toward the base case. This is guaranteed when the argument set is a well-ordered subset of the natural numbers.

Solution Strategies

Once a recurrence is established, it may be solved by iteration (unrolling), by generating functions, by the Master Theorem (for divide-and-conquer forms), or by guessing and proving via induction.

✦

KEY TAKEAWAY

Think of recursive counting like assembling a Russian nesting doll. To determine how many distinct dolls of height n you can build, you first decide what the outermost shell looks like, then count the distinct dolls of height n − 1 that fit inside. The outermost decision is the recursive step; the tiny, innermost doll that you can describe directly is the base case.

SECTION 3

Visual Explanation — The Recursion Tree

A powerful way to visualize recursive counting is through a recursion tree. Consider the classic problem of counting the number of binary strings of length n that contain no two consecutive 1s. Let a(n) denote this count. A string of length n either starts with 0 (leaving a(n−1) valid continuations) or starts with 10 (leaving a(n−2) valid continuations, since the next bit after the 1 must be 0). This yields the Fibonacci-style recurrence a(n) = a(n−1) + a(n−2). The diagram below traces this decomposition for n = 5.

Each node represents a subproblem a(k). Branching left corresponds to the case where the string starts with 0 (reducing to a(k−1)), and branching right corresponds to starting with 10 (reducing to a(k−2)). Leaf nodes are base cases.

Notice how the tree reveals the overlapping subproblems inherent in this recursion — a(3) is computed twice, a(2) three times, and a(1) five times. This observation motivates memoization (caching previously computed values) or equivalently dynamic programming, which computes each value exactly once in a bottom-up pass. Even at this introductory stage, recognizing the tree structure of a recurrence helps you reason about both correctness and computational efficiency.

SECTION 4

Mathematical Framework

The mathematical backbone of recursive counting is the recurrence relation. Formally, a recurrence relation for a sequence {a(n)} is an equation that defines a(n) in terms of one or more preceding terms a(n−1), a(n−2), …, a(n−k), together with initial conditions that specify the first few values. Below are the key formulations encountered in introductory recursive counting.

GENERAL FIRST-ORDER LINEAR RECURRENCE

a(n) = c · a(n − 1) + f(n), n ≥ 1

Here c is a constant multiplier and f(n) is a known function. When f(n) = 0 the recurrence is homogeneous and solves to a(n) = a(0) · cⁿ.

SECOND-ORDER LINEAR RECURRENCE (FIBONACCI TYPE)

a(n) = a(n − 1) + a(n − 2), a(0) = p, a(1) = q

The characteristic equation r² = r + 1 has roots r = (1 ± √5)/2. The closed-form solution involves the golden ratio φ and its conjugate, yielding a(n) = Aφⁿ + Bψⁿ where A and B are determined by initial conditions.

PASCAL'S RECURSIVE IDENTITY

C(n, k) = C(n − 1, k − 1) + C(n − 1, k), C(n, 0) = C(n, n) = 1

This partitions the subsets of size k from an n-element set into those that contain a distinguished element (counted by C(n−1, k−1)) and those that do not (counted by C(n−1, k)).

CATALAN RECURRENCE

Cₙ = Σ (Cᵢ · Cₙ₋₁₋ᵢ), i = 0 to n − 1, C₀ = 1

The n-th Catalan number counts balanced parenthesizations, full binary trees with n + 1 leaves, and dozens of other structures. The closed form is Cₙ = C(2n, n) / (n + 1).

A common methodology for establishing a recurrence involves three steps: (1) identify a bijection between the combinatorial objects you wish to count and a recursively defined set; (2) decompose each object by making a first decision that partitions the set into disjoint cases; and (3) apply the sum and product rules of counting to express the total count in terms of counts at smaller sizes. This procedure — sometimes called the method of distinguished element — is the workhorse of recursive enumeration.

SECTION 5

Types of Recursive Counting Problems

Recursive counting problems can be classified by the form of their recurrence and the structure of the combinatorial objects being enumerated. Understanding this taxonomy helps you recognize which technique to apply when you encounter a new problem. The diagram below categorizes the most common types along two axes: the order of the recurrence (how many previous terms are referenced) and the linearity (whether the relation involves products of terms or only sums).

The vertical axis separates linear recurrences (bottom row), where a(n) depends on a sum of earlier terms, from nonlinear ones (top row), where products or variable coefficients appear. The horizontal axis increases the order or structural complexity.

Recurrence Type	Canonical Example	Counting Context	Closed Form
a(n) = 2 · a(n−1)	Binary strings of length n	Each position is 0 or 1	2ⁿ
a(n) = n · a(n−1)	Permutations of n elements	Choose first, permute rest	n!
a(n) = a(n−1) + a(n−2)	Strings without consecutive 1s	First bit 0 vs. first bits 10	Fibonacci-like
C(n,k) = C(n−1,k−1) + C(n−1,k)	Binomial coefficients	Include or exclude element	n! / (k!(n−k)!)
Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ	Catalan numbers	Left/right subtree split	C(2n,n)/(n+1)

Common recurrence types with their combinatorial origins and closed forms.

SECTION 6

Worked Example — Counting Domino Tilings

Let us apply recursive counting to a classic problem: in how many ways can a 2 × n board be tiled by 1 × 2 dominoes? Denote this count by T(n). We will set up the recurrence, verify it against small cases, and solve.

Tiling a 2 × n Board with Dominoes

1
Step 1 — Identify the First Decision

Focus on the leftmost column of the 2 × n board. It must be covered by at least one domino. There are exactly two options: (a) place a vertical domino covering both cells of column 1, leaving a 2 × (n−1) board; or (b) place two horizontal dominoes covering both rows of columns 1 and 2, leaving a 2 × (n−2) board.

Two disjoint cases identified.
2
Step 2 — Write the Recurrence

By the sum rule, the total number of tilings is the sum of the tilings from each case: T(n) = T(n−1) + T(n−2). This is valid for n ≥ 2.

T(n) = T(n − 1) + T(n − 2)
3
Step 3 — Establish Base Cases

T(0) = 1 (the empty board has exactly one tiling — the empty tiling). T(1) = 1 (a 2 × 1 board can only be tiled by a single vertical domino).

T(0) = 1, T(1) = 1
4
Step 4 — Compute Terms by Iteration

T(2) = T(1) + T(0) = 1 + 1 = 2. T(3) = T(2) + T(1) = 2 + 1 = 3. T(4) = T(3) + T(2) = 3 + 2 = 5. T(5) = T(4) + T(3) = 5 + 3 = 8. These match the Fibonacci numbers shifted by one index.

T(n) = F(n + 1), the (n+1)-th Fibonacci number
5
Step 5 — Verify Against Direct Counting

For n = 3, the three tilings are: (1) three vertical dominoes; (2) top-horizontal pair in columns 1–2, vertical in column 3; (3) vertical in column 1, top-horizontal pair in columns 2–3. This confirms T(3) = 3 ✓.

Recurrence verified. ✓

SECTION 7

Strengths, Limitations & Comparisons

Recursive counting is a remarkably general technique, but it is important to understand where it excels and where alternative approaches may be preferable. The following comparison highlights the trade-offs between recursive counting, direct (closed-form) counting, and generating-function methods.

Criterion	Recursive Counting	Direct / Closed-Form	Generating Functions
Ease of Discovery	High — decompose and count	Requires insight or bijection	Moderate — algebraic fluency
Computation for Large n	O(n) via iteration / DP	O(1) if formula exists	Coefficient extraction may be hard
Generality	Very high — works for most structures	Limited — not always available	Very high — systematic framework
Intuition / Interpretability	Excellent — mirrors object structure	Excellent when formula is simple	Abstract — less combinatorial feel
Asymptotics	Needs solving for growth rate	Immediate from formula	Powerful via singularity analysis

Comparison of three major counting paradigms.

✦

KEY TAKEAWAY

Recursive counting is the Swiss Army knife of combinatorics: it is rarely the most efficient tool for any single task, but it is almost always applicable. When a closed-form formula is elusive or a generating-function approach feels algebraically heavy, setting up a recurrence gives you an immediate computational method and often reveals structural insights that guide you toward more elegant solutions later.

SECTION 8

Connections to Advanced Theory

The introductory recurrences presented in this lesson serve as gateways to several sophisticated mathematical frameworks. Understanding these connections helps contextualize recursive counting within the broader landscape of combinatorics and theoretical computer science.

Introductory Concept	Advanced Generalization	Key Idea
Linear recurrence a(n) = Σcᵢa(n−i)	Characteristic polynomial & Jordan form	The recurrence's behavior is governed by the roots of a polynomial, enabling closed-form solutions via linear algebra.
Recursion trees with overlapping subproblems	Dynamic programming & optimal substructure	Memoization or tabulation reduces exponential recursive calls to polynomial time.
Catalan convolution Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ	Ordinary generating functions (OGFs)	The recurrence translates to a quadratic equation for the OGF C(x), yielding a closed form via the quadratic formula.
Divide-and-conquer recurrences	Master Theorem & Akra–Bazzi method	Recurrences of the form T(n) = aT(n/b) + f(n) have asymptotic solutions determined by the balance between splitting and combining work.
Counting lattice paths	Transfer matrix method & algebraic combinatorics	Matrix exponentiation computes a(n) in O(k³ log n) time for k-th order recurrences, enabling fast enumeration.

How introductory recursive counting concepts connect to advanced theory.

As you progress through combinatorics, you will find that nearly every advanced counting technique — from the symbolic method of Flajolet and Sedgewick to the transfer matrix method for counting paths in directed graphs — is, at its core, a sophisticated way of setting up and solving a recurrence. Mastering the introductory examples in this lesson therefore builds the foundation for all subsequent work in enumerative combinatorics.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why every recurrence relation requires at least one base case. What would happen if you attempted to compute a(5) using a(n) = a(n−1) + a(n−2) without specifying a(0) and a(1)?

Show answer

Without base cases, the recursion never terminates: computing a(5) requires a(4) and a(3), computing a(4) requires a(3) and a(2), and so on. Eventually you reach a(0) and a(−1), but a(−1) is undefined, and even a(0) has no assigned value without a base case. The recurrence provides only a relationship between terms, not their actual values. Base cases serve as the anchoring axioms from which all subsequent values can be uniquely determined, analogous to initial conditions in a differential equation.

Question 2: BASIC CALCULATION

A ternary string of length n is a string over the alphabet {0, 1, 2}. Let a(n) be the number of ternary strings of length n. Set up a first-order recurrence for a(n), state the base case, and compute a(4).

Show answer

The first character can be 0, 1, or 2, and the remaining n − 1 characters form an arbitrary ternary string. By the product rule, a(n) = 3 · a(n − 1) with base case a(0) = 1 (the empty string). Computing iteratively: a(1) = 3, a(2) = 9, a(3) = 27, a(4) = 81. The closed form is a(n) = 3ⁿ, which matches a(4) = 3⁴ = 81. This exemplifies a simple first-order linear homogeneous recurrence with constant coefficient c = 3.

Question 3: INTERMEDIATE

Let b(n) denote the number of binary strings of length n that do not contain the substring '11'. Set up a recurrence for b(n), state the base cases, and compute b(6).

Show answer

Consider the first bit. If it is 0, the remaining n − 1 bits can be any valid string, contributing b(n − 1). If it is 1, the second bit must be 0 (to avoid '11'), and the remaining n − 2 bits can be any valid string, contributing b(n − 2). Thus b(n) = b(n − 1) + b(n − 2). The base cases are b(0) = 1 (the empty string) and b(1) = 2 (strings '0' and '1'). Computing: b(2) = 3, b(3) = 5, b(4) = 8, b(5) = 13, b(6) = 21. This is the Fibonacci sequence shifted by two indices: b(n) = F(n + 2).

Question 4: APPLIED

A staircase has n steps. You can climb 1 or 2 steps at a time. Let S(n) be the number of distinct ways to reach the top. Derive a recurrence for S(n), and use it to find S(8). How does this problem relate to the domino tiling example?

Show answer

Your last move is either a 1-step (from step n−1) or a 2-step (from step n−2). These cases are mutually exclusive and exhaustive, so S(n) = S(n−1) + S(n−2), with S(0) = 1 (standing at the bottom is the unique way to 'reach' step 0) and S(1) = 1. The computation gives S(2) = 2, S(3) = 3, S(4) = 5, S(5) = 8, S(6) = 13, S(7) = 21, S(8) = 34. This is structurally identical to the 2 × n domino tiling problem: a bijection maps each staircase path to a tiling by replacing a 1-step with a vertical domino and a 2-step with a pair of horizontal dominoes. Both yield Fibonacci numbers.

Question 5: CRITICAL THINKING

The Catalan number Cₙ satisfies Cₙ = Σ (Cᵢ · Cₙ₋₁₋ᵢ) for i = 0 to n − 1, with C₀ = 1. Prove that this recurrence correctly counts the number of full binary trees with n + 1 leaves (i.e., n internal nodes). Then compute C₄.

Show answer

A full binary tree with n internal nodes has a root whose left subtree contains some number i of internal nodes and whose right subtree contains n − 1 − i internal nodes (since the root itself accounts for one). The left subtree is a full binary tree counted by Cᵢ, and the right subtree is counted by Cₙ₋₁₋ᵢ. Since the left and right subtrees are chosen independently, the product rule gives Cᵢ · Cₙ₋₁₋ᵢ configurations for a given split. Summing over all valid splits i = 0, 1, …, n − 1 and noting the cases are disjoint (they correspond to different values of i), the sum rule yields Cₙ = Σ Cᵢ · Cₙ₋₁₋ᵢ. Computing: C₀ = 1, C₁ = C₀·C₀ = 1, C₂ = C₀·C₁ + C₁·C₀ = 2, C₃ = C₀·C₂ + C₁·C₁ + C₂·C₀ = 5, C₄ = C₀·C₃ + C₁·C₂ + C₂·C₁ + C₃·C₀ = 5 + 2 + 2 + 5 = 14.

SUMMARY

Lesson Summary

Summary

Recursive counting transforms complex enumeration problems into manageable pieces by expressing the count of objects of size n in terms of counts at smaller sizes via a recurrence relation. The method requires two ingredients: one or more base cases that anchor the recursion and a recursive step derived from a structural decomposition of the objects being counted. We explored canonical examples including Fibonacci-type recurrences (binary strings without consecutive 1s, domino tilings, staircase climbing), Pascal's identity for binomial coefficients, and the Catalan recurrence for counting binary trees and balanced parenthesizations.

The key problem-solving strategy is the method of distinguished element: pick a feature of the object (often the first or last element), classify all objects by the choice at that feature, and apply the sum and product rules to reduce the count to smaller instances. Visualizing the recursion as a recursion tree reveals both the correctness of the decomposition and potential inefficiencies (overlapping subproblems) that motivate dynamic programming. As you advance, these elementary recurrences will serve as the foundation for generating functions, the transfer matrix method, and the symbolic method in analytic combinatorics.