Chapter 6: Mathematical Induction

"To understand recursion, you must first understand recursion." — programmer folklore

Overview

You already trust induction. Every time you write a recursive function and believe it works for an input of size $n$ because it works for size $n-1$, you are reasoning by induction — you just haven't been asked to prove it yet. This chapter turns that instinct into a tool you can defend in code review. We'll start with dominoes, end with a proof that your recursive function is correct, and never once ask you to take a formula on faith.

Here is the problem induction solves. Suppose you claim that a loop you wrote always produces the right answer, for every input size. You cannot test every input — there are infinitely many. You could test $n = 1, 2, 3, \dots, 1000$ and feel pretty good, but "pretty good" is exactly the gap where production bugs live. Induction is the technique that closes that gap. It lets you make a claim about all natural numbers by checking just two things: that the claim holds at the start, and that it propagates — that whenever it holds for one number, it holds for the next.

That second part is the leap. It feels, the first time you see it, like cheating: "Wait, you're assuming the thing you're trying to prove?" By the end of section 6.2 you'll see exactly why it isn't, and why this single technique underlies recursion, loops, recursive data structures, and a surprising amount of the rest of this book.

In this chapter, you will learn to:

• Recognize when a problem calls for induction.
• Structure an induction proof so a reader can check every step.
• Use induction to prove facts about sums, inequalities, and divisibility.
• Prove a recursive function correct, and prove an iterative loop correct with an invariant.
• Spot the subtle errors that make a "proof" by induction collapse.

Learning Paths

🏃 Fast Track: If you can already write a clean induction proof, skim 6.1–6.2, then go straight to 6.4 (induction and recursion) and 6.5 (loop invariants), which is where the CS payoff is. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Work every 🔄 Check Your Understanding before moving on, and write out the proofs in 6.3 yourself before reading ours.

🔬 Deep Dive: After the chapter, prove the equivalence of the three forms of induction (this chapter, Chapter 7's strong induction, and the well-ordering principle). Exercise set, Part E.

6.1 The intuition: dominoes and recursion

Picture an infinite line of dominoes, standing on end, numbered $1, 2, 3, \dots$ — one for every positive integer. You want to knock them all down. What do you need to guarantee?

Two things, and only two:

1. You knock over the first domino.
2. The dominoes are spaced so that whenever domino $k$ falls, it knocks over domino $k+1$.

If both are true, every domino falls. Not because you pushed each one — you only pushed the first — but because falling propagates down the line. Domino 1 falls (you pushed it). Because 1 fell, 2 falls. Because 2 fell, 3 falls. And so on, forever. No domino is left standing, even though there are infinitely many and you performed exactly one push.

Mathematical induction is this argument, made precise. We want to prove a statement $P(n)$ for every positive integer $n$. Statement $P(n)$ is "domino $n$ falls." We prove two things:

1. Base case: $P(1)$ is true. (The first domino falls.)
2. Inductive step: for every $k$, if $P(k)$ is true, then $P(k+1)$ is true. (Each falling domino topples the next.)

From those two facts, we conclude $P(n)$ holds for all $n \ge 1$.

💡 Intuition: The base case is one concrete check. The inductive step is one general argument that works for every $k$ at once. Two finite pieces of work prove infinitely many cases. That leverage is the whole point.

The connection to programming is immediate. A recursive function has the same shape:

def factorial(n):
    if n == 0:          # base case
        return 1
    return n * factorial(n - 1)   # reduce to a smaller case

Why do you believe factorial(100) is correct? Not because you traced 100 multiplications. You believe it because (1) the base case factorial(0) is obviously right, and (2) if factorial(n-1) is right, then n * factorial(n-1) is right. That is an induction proof, hiding in plain sight inside your confidence about the code. We will make it explicit in 6.4.

🔄 Check Your Understanding 1. In the domino picture, which part corresponds to the base case, and which to the inductive step? 2. Suppose the dominoes are spaced too far apart, so a falling domino sometimes doesn't reach the next. Which of the two requirements fails — and would the conclusion still follow?

Answers

1. "The first domino falls" is the base case; "each falling domino knocks over the next" is the inductive step. 2. The inductive step fails (the implication $P(k) \Rightarrow P(k+1)$ is no longer guaranteed for every $k$). Without it, knocking over domino 1 tells you nothing about the rest, and the conclusion does not follow.

6.2 The principle of mathematical induction

Let's state the technique as a theorem you can apply mechanically, then dissect the one step that trips everyone up.

The Principle of Mathematical Induction. Let $P(n)$ be a statement about the positive integer $n$. If

1. $P(1)$ is true (the base case), and
2. for every integer $k \ge 1$, the implication $P(k) \rightarrow P(k+1)$ is true (the inductive step),

then $P(n)$ is true for all integers $n \ge 1$.

A few pieces of vocabulary, because using them correctly is half of writing a clean proof:

• The base case is the concrete starting value. It is usually $n = 1$, but it can be $n = 0$ (when $\mathbb{N}$ includes 0, as it does in this book) or any integer where your claim begins.
• The inductive step is the general implication "if it holds at $k$, it holds at $k+1$."
• Inside the inductive step, the assumption "$P(k)$ is true" has a name: the inductive hypothesis. You assume it in order to derive $P(k+1)$.

Here is the objection everyone has, and it deserves a real answer.

⚠️ Common Pitfall: "Aren't you assuming what you want to prove?" No — and seeing why is the threshold you need to cross. You are not assuming $P(n)$ for the $n$ you care about. In the inductive step you assume $P(k)$ for a single, arbitrary $k$, and from that you prove a different statement, $P(k+1)$. You are proving an implication, not the conclusion. The conclusion — "$P(n)$ for all $n$" — comes from chaining infinitely many of those implications together, starting from the base case. Assuming $P(k)$ to prove $P(k+1)$ is no more circular than assuming the input to a function in order to reason about its output.

🚪 Threshold Concept. Induction is the first time most people prove infinitely many statements with a finite argument. Once it clicks, you will see its shape everywhere: in recursion, in loop reasoning, in the definitions of trees and lists, in the correctness of divide-and-conquer algorithms. It does not just prove formulas — it is how mathematics reaches the infinite. If only one idea from Part I stays with you, make it this one.

Why is the principle itself true? It follows from a basic fact about the positive integers called the well-ordering principle (every non-empty set of positive integers has a smallest element), which we'll meet properly in Chapter 7. The short version: if some $P(n)$ failed, there would be a smallest $n$ where it failed; that $n$ can't be the base case (we checked it), so $n-1$ works but $n$ doesn't — contradicting the inductive step. We'll make this rigorous next chapter. For now, take the principle as a licensed proof technique and let's use it.

6.3 The induction template, by example

Every induction proof has the same skeleton. Learn the skeleton once and you can write any of them.

The induction template. 1. State $P(n)$ explicitly. ("Let $P(n)$ be the statement that …") 2. Base case: prove $P(\text{start})$ directly. 3. Inductive step: fix an arbitrary $k \ge \text{start}$; assume $P(k)$ (the inductive hypothesis); prove $P(k+1)$, using the hypothesis somewhere. 4. Conclude: by induction, $P(n)$ holds for all $n \ge \text{start}$. $\blacksquare$

Example 1: the sum of the first $n$ positive integers

Claim. For all $n \ge 1$, $\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

The strategy first. We want a statement about an arbitrary $n$. Induction lets us bootstrap from $n=1$. The only creative move will be in the inductive step: we'll take the sum up to $k+1$, peel off the last term, and replace the sum up to $k$ using the inductive hypothesis. That "peel off the last term so the hypothesis applies" move is the engine of almost every summation induction.

Proof. Let $P(n)$ be the statement $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Base case ($n=1$): the left side is $\sum_{i=1}^{1} i = 1$. The right side is $\frac{1 \cdot 2}{2} = 1$. They match, so $P(1)$ holds.

Inductive step: fix $k \ge 1$ and assume $P(k)$: that is, assume $$\sum_{i=1}^{k} i = \frac{k(k+1)}{2}.$$ We must show $P(k+1)$, namely $\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}$. Starting from the left side and peeling off the last term: $$\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1),$$ where the second equality uses the inductive hypothesis. Now combine over a common denominator: $$\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$$ This is exactly $P(k+1)$. By the principle of induction, $P(n)$ holds for all $n \ge 1$. $\blacksquare$

🔗 Connection. This is the formula the young Gauss reputedly found by pairing $1+100$, $2+99$, and so on. Induction verifies the formula but doesn't discover it. That division of labor — intuition or computation to find a candidate, induction to prove it — is theme four of this book (Chapter 11 returns to summations in depth).

Example 2: the sum of the first $n$ odd numbers

Claim. For all $n \ge 1$, the sum of the first $n$ odd positive integers is $n^2$. That is, $\sum_{i=1}^{n} (2i-1) = n^2$.

Proof. Let $P(n)$ be $\sum_{i=1}^{n}(2i-1) = n^2$.

Base case ($n=1$): the first odd number is $1$, and $1^2 = 1$. So $P(1)$ holds.

Inductive step: assume $P(k)$: $\sum_{i=1}^{k}(2i-1) = k^2$. Then $$\sum_{i=1}^{k+1}(2i-1) = \underbrace{\sum_{i=1}^{k}(2i-1)}_{=\,k^2 \text{ by hypothesis}} + \big(2(k+1)-1\big) = k^2 + (2k+1) = (k+1)^2.$$ That is $P(k+1)$. By induction, $P(n)$ holds for all $n \ge 1$. $\blacksquare$

💡 Intuition: This one has a beautiful picture. An $n \times n$ square can be built from L-shaped layers ("gnomons") of sizes $1, 3, 5, \dots$ — each layer is the next odd number, and after $n$ layers you've built an $n^2$ square. Induction is the algebraic shadow of that picture.

Example 3: an inequality

Inequalities need induction too, and they introduce a wrinkle: a non-trivial base case.

Claim. For all integers $n \ge 5$, $2^n > n^2$.

The strategy first. Try small $n$ and you'll see the claim is false for $n=2,3,4$ (e.g., $2^3 = 8 < 9 = 3^2$) and becomes true at $n=5$. So the base case is $n=5$, not $n=1$. In the inductive step we want to go from $2^k > k^2$ to $2^{k+1} > (k+1)^2$. Doubling the left side is easy; the work is showing $2k^2 \ge (k+1)^2$ for $k \ge 5$.

Proof. Let $P(n)$ be $2^n > n^2$, for $n \ge 5$.

Base case ($n=5$): $2^5 = 32 > 25 = 5^2$. So $P(5)$ holds.

Inductive step: fix $k \ge 5$ and assume $2^k > k^2$. Then $$2^{k+1} = 2 \cdot 2^k > 2k^2,$$ using the inductive hypothesis. It now suffices to show $2k^2 \ge (k+1)^2$, because then $2^{k+1} > 2k^2 \ge (k+1)^2$. Expanding, $2k^2 \ge (k+1)^2 = k^2 + 2k + 1$ is equivalent to $k^2 - 2k - 1 \ge 0$, i.e. $k^2 \ge 2k+1$. For $k \ge 5$ this is clear ($25 \ge 11$, and the left side grows faster). Hence $2^{k+1} > (k+1)^2$, which is $P(k+1)$. By induction, $P(n)$ holds for all $n \ge 5$. $\blacksquare$

⚠️ Common Pitfall: Forgetting to check that the base case is where the claim actually starts. If you "prove" $2^n > n^2$ with a base case of $n=1$, your base case is false ($2 > 1$ is true, but $n=2,3,4$ fail), and even if $n=1$ slipped through, the chain would break at $n=2$. Always test small values first to find the right starting point.

Example 4: divisibility

Claim. For all $n \ge 0$, $3 \mid (4^n - 1)$ (that is, $4^n - 1$ is divisible by 3).

Proof. Let $P(n)$ be "$3 \mid (4^n - 1)$."

Base case ($n=0$): $4^0 - 1 = 0$, and $3 \mid 0$. So $P(0)$ holds.

Inductive step: assume $P(k)$, i.e. $3 \mid (4^k - 1)$, so $4^k - 1 = 3m$ for some integer $m$ (this is the definition of divisibility from Chapter 4). Then $$4^{k+1} - 1 = 4 \cdot 4^k - 1 = 4(4^k - 1) + 3 = 4(3m) + 3 = 3(4m + 1).$$ Since $4m+1$ is an integer, $3 \mid (4^{k+1}-1)$, which is $P(k+1)$. By induction, $P(n)$ holds for all $n \ge 0$. $\blacksquare$

🔗 Connection. Notice we used the precise definition of "divides" — "$a \mid b$ means $b = a m$ for some integer $m$" — exactly as Chapter 4 insisted. Divisibility proofs almost always go: unpack the definition into an equation, do algebra, repackage into the definition. You'll use this move constantly in Part IV when we build RSA.

Example 5: a geometric sum (why doubling an array is cheap)

Claim. For all $n \ge 0$, $\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$.

The strategy first. The same peel-off engine, but watch the exponent bookkeeping: going from $k$ to $k+1$ the new term is $2^{k+1}$, and the small miracle is that adding it to $2^{k+1}-1$ doubles the leading power.

Proof. Let $P(n)$ be $\sum_{i=0}^{n} 2^i = 2^{n+1}-1$.

Base case ($n=0$): the left side is $2^0 = 1$; the right side is $2^{1}-1 = 1$. They match.

Inductive step: assume $\sum_{i=0}^{k} 2^i = 2^{k+1}-1$. Then $$\sum_{i=0}^{k+1} 2^i = \left(\sum_{i=0}^{k} 2^i\right) + 2^{k+1} = (2^{k+1}-1) + 2^{k+1} = 2\cdot 2^{k+1} - 1 = 2^{k+2}-1,$$ which is $P(k+1)$. By induction, the identity holds for all $n \ge 0$. $\blacksquare$

🔗 Connection. This is the calculation behind the dynamic array (Python's list, C++'s vector). When the array fills, it doubles its capacity, copying everything over. Growing to capacity $2^{n}$ by doubling costs $1 + 2 + 4 + \dots + 2^{n-1} = 2^{n}-1$ copies in total — less than the final size itself. That sum, which we just proved, is why appending to a dynamic array is $O(1)$ on average even though the occasional append triggers an expensive resize. We will return to this "amortized" reasoning in Chapter 14.

Example 6: an inequality whose base case hides

Claim. For all $n \ge 4$, $n! > 2^n$.

The strategy first. Test small values: $3! = 6 < 8 = 2^3$, but $4! = 24 > 16 = 2^4$. So the claim begins at $n = 4$ — once again, find the base case rather than assume it. In the step, advancing from $n!$ to $(n+1)!$ multiplies by $n+1$, while $2^n$ to $2^{n+1}$ multiplies by only $2$; since $n+1 > 2$ for $n \ge 4$, the factorial pulls ahead and stays ahead.

Proof. Let $P(n)$ be $n! > 2^n$, for $n \ge 4$.

Base case ($n=4$): $4! = 24 > 16 = 2^4$. So $P(4)$ holds.

Inductive step: assume $k! > 2^k$ for some $k \ge 4$. Then $$(k+1)! = (k+1)\cdot k! > (k+1)\cdot 2^k > 2\cdot 2^k = 2^{k+1},$$ where the first inequality is the inductive hypothesis and the second uses $k+1 > 2$ (true since $k \ge 4$). So $P(k+1)$ holds, and by induction $n! > 2^n$ for all $n \ge 4$. $\blacksquare$

🔄 Check Your Understanding 1. In Example 1's inductive step, exactly where did we use the inductive hypothesis? 2. Why did Example 3 need a base case of 5 instead of 1? 3. In Example 4, what would go wrong if we tried a base case of $n=1$ instead of $n=0$? (Trick question.)

Answers

1. When we replaced $\sum_{i=1}^{k} i$ with $\frac{k(k+1)}{2}$. 2. The claim $2^n > n^2$ is false for $n = 2, 3, 4$; it only becomes (and stays) true at $n=5$, so that's where the chain must start.
2. Nothing goes wrong — $P(1)$ is also true ($3 \mid 3$), so $n=1$ would be a valid base case too; we just chose the smallest natural number where the claim makes sense.

6.4 Induction and recursion: two sides of one coin

This is the section that makes induction matter to you as a programmer. Recursion and induction are the same idea pointed in opposite directions. Recursion builds a solution for $n$ from the solution for $n-1$; induction proves the solution for $n$ correct from the solution for $n-1$. The base case of your recursion is the base case of your proof. The recursive call is the inductive hypothesis.

Let's make it concrete with our running example for this book: the Fibonacci numbers, defined by $$F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2} \ \text{ for } n \ge 2.$$ We'll return to Fibonacci again and again — to solve its recurrence in closed form (Chapter 18), to compute it in $O(\log n)$ time (Chapter 19), and even to analyze it probabilistically. Here we use it to practice induction.

Claim. For all $n \ge 1$, $\displaystyle\sum_{i=1}^{n} F_i = F_{n+2} - 1.$ (The sum of the first $n$ Fibonacci numbers is two steps ahead, minus one.)

The strategy first. Same engine as a summation proof — peel off the last term — but now "the algebra" uses the defining recurrence $F_{k+3} = F_{k+2} + F_{k+1}$ to recombine terms. Whenever Fibonacci appears in a proof, the recurrence is the tool that lets you simplify.

Proof. Let $P(n)$ be $\sum_{i=1}^{n} F_i = F_{n+2} - 1$.

Base case ($n=1$): the left side is $F_1 = 1$; the right side is $F_3 - 1$. Since $F_2 = 1$ and $F_3 = F_2 + F_1 = 2$, the right side is $2 - 1 = 1$. They match.

Inductive step: assume $P(k)$: $\sum_{i=1}^{k} F_i = F_{k+2} - 1$. Then $$\sum_{i=1}^{k+1} F_i = \left(\sum_{i=1}^{k} F_i\right) + F_{k+1} = (F_{k+2} - 1) + F_{k+1}.$$ By the Fibonacci recurrence, $F_{k+1} + F_{k+2} = F_{k+3}$, so the right side equals $F_{k+3} - 1$, which is exactly $P(k+1)$. By induction, $P(n)$ holds for all $n \ge 1$. $\blacksquare$

Now the payoff: proving a recursive program correct. Consider this implementation of the sum $1 + 2 + \dots + n$:

def triangle(n):
    """Return 1 + 2 + ... + n for n >= 0. (triangle(0) == 0.)"""
    if n == 0:
        return 0
    return n + triangle(n - 1)

print(triangle(5))
# Expected output:
# 15

Claim. For every integer $n \ge 0$, triangle(n) returns $\frac{n(n+1)}{2}$.

Proof (by induction on $n$). Let $P(n)$ be "triangle(n) returns $\frac{n(n+1)}{2}$."

Base case ($n=0$): the code hits the if n == 0 branch and returns $0$, and $\frac{0 \cdot 1}{2} = 0$. So $P(0)$ holds.

Inductive step: assume $P(k)$ — that triangle(k) returns $\frac{k(k+1)}{2}$. For input $k+1 \ge 1$, the function skips the base case and returns (k+1) + triangle(k). By the inductive hypothesis the recursive call returns $\frac{k(k+1)}{2}$, so the function returns $$(k+1) + \frac{k(k+1)}{2} = \frac{2(k+1) + k(k+1)}{2} = \frac{(k+1)(k+2)}{2},$$ which is the formula at $n = k+1$. So $P(k+1)$ holds. By induction, triangle(n) is correct for all $n \ge 0$. $\blacksquare$

💡 Intuition: The recursive call is the inductive hypothesis. We didn't re-trace the recursion; we assumed it works on the smaller input — exactly what the inductive hypothesis grants us. This is why induction is the natural language for reasoning about recursion: the proof has the same shape as the code.

🔄 Check Your Understanding 1. In the correctness proof, what plays the role of the inductive hypothesis? 2. The function requires $n \ge 0$. What happens to both the code and the proof if someone calls triangle(-1)?

Answers

1. The assumption that the recursive call triangle(k) returns the correct value $\frac{k(k+1)}{2}$.
2. The code recurses forever (it never reaches the base case), and the proof doesn't apply because our claim was only made for $n \ge 0$ — the induction starts at 0 and goes up, never down. A robust implementation would guard against negative input.

6.5 Loop invariants: induction for iterative code

Recursion makes induction obvious. But most code uses loops, and loops hide their induction. The tool that exposes it is the loop invariant: a statement that is true before the loop starts and stays true after every iteration. Proving a loop correct is proving an invariant by induction on the number of iterations.

Consider an iterative version of the same sum:

def triangle_iter(n):
    """Return 1 + 2 + ... + n for n >= 0, iteratively."""
    total = 0
    i = 0
    while i < n:
        i = i + 1
        total = total + i
    return total

print(triangle_iter(5))
# Expected output:
# 15

Invariant. At the top of the loop test, $\text{total} = \frac{i(i+1)}{2}$. In words: total always holds the sum $1 + \dots + i$ for the current value of i.

To use an invariant we check three things — and the first two are precisely a base case and an inductive step.

• Initialization (base case). Before the first test, $i = 0$ and $\text{total} = 0$. The invariant says $\text{total}$ should be $\frac{0 \cdot 1}{2} = 0$. It holds.
• Maintenance (inductive step). Suppose the invariant holds at the top of some iteration, so $\text{total} = \frac{i(i+1)}{2}$, and suppose the loop body runs (so $i < n$). The body sets $i' = i + 1$ and then $\text{total}' = \text{total} + i' = \frac{i(i+1)}{2} + (i+1) = \frac{(i+1)(i+2)}{2} = \frac{i'(i'+1)}{2}$. So the invariant holds again at the next test, now for $i'$.
• Termination. The loop ends when $i \ge n$; since $i$ increases by 1 each pass starting from 0 and never overshoots, it ends with $i = n$. Plugging into the invariant, $\text{total} = \frac{n(n+1)}{2}$ — the value we return.

By induction on the number of iterations, the invariant holds every time the test is evaluated; combined with termination, the function returns $\frac{n(n+1)}{2}$. $\blacksquare$

🔗 Connection. This is not a toy. Loop invariants are how real systems are verified — from the binary-search bug that lurked in production libraries for years (an invariant about the search range would have caught it) to formally verified code in aerospace and cryptography. When you can state the invariant of a loop, you understand the loop. We'll lean on invariants again when we prove Dijkstra's algorithm correct in Chapter 29 and the greedy MST algorithms in Chapter 32.

A second invariant makes the pattern stick — and shows that an invariant need not be a formula. Here is a loop that finds the largest value in a non-empty list:

def maximum(values):
    """Return the largest element of a non-empty list."""
    best = values[0]
    i = 1
    while i < len(values):
        if values[i] > best:
            best = values[i]
        i = i + 1
    return best

print(maximum([3, 7, 2, 9, 4]))
# Expected output:
# 9

Invariant. At the top of the loop test, best equals the maximum of the first i elements, values[0..i-1].

• Initialization. Before the loop, $i = 1$ and best is values[0], which is the maximum of the first one element. The invariant holds.
• Maintenance. Suppose best is the maximum of the first $i$ elements and the body runs. It compares values[i] against best, keeps whichever is larger, and increments $i$. The new best is therefore the maximum of the first $i+1$ elements — the invariant again, now for $i+1$.
• Termination. The loop ends with $i = \texttt{len(values)}$, so best is the maximum of all the elements, which is exactly what we return. $\blacksquare$

Notice there was no algebraic formula this time. The invariant is a statement about the program's variables — "best is the max so far" — not an identity. That is the general shape of a loop proof: name the property the loop keeps true, show it holds at entry and survives one iteration, and read off the result at exit.

🐛 Find the Error. A student writes the invariant for triangle_iter as "$\text{total} = \frac{i(i+1)}{2}$ at the end of the loop body" and then claims initialization holds because $\text{total} = 0$ before the loop. What is wrong with this?

Answer

The placement is inconsistent. An invariant must be stated at a fixed program point and checked there every time. If the invariant is "at the end of the loop body," then there is no "initialization" before the body has ever run — initialization should be checked at the top of the loop test. Stating the invariant at the loop test (as we did) makes initialization, maintenance, and termination line up cleanly. Sloppiness about where the invariant holds is the single most common loop-proof error.

6.6 When induction goes wrong

Because induction is mechanical, it's easy to run the machinery without the parts engaging — to write something that looks like an induction proof but proves nothing. The two failure modes are a broken base case and a broken inductive step. The most famous example breaks the second in a beautifully subtle way.

🐛 Find the Error: "All horses are the same color."

Claim (false). In any group of $n$ horses, all the horses are the same color.

"Proof." Let $P(n)$ be the claim for groups of size $n$. Base case ($n=1$): a single horse is trivially the same color as itself. ✓ Inductive step: assume any group of $k$ horses is all one color. Take a group of $k+1$ horses, lined up. The first $k$ of them form a group of size $k$, so by the hypothesis they're all one color. The last $k$ of them also form a group of size $k$, so they're all one color too. The two groups overlap, so all $k+1$ horses share that one color. ✓ By induction, all horses are the same color. $\blacksquare$(?)

Something is obviously wrong — so where exactly does the proof fail?

Take a minute on it before reading the resolution; locating the flaw is the real skill.

Resolution. The inductive step secretly assumes the two groups of size $k$ overlap. For $k+1 = 2$, the "first $k$" is just horse 1 and the "last $k$" is just horse 2 — two groups of size 1 that do not overlap. So the step $P(1) \rightarrow P(2)$ is exactly the one that fails, and the chain breaks at the very first link. The base case is fine; the inductive step is valid for $k \ge 2$ but not for $k = 1$, and induction needs it for every $k \ge$ base. One missing link and the whole infinite chain falls apart.

The lesson is general and worth internalizing:

⚠️ Common Pitfall: An inductive step must hold for every $k$ from the base case onward — not "for typical $k$" or "for large enough $k$." Always ask: does my argument secretly require $k$ to be big enough (an overlap, a term to peel off, a value to be positive)? If so, either the base case must be raised to cover the gap, or the proof is broken. The horses fail because the overlap argument needs $k \ge 2$ while the chain needs $k \ge 1$.

Other failure modes to watch for, collected for your exercises:

• A false or skipped base case. If $P(\text{start})$ is false (or you never check it), a perfectly valid inductive step proves nothing — you've shown each domino topples the next, but never pushed the first.
• Using the hypothesis on a case you haven't established. Ordinary induction lets you assume $P(k)$ to prove $P(k+1)$ — one step back. If your argument needs to assume $P(k-1)$ and $P(k)$ (as Fibonacci-style arguments do), you need strong induction, the subject of Chapter 7.

🔄 Check Your Understanding 1. In a flawed proof with a true inductive step but an unchecked base case, is the conclusion necessarily false? 2. What single change to the horse "proof" would you have to make for it to actually work — and why is that change impossible here?

Answers

1. Not necessarily false — but unproven. The argument establishes nothing about whether the statement is true; it might be true for other reasons, or false. An induction with a gap is simply not a proof. 2. You would need the overlap argument to hold at $k=1$ (proving $P(1) \rightarrow P(2)$), which is impossible because two single-horse groups never overlap. There is no repair because the claim is genuinely false.

Project Checkpoint: an inductive-claim tester for the Toolkit

Theme four of this book is that computation and proof are complementary: code can test a conjecture on many cases (cheap, fallible), and a proof settles all cases (expensive, certain). Let's add a small tool to our growing dmtoolkit that embodies the testing half — a function that checks a claimed identity for many values of $n$. It won't prove anything, but it's exactly what you'd run before attempting a proof, to make sure the claim is even worth proving.

Create dmtoolkit/recurrences.py (we'll grow this module in Chapters 18–19) and add:

def check_identity(lhs, rhs, upto=20, start=0):
    """Test whether lhs(n) == rhs(n) for n in [start, upto].
    Returns the first n where they differ, or None if all agree.
    This TESTS a conjecture; it does not prove it (see Chapter 6)."""
    for n in range(start, upto + 1):
        if lhs(n) != rhs(n):
            return n
    return None

def fib(n):
    """Naive recursive Fibonacci (F_0 = 0, F_1 = 1). Chapter 19 makes this fast."""
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

# Test the identity we proved in 6.4: sum of first n Fibonacci numbers == F(n+2) - 1
lhs = lambda n: sum(fib(i) for i in range(1, n + 1))
rhs = lambda n: fib(n + 2) - 1
print(check_identity(lhs, rhs, upto=15, start=1))
# Expected output:
# None

The output None means "no counterexample found up to $n=15$" — encouraging evidence, and indeed we proved this identity in section 6.4, so we know it holds for all $n$. Try pointing check_identity at a false claim (say, $\sum_{i=1}^n i = n^2$) and watch it return the first $n$ where the two sides diverge. That returned number is a counterexample — the thing that, by Chapter 5, single-handedly disproves a universal claim. Your Toolkit can now both suggest identities worth proving and refute ones that aren't.

Toolkit so far: logic.py (Chapters 1–3) and now the beginnings of recurrences.py. By the capstone you'll have a complete discrete-math library — and the judgment to know when its "no counterexample found" is reassurance and when you need a proof.

Summary

Mathematical induction proves a statement $P(n)$ for all integers $n \ge \text{start}$ from two finite pieces of work. The essential facts to carry forward:

• The inductive step proves an implication; assuming $P(k)$ to prove $P(k+1)$ is not circular.
• The base case must be where the claim actually starts (test small values to find it).
• The inductive step must hold for every $k$ from the base onward — a single missing link (the horses at $k=1$) breaks the whole chain.
• Recursion and induction are the same shape: base case ↔ base case, recursive call ↔ inductive hypothesis. To reason about iterative code, use a loop invariant (initialization = base case, maintenance = inductive step, plus termination).
• The summation engine is "peel off the last term, then apply the hypothesis." The divisibility engine is "unpack the definition, do algebra, repackage."

Induction is the workhorse of the rest of this book. We'll use it on recurrences (Chapters 18–19), trees (Chapter 31), and algorithm correctness throughout Part V.

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 5) The horse-coloring "proof" fails at one specific implication. Which proof technique from Chapter 5 most directly disproves the all-horses claim, and what is the one-line counterexample?
2. (Ch. 5) Restate the principle of induction's justification as a proof by contradiction using a "smallest counterexample." Which earlier technique is that?
3. (Ch. 4) In Example 4 we wrote "$3 \mid x$ means $x = 3m$ for some integer $m$." Which kind of statement is "$a \mid b$" — and why does unpacking the definition matter in a direct proof?
4. (Ch. 4) Is the inductive step $P(k) \rightarrow P(k+1)$ proved by direct proof or by contraposition in Example 1? Could it have been done the other way?

Answers

1. A counterexample (Chapter 5's disproof of a universal statement): two horses of different colors — a group of size 2 that isn't monochromatic. 2. Assume some $P(n)$ fails; by well-ordering there is a smallest such $n$; it isn't the base case, so $P(n-1)$ holds, but the inductive step then forces $P(n)$ — contradiction. That's proof by contradiction. 3. "$a \mid b$" is an existential statement ("there exists an integer $m$ with $b = am$"); unpacking it turns a relationship into an equation you can do algebra with. 4. Direct proof — we assumed $P(k)$ and derived $P(k+1)$ by a chain of equalities. A contrapositive version would be awkward and unnecessary here.

What's Next

Ordinary induction lets you assume one case back — $P(k)$ — to prove $P(k+1)$. But some arguments, including the most natural proofs about Fibonacci numbers and about factoring integers into primes, need to assume all previous cases at once. That stronger tool is strong induction, and it comes with a close cousin, the well-ordering principle, that finally explains why induction works at all. We'll also learn to define objects recursively — sequences, sets, and the tree structures that power half of computer science — and prove things about them by structural induction. That's Chapter 7.