3. Induction and Recursion

This chapter is about infinite families of objects that are each described by finite rules: sequences, sums, recursively built sets and data structures, and the programs that process them. Its main proof tool is mathematical induction, which turns "it holds at the start, and each step preserves it" into "it holds for every case". The same pattern explains why recursive functions return correct answers, why loops terminate, and how running times are counted.

<a id="31-sequences-and-summations"></a>

3.1 Sequences and Summations

Sequences are ordered lists of values indexed by integers, and summations add up their terms. This subchapter introduces the notation, the sequences and sums that appear most often in algorithm analysis, and techniques for reducing a sum to a closed formula.

Sequences

Why. Many quantities in computing come in an indexed series: the running time for inputs of size 1, 2, 3, …, the capacity of a growing buffer after each resize, the balance of an account month by month. We need a uniform way to name the n-th value and to describe the whole series by a finite rule.

What. A sequence is a function from a set of consecutive integers (usually ℕ = {0, 1, 2, …} or ℤ⁺ = {1, 2, 3, …}) to a set S (2.2). The image of n is written a_n and called the n-th term. The whole sequence is written (a_n) or {a_n}, or listed as a_0, a_1, a_2, ….

A finite sequence a_1, a_2, …, a_n is also called a string or word when its terms come from an alphabet. Its length is n, and the string of length 0 is the empty string λ (used heavily in Chapter 13).

There are two standard ways to specify a sequence:

Specification	Form	Example	Computing a_n
Explicit (closed form)	a_n = f(n)	a_n = 2n + 1	Directly, in one evaluation
Recursive	Initial term(s) plus a rule using earlier terms	a_0 = 1, a_n = a_{n−1} + 2	Step by step from a_0

Both describe the same sequence 1, 3, 5, 7, …. Converting a recursive specification into an explicit one is called solving the recurrence (Chapter 6).

Monotonicity. A sequence is increasing if a_n < a_{n+1} for all n, and non-decreasing if a_n ≤ a_{n+1}. Decreasing and non-increasing are defined symmetrically. The running time of most algorithms, as a function of input size, is non-decreasing.

Finitely many terms never determine a sequence. "Find the next term" puzzles have no unique answer. The sequence 1, 2, 4, 8, 16 looks like 2^n, but it is also the start of the number of regions formed by joining n points on a circle with all possible chords, whose sixth term is 31, not 32. The first terms suggest a formula. Only a proof establishes it.

   n points on a circle        1    2    3    4    5    6
   regions (all chords)        1    2    4    8   16   31   <- not 32
   2^(n-1)                     1    2    4    8   16   32

Analogy. An explicit formula is a random-access array: ask for index 1000 and get the answer immediately. A recursive definition is a linked list: to reach item 1000, you walk through the 999 before it.

from itertools import islice
from math import comb

def explicit(n):
    return 2 * n + 1                           # a_n = 2n + 1

def recursive():
    a = 1                                      # a_0 = 1
    while True:                                # an infinite sequence as a lazy generator
        yield a
        a = a + 2                              # a_n = a_{n-1} + 2

print([explicit(n) for n in range(6)])         # [1, 3, 5, 7, 9, 11]
print(list(islice(recursive(), 6)))            # [1, 3, 5, 7, 9, 11]

def circle_regions(n):
    return comb(n, 4) + comb(n, 2) + 1         # closed form for the chord-regions sequence

print([circle_regions(n) for n in range(1, 8)])    # [1, 2, 4, 8, 16, 31, 57]

Key takeaways

• A sequence is a function whose domain is a set of consecutive integers. a_n is its n-th term.
• Sequences are specified explicitly (a_n = f(n)) or recursively (initial terms plus a rule).
• A finite sequence over an alphabet is a string. The empty string λ has length 0.
• No finite list of terms determines a sequence. A guessed formula must be proved.

Practice

1. (Beginner) Give an explicit formula and a recursive definition for each sequence: 3, 7, 11, 15, … and 2, 6, 18, 54, ….
2. (Intermediate) Find two different explicit formulas that both begin 1, 2, 4 but differ at the fourth term. Then list the first five terms of a_n = n² − n + 1 and of b_0 = 1, b_n = b_{n−1} + 2(n − 1) and explain why they agree.
3. (Interview) A log-processing service must expose "the n-th event" for an unbounded stream. When would you model it as a generator (recursive style) and when as an indexable function (explicit style)? Hint: compare the cost of reaching term n, the memory used, and whether terms can be recomputed independently.

Arithmetic and Geometric Progressions

Why. Two growth patterns dominate computing. Adding a fixed amount at each step (one more element, one more second) gives linear growth. Multiplying by a fixed factor (doubling a buffer, halving a search range, compounding interest) gives exponential growth. These patterns are the arithmetic and geometric progressions.

What.

	Arithmetic progression	Geometric progression
Rule	Constant difference d between terms	Constant ratio r between terms
Recursive form	a_0 = a, a_n = a_{n−1} + d	a_0 = a, a_n = r · a_{n−1}
Explicit form	a_n = a + n·d	a_n = a · r^n
Example	5, 8, 11, 14, … (a = 5, d = 3)	3, 6, 12, 24, … (a = 3, r = 2)
Growth	Linear in n	Exponential if |r| > 1, decays to 0 if |r| < 1
Test	a_{n+1} − a_n is constant	a_{n+1} / a_n is constant (terms non-zero)
In computing	Array addresses, evenly spaced timestamps	Buffer doubling, exponential backoff, halving in binary search

The two families are linked by logarithms and exponentials: if (a_n) is arithmetic, then (2^{a_n}) is geometric, and if (b_n) is geometric with positive terms, then (log b_n) is arithmetic. This is why exponential growth looks like a straight line on a log-scale plot.

How. To identify a progression, compute consecutive differences and ratios. To find the n-th term, read off a (the term at index 0) and d or r, then use the explicit form. Watch the indexing: if the sequence starts at a_1, the formulas become a_n = a_1 + (n − 1)d and a_n = a_1 · r^{n−1}.

 Arithmetic: address of A[i] = base + i * size      Geometric: dynamic array capacity after resizes
   base=1000, size=4                                  1 -> 2 -> 4 -> 8 -> 16 -> 32
   A[0]  A[1]  A[2]  A[3]                             ×2   ×2   ×2   ×2    ×2
   1000  1004  1008  1012   (d = 4)                   reaching capacity N takes only ~log2(N) resizes

def classify(seq):
    diffs = {b - a for a, b in zip(seq, seq[1:])}
    ratios = {b / a for a, b in zip(seq, seq[1:]) if a != 0}
    if len(diffs) == 1:
        return f"arithmetic, d = {diffs.pop()}"
    if len(ratios) == 1 and 0 not in seq:
        return f"geometric, r = {ratios.pop()}"
    return "neither"

print(classify([5, 8, 11, 14]))       # arithmetic, d = 3
print(classify([3, 6, 12, 24]))       # geometric, r = 2.0
print(classify([1, 4, 9, 16]))        # neither  (squares: differences 3, 5, 7 grow)

# Exponential backoff: retry delays form a geometric progression, capped at a maximum
base, factor, cap = 0.1, 2, 5.0
delays = [min(base * factor**k, cap) for k in range(8)]
print(delays)                         # [0.1, 0.2, 0.4, 0.8, 1.6, 3.2, 5.0, 5.0]

Key takeaways

• Arithmetic: constant difference, a_n = a + nd, linear growth.
• Geometric: constant ratio, a_n = a·r^n, exponential growth or decay.
• Check the starting index. Starting at a_1 shifts the exponent or multiplier to n − 1.
• Logarithms turn geometric progressions into arithmetic ones, and exponentials do the reverse.

Practice

1. (Beginner) Classify each sequence and give its 10th term (counting the first listed term as a_1): 7, 4, 1, −2, … and 81, 27, 9, 3, ….
2. (Intermediate) A geometric progression has a_2 = 12 and a_5 = 96. Find a_0 and r. Can an arithmetic progression with d ≠ 0 also be geometric?
3. (Interview) Why do dynamic arrays (Python list, Java ArrayList, C++ std::vector) grow capacity by a constant factor instead of a constant amount? Hint: count the total number of element copies needed to reach n elements under each policy. The closed forms in the next topics will make this precise.

Summation Notation

Why. Analysing algorithms constantly requires adding up long lists of terms: the work done by every iteration of a loop, the cost of every level of a recursion. Writing a_1 + a_2 + ⋯ + a_n is clumsy and ambiguous about the pattern. Summation notation states exactly which terms are added.

What. The sum of a_m, a_{m+1}, …, a_n is written

     n
     Σ   a_i        written inline as  Σ_{i=m}^{n} a_i
    i=m

• i is the index of summation. It is a bound variable (1.2): renaming it to j or k changes nothing.
• m is the lower limit and n the upper limit. The sum has n − m + 1 terms.
• If n < m, the sum is empty and equals 0, the identity for addition.
• Σ_{x ∈ S} f(x) sums f over all elements of a finite set S.
• Products use the same notation with Π. An empty product equals 1, which is why 0! = 1 and x^0 = 1.

A summation is exactly a for loop with an accumulator:

def summation(a, m, n):
    total = 0                      # empty sum = 0
    for i in range(m, n + 1):      # i runs from m to n inclusive: n - m + 1 terms
        total += a(i)
    return total

print(summation(lambda i: i * i, 1, 4))     # 30 = 1 + 4 + 9 + 16
print(summation(lambda i: i * i, 5, 4))     # 0   (empty sum)
print(sum(i * i for i in range(1, 5)))      # 30   (the idiomatic one-liner)

Manipulation rules.

Rule	Identity
Constant factor	Σ c·a_i = c · Σ a_i
Sum of sums	Σ (a_i + b_i) = Σ a_i + Σ b_i
Constant term	Σ_{i=m}^{n} c = (n − m + 1)·c
Splitting the range	Σ_{i=m}^{n} a_i = Σ_{i=m}^{k} a_i + Σ_{i=k+1}^{n} a_i for m ≤ k < n
Index shift (j = i + s)	Σ_{i=m}^{n} a_i = Σ_{j=m+s}^{n+s} a_{j−s}
Swapping a double sum	Σ_{i=1}^{p} Σ_{j=1}^{q} a_{ij} = Σ_{j=1}^{q} Σ_{i=1}^{p} a_{ij}

The first two rules together are called linearity. Common mistakes: Σ a_i·b_i ≠ (Σ a_i)(Σ b_i), and Σ_{i=1}^{n} c = n·c, not c.

Nested loops are double sums. The number of times the body runs is the sum over the outer index of the number of inner iterations. When the inner range depends on the outer index, the summation diagram is a triangle, and swapping the order of summation means reading it by columns instead of rows.

for i in 1..4:              i\j  1  2  3  4
    for j in 1..i:           1   *                  rows:    Σ_{i=1}^{4} i = 1+2+3+4 = 10
        body()               2   *  *
                             3   *  *  *            columns: Σ_{j=1}^{4} (4 − j + 1) = 4+3+2+1 = 10
                             4   *  *  *  *

n = 4
count = sum(1 for i in range(1, n + 1) for j in range(1, i + 1))
print(count)                                         # 10
print(sum(i for i in range(1, n + 1)))               # 10  (by rows)
print(sum(n - j + 1 for j in range(1, n + 1)))       # 10  (by columns)

Key takeaways

• Σ_{i=m}^{n} a_i has n − m + 1 terms. The index is a bound variable.
• An empty sum is 0 and an empty product is 1.
• Linearity, range splitting, and index shifting are the core manipulation rules.
• Nested loops correspond to double sums, and the order of summation may be swapped.

Practice

1. (Beginner) Evaluate Σ_{i=1}^{5} (2i − 1), Σ_{k=0}^{3} 2^k, and Π_{j=1}^{4} j.
2. (Intermediate) Rewrite Σ_{i=3}^{n+2} (i − 2)² so that the index starts at 1. Then use linearity to express Σ_{i=1}^{n} (3i + 2) in terms of Σ i and n.
3. (Interview) Exactly how many times does body() run in for i in range(n): for j in range(i + 1, n): body(), and what common task does this loop perform? Hint: write the count as a double sum and reverse the order of summation, or count unordered pairs directly.

Closed Forms of Common Sums

Why. A sum like Σ_{i=1}^{n} i hides how big it is. A closed form, such as n(n + 1)/2, is a formula with a fixed number of operations regardless of n. It can be evaluated in constant time and immediately shows the growth rate (Chapter 10), which is usually what an analysis needs.

What.

Sum	Closed form	Growth
Σ_{i=1}^{n} 1	n	Θ(n)
Σ_{i=1}^{n} i	n(n + 1) / 2	Θ(n²)
Σ_{i=1}^{n} i²	n(n + 1)(2n + 1) / 6	Θ(n³)
Σ_{i=1}^{n} i³	(n(n + 1) / 2)²	Θ(n⁴)
Σ_{i=0}^{n} r^i, r ≠ 1	(r^{n+1} − 1) / (r − 1)	Θ(r^n) if r > 1, Θ(1) if 0 < r < 1
Σ_{i=0}^{∞} r^i, |r| < 1	1 / (1 − r)	constant
Σ_{i=1}^{n} 1/i (harmonic H_n)	no closed form; H_n ≈ ln n + 0.5772	Θ(log n)

Rule of thumb: Σ_{i=1}^{n} i^k is Θ(n^{k+1}), just as the integral of x^k is x^{k+1}/(k+1).

How: the arithmetic series (Gauss's pairing). Write the sum forwards and backwards and add the two lines column by column:

  S =   1   +   2   + ... + (n-1) +   n
  S =   n   + (n-1) + ... +   2   +   1
 ---------------------------------------
 2S = (n+1) + (n+1) + ... + (n+1) + (n+1)   = n(n+1)      so   S = n(n+1)/2

More generally, any arithmetic series equals the number of terms times the average of the first and last terms.

How: the geometric series (shift and subtract). Multiply by r and subtract. Everything except two terms cancels:

   S = 1 + r + r² + ... + r^n
  rS =     r + r² + ... + r^n + r^{n+1}
 -------------------------------------
  rS − S = r^{n+1} − 1               so   S = (r^{n+1} − 1)/(r − 1)

For r = 2 this gives 1 + 2 + 4 + ⋯ + 2^n = 2^{n+1} − 1: each power of two is one more than the sum of all smaller powers. This explains why a doubling dynamic array does O(n) total copying work: the copies form a geometric series dominated by its last term.

Analogy. A geometric series with r = 1/2 is walking half the remaining distance to a wall with every step. You never pass the wall, so the total distance converges to 1.

from fractions import Fraction

n = 100
assert sum(range(1, n + 1)) == n * (n + 1) // 2
assert sum(i**2 for i in range(1, n + 1)) == n * (n + 1) * (2 * n + 1) // 6
assert sum(i**3 for i in range(1, n + 1)) == (n * (n + 1) // 2) ** 2
assert sum(3**i for i in range(n + 1)) == (3**(n + 1) - 1) // (3 - 1)

# Partial sums of 1/2 + 1/4 + 1/8 + ... approach 1 but never reach it
print([str(sum(Fraction(1, 2**i) for i in range(1, k + 1))) for k in range(1, 6)])
# ['1/2', '3/4', '7/8', '15/16', '31/32']

# Dynamic array: copies made when doubling capacity from 1 up to n = 1024
copies = sum(2**i for i in range(10))      # 1 + 2 + ... + 512 elements copied
print(copies)                              # 1023 < 2 * 1024, so O(1) amortized per append

Key takeaways

• Closed forms replace an n-term sum by a constant-size formula that reveals the growth rate.
• Σ i = n(n + 1)/2 (pairing) and Σ r^i = (r^{n+1} − 1)/(r − 1) (shift and subtract) are the two most used.
• A geometric series with r > 1 is dominated by its largest term. With |r| < 1 it is bounded by a constant.
• The harmonic sum H_n has no closed form but grows like ln n.

Practice

1. (Beginner) Compute 1 + 2 + ⋯ + 200 and 1 + 3 + 9 + ⋯ + 3^6 using closed forms.
2. (Intermediate) Find a closed form for the sum of the first n odd numbers 1 + 3 + ⋯ + (2n − 1) and for Σ_{i=1}^{n} (3i + 2). Verify each for n = 4.
3. (Interview) An algorithm processes an input of size n, then recurses on an input of size n/2, then n/4, and so on down to 1, doing linear work at each level. What is the total work? How would the answer change if each level spawned two halves instead of one? Hint: write the work per level as a series. One case is geometric with r = 1/2, the other has log₂ n equal terms.

Telescoping Sums

Why. Some sums have no obvious pattern, but each term can be written as a difference of consecutive values of another sequence. Then almost everything cancels, leaving only the first and last values, like a collapsible telescope folding down to its two ends.

What. For any sequence (a_n),

  Σ_{i=1}^{n} (a_i − a_{i−1}) = a_n − a_0

because the sum is (a_1 − a_0) + (a_2 − a_1) + ⋯ + (a_n − a_{n−1}) and every intermediate term appears once with + and once with −. This is the discrete analogue of the fundamental theorem of calculus: summing the differences of a sequence recovers the change in the sequence.

How. Find a sequence a_i such that the term you are summing equals a_i − a_{i−1} (or a_{i+1} − a_i). Partial fractions and factorial identities are the usual sources.

Example 1. Σ_{i=1}^{n} 1/(i(i + 1)). Partial fractions give 1/(i(i + 1)) = 1/i − 1/(i + 1).

  (1/1 − 1/2) + (1/2 − 1/3) + (1/3 − 1/4) + ... + (1/n − 1/(n+1))
        ╰───────╯      ╰───────╯      ╰──── ... ───╯
         cancel         cancel            cancel
  = 1 − 1/(n+1) = n/(n+1)

Example 2. Σ_{i=1}^{n} i·i!. Since (i + 1)! − i! = i!·(i + 1 − 1) = i·i!, the sum telescopes to (n + 1)! − 1! = (n + 1)! − 1.

Example 3: deriving Σ i without guessing. Since i² − (i − 1)² = 2i − 1, summing from 1 to n gives n² − 0² = 2·Σ i − n, so Σ i = (n² + n)/2. The same trick with cubes, i³ − (i − 1)³ = 3i² − 3i + 1, derives the formula for Σ i².

In computing. The potential method of amortized analysis is a telescoping argument. If an operation costs c_i and changes a potential function from Φ_{i−1} to Φ_i, then the total of c_i + (Φ_i − Φ_{i−1}) over all operations equals the total actual cost plus Φ_n − Φ_0. The potential terms collapse.

from fractions import Fraction
from math import factorial

n = 10
lhs = sum(Fraction(1, i * (i + 1)) for i in range(1, n + 1))
print(lhs, Fraction(n, n + 1))                       # 10/11 10/11

assert sum(i * factorial(i) for i in range(1, n + 1)) == factorial(n + 1) - 1

# Generic check: summing differences of any sequence recovers last − first
a = [5, 2, 9, 9, 4, 11]
diffs = [a[i] - a[i - 1] for i in range(1, len(a))]
print(sum(diffs), a[-1] - a[0])                      # 6 6

Key takeaways

• Σ_{i=1}^{n} (a_i − a_{i−1}) = a_n − a_0: all intermediate terms cancel.
• The skill is rewriting a term as a difference of consecutive values, often via partial fractions.
• Telescoping can derive closed forms such as Σ i from scratch.
• Amortized analysis with a potential function relies on a telescoping sum.

Practice

1. (Beginner) Evaluate Σ_{i=1}^{99} (√(i + 1) − √i) and Σ_{k=1}^{n} (2^k − 2^{k−1}).
2. (Intermediate) Use 1/(i(i + 2)) = (1/2)(1/i − 1/(i + 2)) to find a closed form for Σ_{i=1}^{n} 1/(i(i + 2)). Why do two terms survive at each end instead of one?
3. (Interview) Explain why the total actual cost of n operations is at most the sum of their amortized costs ĉ_i = c_i + Φ_i − Φ_{i−1}, provided the potential satisfies Φ_n ≥ Φ_0. Hint: sum the definition of ĉ_i over all i and let the potential terms telescope.

<a id="32-mathematical-induction"></a>

3.2 Mathematical Induction

Induction proves statements of the form "for every integer n ≥ n₀, P(n)" by proving finitely many things. This subchapter covers the standard form, the strong form, their common foundation in the well-ordering principle, and the mistakes that make induction proofs fail.

Weak Induction

Why. Testing Σ_{i=1}^{n} i = n(n + 1)/2 for a million values of n still leaves infinitely many unchecked. A direct proof needs a clever idea for each new formula. Induction gives a general method: instead of proving P(n) for each n separately, prove that the property starts and that it propagates.

Analogy. Picture an infinite row of dominoes. If the first domino falls, and every falling domino knocks over the next one, then every domino falls. You never need to watch domino number one million; the two facts together guarantee it.

What. The principle of mathematical induction (weak or ordinary induction) states that to prove ∀n ≥ n₀ P(n), it suffices to prove:

1. Basis step: P(n₀).
2. Inductive step: ∀k ≥ n₀ (P(k) → P(k + 1)).

In the inductive step, the assumption P(k) is the inductive hypothesis (IH). As an inference rule (1.3):

  P(n₀)
  ∀k ≥ n₀ (P(k) → P(k + 1))
  ─────────────────────────
  ∴ ∀n ≥ n₀ P(n)

The inductive step is proved like any conditional (1.4): take an arbitrary k ≥ n₀, assume P(k), and derive P(k + 1). You are not assuming what you want to prove. You are proving an implication, and the implication is what makes the chain of dominoes work.

How: the proof template.

Theorem. For all integers n ≥ n₀, P(n).
Proof (by induction on n).
  Basis.  Show P(n₀) by direct computation.
  Inductive step.  Let k ≥ n₀ be arbitrary and assume P(k)   (IH).
          Write out P(k + 1), the goal.
          Rewrite the goal so that a P(k)-shaped piece appears, apply the IH, simplify.
          Therefore P(k + 1).
  By induction, P(n) holds for all n ≥ n₀.  ∎

Example 1 (a sum). For all n ≥ 1, 1 + 2 + ⋯ + n = n(n + 1)/2.

Proof. Basis: for n = 1, the left side is 1 and the right side is 1·2/2 = 1. Inductive step: assume 1 + ⋯ + k = k(k + 1)/2 for some k ≥ 1. Then

  1 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)       (IH applied to the first k terms)
                        = (k + 1)(k/2 + 1)
                        = (k + 1)(k + 2)/2           which is P(k + 1).  ∎

Example 2 (divisibility). For all n ≥ 0, 3 ∣ n³ − n.

Proof. Basis: 0³ − 0 = 0 = 3·0. Inductive step: assume 3 ∣ k³ − k. Then (k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k). The first part is divisible by 3 by the IH and the second is a multiple of 3, so the sum is divisible by 3. ∎

Example 3 (an inequality with a later start). For all n ≥ 5, 2^n > n².

Proof. Basis: 2⁵ = 32 > 25 = 5². (The claim is false for n = 2, 3, 4, which is why n₀ = 5.) Inductive step: assume 2^k > k² with k ≥ 5. Then 2^{k+1} = 2·2^k > 2k². It remains to show 2k² ≥ (k + 1)², i.e. k² ≥ 2k + 1. This holds because k ≥ 5 gives k² ≥ 5k = 2k + 3k > 2k + 1. ∎

Induction is recursion. An induction proof is a recipe that builds a proof of P(n) for any specific n: start from the basis and apply the inductive step n − n₀ times. The structure is identical to a recursive function with a base case.

def proof_of(n):
    """Produce the chain of steps that establishes P(n) from the basis P(0)."""
    if n == 0:
        return ["P(0) by the basis step"]
    return proof_of(n - 1) + [f"P({n - 1}) -> P({n}) by the inductive step"]

print(*proof_of(3), sep="\n")
# P(0) by the basis step
# P(0) -> P(1) by the inductive step
# P(1) -> P(2) by the inductive step
# P(2) -> P(3) by the inductive step

# Spot checks (not a proof) of the three examples above
assert all(sum(range(1, n + 1)) == n * (n + 1) // 2 for n in range(1, 500))
assert all((n**3 - n) % 3 == 0 for n in range(500))
assert all(2**n > n**2 for n in range(5, 500)) and not 2**4 > 4**2

Key takeaways

• Weak induction: prove the basis P(n₀) and the step P(k) → P(k + 1) for arbitrary k ≥ n₀.
• The inductive hypothesis is the premise of an implication, not an assumption of the result.
• In the step, locate a copy of P(k) inside P(k + 1), apply the IH, and finish with algebra.
• The basis can start at any n₀. Choose it as the first value where the claim, and the step's reasoning, both hold.

Practice

1. (Beginner) Prove by induction that 1 + 2 + 4 + ⋯ + 2^n = 2^{n+1} − 1 for all n ≥ 0.
2. (Intermediate) Prove that n! > 2^n for all n ≥ 4, and that 6 ∣ 7^n − 1 for all n ≥ 0.
3. (Interview) A 2^n × 2^n grid has one arbitrary square removed. Prove that the rest can always be tiled with L-shaped trominoes (3-square L pieces). Hint: split the grid into four 2^{n−1} × 2^{n−1} quadrants. One quadrant contains the missing square. Place a single tromino at the centre so that each of the other three quadrants is also missing exactly one square.

Strong Induction

Why. Sometimes P(k + 1) does not follow from P(k) alone but from some earlier case, or from several. To prove that n factors into primes, write n = a·b: the factors a and b can be anywhere below n, not just at n − 1. Strong induction lets the inductive step use every earlier case.

Analogy. Weak induction is a ladder where each rung rests on the one directly below. Strong induction is a staircase built from concrete: each new step rests on the whole solid structure beneath it.

What. The principle of strong induction (complete induction) states that to prove ∀n ≥ n₀ P(n), it suffices to prove:

1. Basis step: P(n₀), and possibly P(n₀ + 1), …, P(n₀ + b) if the step needs to reach back b + 1 places.
2. Inductive step: for every k ≥ n₀ + b, (P(n₀) ∧ P(n₀ + 1) ∧ ⋯ ∧ P(k)) → P(k + 1).

	Weak induction	Strong induction
Hypothesis in the step	P(k) only	P(n₀), …, P(k): all earlier cases
Typical use	Sums, simple inequalities, one-step recurrences	Factorizations, multi-term recurrences, divide-and-conquer, games
Basis	Usually one case	As many cases as the step reaches back
Logical strength	Equivalent: each can be derived from the other	Equivalent

Strong induction is no more powerful than weak induction. Applying weak induction to Q(n) = P(n₀) ∧ ⋯ ∧ P(n) turns any strong induction proof into a weak one. Use whichever form makes the step easiest to write.

Example 1 (prime factorization exists). Every integer n ≥ 2 is a product of one or more primes.

Proof. Basis: 2 is prime, so it is a product of one prime. Inductive step: assume every integer j with 2 ≤ j ≤ k is a product of primes, and consider k + 1. If k + 1 is prime, we are done. Otherwise k + 1 = a·b with 2 ≤ a, b ≤ k. By the IH both a and b are products of primes, so their product is too. ∎

The IH was applied to a and b, whose values we do not know in advance. Weak induction would offer only P(k), which is useless here.

Example 2 (postage). Every amount n ≥ 12 cents can be paid with 4-cent and 5-cent stamps.

Proof. Basis: 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5. Inductive step: let k ≥ 15 and assume all amounts from 12 to k can be paid. Then k + 1 − 4 = k − 3 lies between 12 and k, so it can be paid. Add one 4-cent stamp. ∎

Four basis cases are needed because the step reaches back four places. With only n = 12 as the basis, the step for k + 1 = 13 would rely on 9, which cannot be paid.

The proof is also an algorithm. Each recursive call corresponds to one use of the inductive hypothesis:

def postage(n):
    """Return (fours, fives) with 4*fours + 5*fives == n, for n >= 12."""
    base = {12: (3, 0), 13: (2, 1), 14: (1, 2), 15: (0, 3)}   # the four basis cases
    if n in base:
        return base[n]
    fours, fives = postage(n - 4)                             # IH applied to n - 4, not n - 1
    return fours + 1, fives

for n in [12, 17, 23, 100]:
    f4, f5 = postage(n)
    assert 4 * f4 + 5 * f5 == n
    print(n, (f4, f5))
# 12 (3, 0)
# 17 (3, 1)
# 23 (2, 3)
# 100 (25, 0)

Key takeaways

• Strong induction assumes P for all values from n₀ to k when proving P(k + 1).
• Use it when the step needs cases other than the immediately preceding one, for example after splitting into factors or halves.
• Provide as many basis cases as the step reaches back. A missing basis case breaks the whole chain.
• Weak and strong induction are logically equivalent. A constructive strong induction proof is a recursive algorithm.

Practice

1. (Beginner) Prove that every amount n ≥ 8 cents can be paid with 3-cent and 5-cent stamps. How many basis cases do you need?
2. (Intermediate) Prove by strong induction that every positive integer is a sum of distinct powers of 2 (the existence of binary representation). Then prove that the Fibonacci numbers (f_0 = 0, f_1 = 1, f_n = f_{n−1} + f_{n−2}) satisfy f_n < 2^n for all n ≥ 0.
3. (Interview) Two players alternately remove 1 or 2 stones from a pile of n. Whoever takes the last stone wins. Prove that the first player has a winning strategy if and only if n is not a multiple of 3. Hint: use strong induction on n, with cases on n mod 3. Show that from a multiple of 3 every move leaves a non-multiple, and from a non-multiple some move leaves a multiple.

Well-Ordering Principle

Why. Why is induction valid at all? It cannot be proved from ordinary arithmetic alone. It rests on a basic property of the natural numbers, which also supports two other common arguments: the "minimal counterexample" proof and the proof that a loop terminates.

What. The well-ordering principle (WOP) states:

  Every non-empty subset of ℕ has a least element.

This is what makes (ℕ, ≤) a well-order (2.5). It fails for other familiar number sets:

Set	Well-ordered by ≤?	A non-empty subset with no least element
ℕ, ℤ⁺, {n ∈ ℤ | n ≥ n₀}	Yes	None exists
ℤ	No	ℤ itself (no smallest integer)
ℚ≥0, ℝ≥0	No	{1/n | n ∈ ℤ⁺} (gets arbitrarily close to 0, never reaches it)

WOP implies induction. Suppose P(0) and ∀k (P(k) → P(k + 1)) hold, but P(n) fails for some n. Then the set of counterexamples C = {n ∈ ℕ | ¬P(n)} is non-empty, so by WOP it has a least element m. m ≠ 0 because P(0) holds. So m − 1 ∈ ℕ and m − 1 ∉ C because m is the least counterexample. Hence P(m − 1) holds, and the inductive step gives P(m), contradicting m ∈ C. ∎ (Conversely, WOP can be proved by strong induction, so the three principles are equivalent.)

How: proof by minimal counterexample. Suppose the theorem is false, take the smallest counterexample m, and derive a contradiction, usually by constructing an even smaller counterexample. This is induction in contrapositive form.

Example. Every integer n ≥ 2 has a prime divisor. Suppose not, and let m be the least integer ≥ 2 with no prime divisor. m is not prime (it would divide itself), so m = a·b with 2 ≤ a < m. Since a < m, a has a prime divisor p, and p ∣ a ∣ m, a contradiction. ∎

How: proving termination. A strictly decreasing sequence of natural numbers must be finite. Otherwise its set of values would be a non-empty subset of ℕ with no least element. So, to prove that a loop terminates, find a variant (ranking function): an expression with natural-number values that strictly decreases on every iteration.

Algorithm	Variant	Why it decreases
Euclid's gcd(a, b)	b	b is replaced by a mod b < b
Binary search	hi − lo	Each iteration discards at least one position
Bubble sort	Number of inversions	Each adjacent swap of an inverted pair removes exactly one inversion
Countdown while n > 0: n -= 1	n	Decremented by 1

def gcd(a, b):
    """Euclid's algorithm for a, b >= 0, with the termination variant checked at run time."""
    while b != 0:
        old_variant = b
        a, b = b, a % b
        assert 0 <= b < old_variant      # the variant is a natural number and strictly decreases
    return a

print(gcd(252, 105))                     # 21

# By contrast, there is no known variant for the Collatz loop below.
# Whether it terminates for every n >= 1 is a famous open problem.
def collatz_steps(n):
    steps = 0
    while n != 1:
        n = n // 2 if n % 2 == 0 else 3 * n + 1
        steps += 1
    return steps

print(collatz_steps(27))                 # 111

Key takeaways

• WOP: every non-empty set of natural numbers has a least element. It fails for ℤ, ℚ≥0, and ℝ≥0.
• WOP, weak induction, and strong induction are equivalent. Each can be derived from the others.
• Minimal counterexample: assume a smallest failure exists, then produce a smaller one or another contradiction.
• A loop terminates if some natural-number-valued variant strictly decreases on every iteration.

Practice

1. (Beginner) Which of these sets have a least element: {n ∈ ℤ | n² > 50}, {n ∈ ℕ | n² > 50}, {x ∈ ℝ | x > 0}, the set of positive even numbers that are not a sum of two primes?
2. (Intermediate) Use WOP to prove the existence half of the division algorithm: for integers a and d > 0, there exist integers q and 0 ≤ r < d with a = dq + r. Hint: take r to be the least element of {a − dq | q ∈ ℤ, a − dq ≥ 0} and show it is less than d.
3. (Interview) Prove that "while some adjacent pair is out of order, swap it" terminates for every finite list, and bound the number of swaps. Hint: an inversion is a pair of positions i < j with A[i] > A[j]. What happens to the number of inversions after one adjacent swap, and what is its maximum value?

Common Induction Pitfalls

Why. An induction proof has few moving parts, so a flaw in any one of them invalidates the whole argument while the rest still looks convincing. Recognising the standard failure patterns is the fastest way to write correct proofs and to review other people's.

What.

Pitfall	What goes wrong	Fix
Missing or wrong basis	The step is valid but the chain never starts	Always verify the basis explicitly, with real numbers
Step fails for small k	The step's argument silently needs k to be large enough	Check the step at the smallest k it is used for. Add basis cases or raise n₀
Too few basis cases in strong induction	The step reaches back further than the basis covers	Count how far back the IH is applied and cover that many base values
Assuming the conclusion	Start from P(k + 1) and derive a true statement	Start from the IH and derive P(k + 1), or make sure every step is reversible
Hypothesis too weak	The IH does not give enough information to prove P(k + 1)	Prove a stronger statement (strengthen the IH)
"Build-up" error	P(k + 1) is proved only for objects built from a size-k object, not for every size-k + 1 object	Start from an arbitrary object of size k + 1 and reduce it to size k

Example 1 (missing basis). Claim: n² + n is odd for every n ≥ 1. The step works: if k² + k is odd, then (k + 1)² + (k + 1) = (k² + k) + 2(k + 1) is odd plus even, which is odd. But the basis fails: 1² + 1 = 2 is even. In fact n² + n = n(n + 1) is always even. The step only shows that oddness would propagate, and there is no odd case to start from.

step_ok = all((k*k + k) % 2 == 0 or ((k+1)**2 + (k+1)) % 2 == 1 for k in range(1000))
basis_ok = (1*1 + 1) % 2 == 1
print(step_ok, basis_ok)      # True False  -> the implication holds, but the chain never starts

Example 2 (step fails for small k): "all horses are the same colour". Claim: in every set of n ≥ 1 horses, all horses have the same colour. Basis: one horse has one colour. Step: given k + 1 horses, remove horse A. The remaining k share a colour by the IH. Put A back, remove horse B instead, and the remaining k again share a colour. The two groups overlap, so all k + 1 share a colour.

  k + 1 = 3:   {H1, H2, H3}  ->  {H2, H3} same colour,  {H1, H3} same colour,  overlap = {H3}   works
  k + 1 = 2:   {H1, H2}      ->  {H2} same colour,      {H1} same colour,      overlap = ∅      FAILS

The step needs the two groups to share a horse, which requires k + 1 ≥ 3. The case 1 → 2 is the broken domino, so nothing beyond n = 1 follows.

Example 3 (strengthening the hypothesis). Claim: Σ_{i=1}^{n} 1/i² < 2 for all n ≥ 1. A direct induction fails: knowing the sum is below 2 says nothing about whether adding 1/(k + 1)² keeps it below 2. Prove the stronger claim Σ_{i=1}^{n} 1/i² ≤ 2 − 1/n instead. Then the IH is precise enough:

  Σ_{i=1}^{k+1} 1/i² ≤ 2 − 1/k + 1/(k + 1)²  ≤  2 − 1/(k + 1)
  because   1/(k + 1)² ≤ 1/k − 1/(k + 1) = 1/(k(k + 1)).

The stronger statement is easier to prove because it gives the step more to work with. Experienced provers strengthen the hypothesis routinely.

Example 4 (build-up error). To prove a property of all connected graphs with k + 1 vertices, it is tempting to take a connected graph with k vertices and add a vertex. But that only covers graphs that can be built this way, and you have to prove that every (k + 1)-vertex graph arises like that, which is often the hard part. The safe pattern is to start from an arbitrary (k + 1)-vertex graph, remove a suitable vertex, and apply the IH to what remains.

Key takeaways

• Check the basis with actual values. A valid step with a false basis proves nothing.
• Check that the inductive step works for the smallest k it is applied to.
• Argue forward from the IH to P(k + 1), never backward from P(k + 1) to something true.
• If the IH is too weak to finish the step, strengthen the statement being proved.
• In the step, start from an arbitrary object of size k + 1 and shrink it. Do not grow a size-k object.

Practice

1. (Beginner) Find the error: "Claim: n = n + 1 for all n. Step: if k = k + 1, adding 1 to both sides gives k + 1 = k + 2. Hence the claim holds by induction."
2. (Intermediate) Find the error: "Every set of n ≥ 2 lines in the plane, no two parallel, passes through a common point. Basis: two non-parallel lines meet. Step: given k + 1 lines, the first k meet at a point p and the last k meet at a point q. The k − 1 lines in both groups pass through p and q, so p = q."
3. (Interview) A teammate proves "every tree with n vertices has n − 1 edges" by taking a tree with k vertices and attaching a new leaf. Is the proof complete? What must be added, or how should the step be restructured? Hint: does every tree with k + 1 vertices arise by attaching a leaf to a k-vertex tree? What property of trees (Chapter 9) would you need to prove first?

<a id="33-recursive-definitions"></a>

3.3 Recursive Definitions

A recursive definition describes an object in terms of smaller instances of itself, plus base cases that stop the regress. This subchapter applies the idea to functions, sets, and algorithms, introduces structural induction for proving facts about recursively defined objects, and finishes with loop invariants for proving iterative programs correct.

Recursively Defined Functions

Why. Many functions are easiest to state in terms of their own smaller values: n! = n·(n − 1)!, or "the number of ways to climb n stairs taking 1 or 2 steps at a time is the number of ways for n − 1 plus the number for n − 2". A closed form may be unknown, complicated, or non-existent, while the recursive description is short and obviously right.

What. A function f with domain ℕ is defined recursively by:

1. Basis step: the value of f at one or more initial arguments, such as f(0).
2. Recursive step: a rule giving f(n) in terms of f at smaller arguments.

Strong induction (3.2) guarantees that such a definition determines exactly one value for every n: the values at smaller arguments are already determined when f(n) is computed.

Function	Basis	Recursive step
Factorial	0! = 1	n! = n · (n − 1)!
Power	a^0 = 1	a^n = a · a^{n−1}
Sum of a sequence	Σ_{i=1}^{0} a_i = 0	Σ_{i=1}^{n} a_i = Σ_{i=1}^{n−1} a_i + a_n
Fibonacci	f_0 = 0, f_1 = 1	f_n = f_{n−1} + f_{n−2}
GCD (Euclid)	gcd(a, 0) = a	gcd(a, b) = gcd(b, a mod b) for b > 0

Well-definedness. A recursive "definition" must reach a base case from every argument, by steps that always land inside the domain. Two ways this fails:

• f(n) = 1 + f(n + 1): the argument grows, so no base case is ever reached and f is not defined.
• g(n) = g(n/2) for even n and g(n) = g(3n + 1) for odd n > 1, with g(1) = 1: whether every argument reaches 1 is the open Collatz problem from 3.2. Nobody knows whether g is well-defined on all of ℤ⁺.

The safe pattern is the one in the table: every recursive call is made on an argument that is strictly smaller in a well-ordered set (3.2). Arguments need not shrink by 1. Euclid's algorithm shrinks the second argument, and the Ackermann function shrinks a pair of arguments in lexicographic order. That function is well-defined but grows faster than any function built from loops with bounds fixed in advance.

Recursion and induction are partners. Properties of a recursively defined function are proved by induction that follows the same structure as the definition.

Example. For all n ≥ 1, f_1 + f_2 + ⋯ + f_n = f_{n+2} − 1. Basis: f_1 = 1 and f_3 − 1 = 2 − 1 = 1. Step: assume f_1 + ⋯ + f_k = f_{k+2} − 1. Then f_1 + ⋯ + f_k + f_{k+1} = f_{k+2} − 1 + f_{k+1} = f_{k+3} − 1 by the Fibonacci rule. ∎

Efficiency. A definition that is mathematically correct can be computationally disastrous. Translating the Fibonacci definition literally recomputes the same values over and over. The number of calls is 2f_{n+1} − 1, which grows exponentially. Caching each value after it is computed (memoization) makes the cost linear.

 fib(5) call tree: fib(3) is computed twice, fib(2) three times, fib(1) five times
                         fib(5)
                  ┌────────┴────────┐
               fib(4)             fib(3)
            ┌─────┴─────┐       ┌───┴───┐
         fib(3)      fib(2)   fib(2)  fib(1)
        ┌──┴──┐      ┌──┴──┐  ┌──┴──┐
     fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
     ┌──┴──┐
  fib(1) fib(0)

from functools import lru_cache

def factorial(n):
    return 1 if n == 0 else n * factorial(n - 1)     # basis | recursive step

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    if n < 2:
        return n                                     # f_0 = 0, f_1 = 1
    return fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)                             # memoization: each f_n computed once
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(factorial(5))                                  # 120
print(fib_naive(20), calls)                          # 6765 21891   (21891 = 2*f_21 - 1)
print(fib(90))                                       # 2880067194370816120  (instant)

Key takeaways

• A recursive definition has a basis and a recursive step that uses values at smaller arguments.
• It is well-defined when every chain of recursive calls reaches a base case, which is guaranteed when arguments strictly decrease in a well-ordered set.
• Prove properties of recursively defined functions by induction that mirrors the definition.
• Direct translation can repeat work exponentially. Memoization or bottom-up iteration avoids this.

Practice

1. (Beginner) Give a recursive definition of m·n for m, n ∈ ℕ using only addition, and of the sequence a_n = 3^n + 1. Compute f_0 through f_10.
2. (Intermediate) Prove by induction that f_{n+1}·f_{n−1} − f_n² = (−1)^n for all n ≥ 1 (Cassini's identity).
3. (Interview) Prove that the naive recursive Fibonacci makes exactly 2f_{n+1} − 1 calls on input n, and rewrite it to use O(n) time and O(1) extra space. Hint: let C(n) be the number of calls, write a recurrence for C(n) that resembles the Fibonacci rule, and prove the formula by strong induction. For the rewrite, keep only the last two values.

Recursively Defined Sets

Why. Many important collections are infinite but generated by a few rules: the natural numbers, all strings over an alphabet, all syntactically valid programs, all JSON documents, all binary trees. Listing them is impossible, but stating "these are the starting elements, and these rules build new elements from existing ones" captures the set exactly.

What. A set S is defined recursively by:

1. Basis step: specific elements that belong to S.
2. Recursive step: rules that build new elements of S from elements already known to be in S.
3. Exclusion rule: S contains nothing else. It is the smallest set closed under the rules.

The exclusion rule is usually left implicit, but it is essential. Without it, the rules "0 ∈ S; if n ∈ S then n + 2 ∈ S" would also be satisfied by ℤ, not just by the even naturals.

Set	Basis	Recursive step
ℕ	0 ∈ ℕ	n ∈ ℕ → n + 1 ∈ ℕ
Strings Σ* over alphabet Σ	λ ∈ Σ*	w ∈ Σ*, x ∈ Σ → wx ∈ Σ*
Balanced parentheses B	λ ∈ B	u, v ∈ B → (u)v ∈ B
Full binary trees T	A single vertex is in T	T₁, T₂ ∈ T → a new root with left subtree T₁ and right subtree T₂ is in T
Lists of A	Nil (empty list)	a ∈ A, L a list → Cons(a, L) is a list
Arithmetic expressions E	Numbers and variables	e₁, e₂ ∈ E → (e₁ + e₂), (e₁ · e₂), (−e₁) are in E

How: generating elements in rounds. Start with the basis elements, then repeatedly apply every rule to what you already have. Every element of S appears after finitely many rounds, and the round in which it first appears measures how many rule applications it needs. This is the same as producing the strings of a grammar (Chapter 13).

Balanced parentheses B, rule: u, v ∈ B  ->  (u)v ∈ B

Round 0:  λ
Round 1:  ()                               u = λ,  v = λ
Round 2:  ()(),  (()),  (())()             new combinations using ()
Round 3:  ()()(), ()(()), (()()), ((())), ...

def balanced_up_to(max_len):
    """Generate the recursively defined set B of balanced strings up to length max_len."""
    B = {""}                                           # basis: the empty string λ
    while True:
        new = {f"({u}){v}" for u in B for v in B       # recursive step: (u)v
               if len(u) + len(v) + 2 <= max_len}
        if new <= B:                                   # no new elements: closed under the rule
            return B
        B |= new

def is_balanced(s):
    """Membership test: each prefix has at least as many '(' as ')', and totals are equal."""
    depth = 0
    for c in s:
        depth += 1 if c == "(" else -1
        if depth < 0:
            return False
    return depth == 0

B6 = balanced_up_to(6)
print(sorted(B6, key=lambda s: (len(s), s)))
# ['', '()', '(())', '()()', '((()))', '(()())', '(())()', '()(())', '()()()']
print(len(B6), all(is_balanced(s) for s in B6))       # 9 True

The recursive definition and the counter-based membership test describe the same set. Proving that they agree is a typical use of structural induction (next topic).

Data types are recursively defined sets. An algebraic data type in a functional language, or a class whose fields refer to the class itself, is a recursive set definition in code:

from dataclasses import dataclass
from typing import Optional

@dataclass
class Tree:                     # full binary tree: either a leaf (no children) or a root with two subtrees
    left: Optional["Tree"] = None
    right: Optional["Tree"] = None

leaf = Tree()                                  # basis
t = Tree(Tree(leaf, leaf), leaf)               # recursive step applied twice

Key takeaways

• A recursive set definition has a basis, recursive rules, and an exclusion rule: the set is the smallest one closed under the rules.
• Every element is produced by finitely many rule applications starting from basis elements.
• Strings, lists, trees, expressions, and grammars are all recursively defined sets.
• Recursive data types in code are recursive set definitions.

Practice

1. (Beginner) Give recursive definitions of the set of positive multiples of 3, and of the set of palindromes over {a, b}.
2. (Intermediate) Let S be defined by (3, 2) ∈ S, and (a, b) ∈ S → (a + 2, b + 3) ∈ S and (a + 3, b + 2) ∈ S. List the elements produced in the first two rounds. Conjecture a property shared by all elements of S that involves 5 ∣ a + b.
3. (Interview) Write a recursive definition of the set of valid JSON values, then sketch a recursive validate(value) function whose cases correspond to your rules. Hint: the basis covers null, booleans, numbers, and strings. The recursive step covers arrays of values and objects mapping strings to values.

Structural Induction

Why. Recursively defined sets such as trees, strings, and expressions are not naturally indexed by a single integer n. We could induct on size or height, but there is a more direct method whose shape matches the definition of the set exactly, the same way recursive code matches the shape of the data.

What. To prove that P(x) holds for every element x of a recursively defined set S:

1. Basis step: show P(x) for every basis element x.
2. Recursive step: for every rule that builds x from x₁, …, x_m, show that P(x₁) ∧ ⋯ ∧ P(x_m) implies P(x).

Why it works: the elements for which P holds form a set that contains the basis and is closed under the rules. S is the smallest such set (the exclusion rule), so every element of S satisfies P. Equivalently, it is strong induction on the number of rule applications needed to build x. Ordinary weak induction is the special case where S = ℕ, with basis 0 and rule n ↦ n + 1.

Example 1 (full binary trees). Define for a full binary tree T:

	Single vertex	Tree with root, subtrees T₁ and T₂
Leaves l(T)	1	l(T₁) + l(T₂)
Internal vertices i(T)	0	1 + i(T₁) + i(T₂)
Height h(T)	0	1 + max(h(T₁), h(T₂))
Vertices n(T)	1	1 + n(T₁) + n(T₂)

Claim: l(T) = i(T) + 1 for every full binary tree. Basis: a single vertex has l = 1 and i = 0. Recursive step: assume l(T₁) = i(T₁) + 1 and l(T₂) = i(T₂) + 1. Then l(T) = l(T₁) + l(T₂) = i(T₁) + i(T₂) + 2 = (1 + i(T₁) + i(T₂)) + 1 = i(T) + 1. ∎

Claim: n(T) ≤ 2^{h(T)+1} − 1. Basis: n = 1 = 2^1 − 1. Recursive step: with h = h(T), both subtrees have height at most h − 1, so n(T) = 1 + n(T₁) + n(T₂) ≤ 1 + 2(2^h − 1) = 2^{h+1} − 1. ∎

The second claim is why a balanced binary search tree with n keys has height at least log₂(n + 1) − 1 (Chapter 9).

            •              l(T) = 4 leaves (○)
          ╱   ╲            i(T) = 3 internal (•)
         •     ○           l = i + 1  (holds)
        ╱ ╲                h(T) = 3, n(T) = 7 ≤ 2^4 − 1 = 15  (holds)
       ○   •
          ╱ ╲
         ○   ○

Example 2 (strings). Define the length of a string recursively: len(λ) = 0 and len(wx) = len(w) + 1. Define concatenation by w·λ = w and w·(vx) = (w·v)x. Claim: len(w·v) = len(w) + len(v). Use structural induction on v. Basis: len(w·λ) = len(w) = len(w) + 0. Step: len(w·(vx)) = len((w·v)x) = len(w·v) + 1 = len(w) + len(v) + 1 = len(w) + len(vx). ∎

Recursive code follows the same pattern. A function defined by one case per rule of the data type is called structural recursion. It terminates, because each call is on a strictly smaller part, and its correctness proof is a structural induction with one case per branch.

from dataclasses import dataclass
from typing import Optional

@dataclass
class Tree:
    left: Optional["Tree"] = None
    right: Optional["Tree"] = None

def is_leaf(t):
    return t.left is None and t.right is None

def leaves(t):       return 1 if is_leaf(t) else leaves(t.left) + leaves(t.right)
def internal(t):     return 0 if is_leaf(t) else 1 + internal(t.left) + internal(t.right)
def height(t):       return 0 if is_leaf(t) else 1 + max(height(t.left), height(t.right))
def size(t):         return 1 if is_leaf(t) else 1 + size(t.left) + size(t.right)

L = Tree()
t = Tree(Tree(L, Tree(L, L)), L)                     # the tree drawn above
print(leaves(t), internal(t), height(t), size(t))    # 4 3 3 7
assert leaves(t) == internal(t) + 1
assert size(t) <= 2 ** (height(t) + 1) - 1

Key takeaways

• Structural induction proves P for every element of a recursively defined set: basis elements, then one step per construction rule.
• In each step, assume P for the components and prove it for the constructed element.
• It is valid because of the exclusion rule. Weak induction on ℕ is the simplest special case.
• Structural recursion and structural induction share a shape: one case per rule.

Practice

1. (Beginner) Prove by structural induction that every string in the set B of balanced parentheses has even length.
2. (Intermediate) Define reverse(λ) = λ and reverse(wx) = x·reverse(w) for a symbol x. Prove that len(reverse(w)) = len(w). Then prove that every string in B has equal numbers of ( and ), and that every prefix has at least as many ( as ).
3. (Interview) Explain why a function that walks a JSON document by recursing only into the elements of arrays and the values of objects must terminate on any document parsed from text, but may loop forever on an in-memory object graph built in code. Hint: the termination argument is structural induction over a finite, recursively built value. What can an in-memory graph contain that a parsed tree cannot?

Recursive Algorithms

Why. If a problem can be reduced to smaller instances of the same problem, a recursive algorithm writes that reduction down directly. The resulting code is often shorter and much easier to prove correct than an iterative equivalent, because the correctness proof is an induction with the same structure as the code.

What. A recursive algorithm solves an instance by:

1. Solving base cases directly.
2. Otherwise, reducing the instance to one or more smaller instances, solving them by recursive calls, and combining the results.

Its correctness proof is a strong induction on the input size:

• Basis: the base cases return correct answers.
• Inductive step: assuming every recursive call on a smaller input returns a correct answer (the IH), the combination step produces a correct answer.
• Termination: every call is on a strictly smaller input, measured by a natural-number variant (3.2).

The key discipline is the recursive leap of faith: when reasoning about the combine step, trust the recursive calls to be correct. Do not trace them. That trust is exactly what the inductive hypothesis provides.

Example: fast exponentiation. Computing a^n with n multiplications is slow when n is large, as in cryptography (Chapter 4). Use a^n = (a^{n/2})² for even n.

def power(a, n):
    """Compute a**n for n >= 0 with O(log n) multiplications."""
    if n == 0:
        return 1                              # basis: a^0 = 1
    half = power(a, n // 2)                   # IH: correct, because n // 2 < n
    if n % 2 == 0:
        return half * half                    # a^n = (a^{n/2})^2
    return half * half * a                    # a^n = (a^{(n-1)/2})^2 · a

def binary_search(arr, target, lo=0, hi=None):
    """Return an index of target in sorted arr[lo:hi], or -1."""
    if hi is None:
        hi = len(arr)
    if lo >= hi:
        return -1                             # basis: empty range
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)   # range shrinks: variant hi - lo decreases
    return binary_search(arr, target, lo, mid)

print(power(3, 13), 3**13)                    # 1594323 1594323
print(binary_search([2, 3, 5, 7, 11, 13], 11), binary_search([2, 3, 5, 7], 4))   # 4 -1

Correctness of power, by strong induction on n. Basis: power(a, 0) = 1 = a^0. Step: let n ≥ 1 and assume power(a, m) = a^m for all m < n. Since ⌊n/2⌋ < n, half = a^{⌊n/2⌋}. If n is even, half² = a^n. If n is odd, ⌊n/2⌋ = (n − 1)/2, and half²·a = a^{n−1}·a = a^n. ∎ The argument halves at each call, so there are about log₂ n calls.

The call stack. Each active call keeps its own frame (arguments, local variables, return point) on the call stack. The maximum recursion depth determines the memory used, and very deep recursion overflows the stack.

factorial(3)                          stack grows ↓          returns ↑
 └─ 3 * factorial(2)                  [factorial(3): n=3]     6
       └─ 2 * factorial(1)            [factorial(2): n=2]     2
             └─ 1 * factorial(0)      [factorial(1): n=1]     1
                   └─ return 1        [factorial(0): n=0]     1

	Recursion	Iteration
Natural fit	Recursive data (trees, grammars), divide-and-conquer	Linear scans, simple counters
Correctness proof	Induction mirroring the recursive structure	Loop invariant (next topic)
Memory	O(depth) stack frames	Usually O(1) extra
Risk	Stack overflow (Python's default limit is about 1000 frames)	Off-by-one errors in loop bounds
Conversion	Every recursion can be made iterative with an explicit stack	Tail recursion is a loop in disguise

The running time of a recursive algorithm satisfies a recurrence, for example T(n) = T(n/2) + O(1) for binary search and T(n) = 2T(n/2) + O(n) for merge sort. Solving such recurrences is the subject of Chapter 6.

Key takeaways

• A recursive algorithm handles base cases directly and reduces larger inputs to strictly smaller ones.
• Prove correctness by strong induction: base cases, the combine step under the IH, and a decreasing variant for termination.
• Trust the recursive calls when reasoning about one level. That trust is the inductive hypothesis.
• Recursion uses stack space proportional to its depth. Its running time is described by a recurrence.

Practice

1. (Beginner) Write a recursive function that returns the maximum of a non-empty list, and prove it correct by induction on the length of the list.
2. (Intermediate) Prove that binary_search above returns a correct answer: an index of target if it occurs in the sorted range arr[lo:hi], and −1 otherwise. State the variant that guarantees termination.
3. (Interview) A recursive depth-first search crashes with RecursionError on a graph shaped like a path of 100 000 vertices. Rewrite it iteratively and explain what replaces the call stack. Hint: push vertices onto an explicit list used as a stack. Consider when a vertex should be marked as visited so that it is processed only once.

Program Correctness and Loop Invariants

Why. Testing shows that a program works on the inputs you tried. A proof shows that it works on all inputs. For loops, the main proof tool is the loop invariant, a property that holds before and after every iteration. It is induction applied to the number of iterations.

What. A program S is specified with a precondition p (what is assumed about the input) and a postcondition q (what must hold at the end). The Hoare triple {p} S {q} states:

• Partial correctness: if p holds before S runs and S terminates, then q holds afterwards.
• Total correctness: partial correctness, and S terminates on every input satisfying p.

Rule	Premises	Conclusion
Composition	{p} S₁ {r} and {r} S₂ {q}	{p} S₁; S₂ {q}
Conditional	{p ∧ c} S₁ {q} and {p ∧ ¬c} S₂ {q}	{p} if c then S₁ else S₂ {q}
Loop	{I ∧ c} S {I}	{I} while c: S {I ∧ ¬c}

The loop rule is the heart of the method. If the body preserves I whenever it runs, then I still holds when the loop exits, and so does ¬c because the loop stopped.

How: the three-part invariant proof.

1. Initialization: I holds before the first iteration.
2. Maintenance: if I and the loop condition hold at the start of an iteration, I holds at its end.
3. Termination: the loop stops (find a decreasing variant, 3.2), and I ∧ ¬c implies the postcondition.

Steps 1 and 2 are the basis and inductive step of an induction on the number of iterations completed. A good invariant usually describes the part of the job already done.

Example: iterative fast exponentiation.

def power_iter(a, n):
    """Precondition: n >= 0.  Postcondition: returns a**n."""
    result, base, exp = 1, a, n
    # Invariant I:  result * base**exp == a**n   and   exp >= 0
    while exp > 0:                                   # variant: exp (a natural number that strictly decreases)
        assert result * base**exp == a**n            # I holds at the start of each iteration
        if exp % 2 == 1:
            result *= base                           # moves one factor of base into result
        base *= base                                 # base**exp keeps its value after halving exp
        exp //= 2
    assert result * base**exp == a**n and exp == 0   # I ∧ ¬(exp > 0)
    return result                                    # since exp == 0, result == a**n

print(power_iter(3, 13))                             # 1594323

Proof. Initialization: result·base^exp = 1·a^n = a^n. Maintenance: suppose result·base^exp = a^n with exp > 0. If exp is even, the new values are base² and exp/2, and (base²)^{exp/2} = base^exp. If exp is odd, the new values are result·base, base², and (exp − 1)/2, and result·base·(base²)^{(exp−1)/2} = result·base^exp. Either way the product is unchanged. Termination: exp is a natural number that strictly decreases (it is halved while positive), so the loop stops. At exit exp = 0, so I gives result·1 = a^n. ∎

Example: insertion sort. Invariant of the outer loop: at the start of iteration i, A[0:i] contains the original first i elements, in sorted order. Initialization: A[0:1] has one element and is sorted. Maintenance: the inner loop inserts A[i] into its place, so A[0:i+1] is sorted. Termination: the loop ends with i = n, so A[0:n], the whole array, is sorted.

 i = 3:   [ 2  5  8 | 4  9  1 ]      invariant: A[0:3] = [2, 5, 8] is sorted
                      ↑ insert 4
 i = 4:   [ 2  4  5  8 | 9  1 ]      invariant restored for A[0:4]

Concept	Role	Proves	Example for power_iter
Invariant	Property preserved by every iteration	Partial correctness	result·base^exp = a^n
Variant	Natural-number quantity that strictly decreases	Termination	exp

Key takeaways

• {p} S {q}: partial correctness assumes termination, while total correctness also proves it.
• A loop invariant is proved by initialization, maintenance, and termination. This is induction on the number of iterations.
• At exit, the invariant together with the negated loop condition must imply the postcondition.
• Pair every invariant with a variant to prove that the loop terminates.

Practice

1. (Beginner) State an invariant for the loop best = A[0]; for i in range(1, n): best = max(best, A[i]) and use it to prove that the loop returns the maximum of A.
2. (Intermediate) Prove that this loop computes n! for n ≥ 0: f, i = 1, 0; while i < n: i += 1; f *= i. Give the invariant, the variant, and the three proof parts.
3. (Interview) State the invariant that makes the iterative binary search lo, hi = 0, len(A) / while lo < hi: ... correct, and explain how a wrong update such as lo = mid instead of lo = mid + 1 breaks either the invariant or the variant. Hint: the invariant should say where target must be if it occurs at all. Check whether hi − lo still strictly decreases when hi = lo + 1.

<a id="4-number-theory"></a>