Discrete Math and Proof

Proof by induction and recursion

Proving a statement for every natural number

~11 minLesson 11 of 19Written by Claude Opus 4.8

Line up a million dominoes. You can't push each one - but you don't have to. Knock the first, and guarantee that every domino topples its neighbour, and all million fall from those two facts alone. That is mathematical induction: a finite argument that certifies infinitely many cases at once.

Two facts, infinitely many cases

To prove a statement

P (n)

for every integer

n \geq 1

, you never check them one by one. You prove exactly two things. Base case:

P (1)

is true - the first domino falls. Inductive step: whenever

P (k)

is true,

P (k + 1)

is true too - each domino, as it falls, knocks the next. Chain those and the whole line goes down.

Topple the dominoes, prove the sum

We'll prove the classic identity $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ . Step 1: knock the base case. Step 2: drag the three algebra pieces into the order that turns $P (k)$ into $P (k + 1)$ - until you do, no domino past the first is allowed to fall. Step 3: scrub $n$ and watch the chain cascade, with the running sum matching the formula at every stop.

Domino induction: knock the base case, arrange the chain to prove the step, then scrub n and watch the whole line cascade.

No dominoes down yet - knock the base case to begin.

topple up to n = 0

Start by knocking the first domino - the base case P(1).

claim

P (n) : 1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}

base

P (1) : 1 = \frac{1 \cdot 2}{2} = 1 ✓

assume

P (k) : 1 + 2 + \dots + k = \frac{k ( k + 1 )}{2}

(the inductive hypothesis)

step - arrange the chain

Drag the three pieces left-to-right so each equals the one before it, ending at $P (k + 1)$ :

arrange the three pieces to unlock the rest of the chain →

therefore

P (k) \Rightarrow P (k + 1)

, so by induction

P (n)

holds for all

n \geq 1. ■

What the two gates are really teaching

Notice you can't reach domino 3 by force - only by proving the rule. That is the whole discipline of induction: the base case gives you a place to stand, the inductive step is a reusable machine that turns any true case into the next one, and running the machine down the line covers every

n

. The dominoes are just the machine made visible.

The three moving parts, named

Base case - prove $P (1)$ (or whatever the smallest $n$ is) directly. Without it, nothing starts; a rule with no first domino topples nothing.
Inductive hypothesis - the assumption that $P (k)$ holds for some arbitrary $k$ . You are not assuming the conclusion; you are assuming one case to build the next.
Inductive step - prove the implication $P (k) \Rightarrow P (k + 1)$ . This is the domino-knocks-its-neighbour guarantee, and it must hold for every $k$ .

The template, formally

The principle of mathematical induction is the single rule of inference:

base P (1) \land inductive step (\forall k \geq 1, P (k) \Rightarrow P (k + 1)) ⟹ \forall n \geq 1, P (n) .

Every induction proof is that shape filled in. In our demo the step is the algebra you dragged: $\frac{k ( k + 1 )}{2} + (k + 1) = \frac{k ( k + 1 ) + 2 ( k + 1 )}{2} = \frac{( k + 1 ) ( k + 2 )}{2}$ , which is exactly $P (k + 1)$ 's right-hand side.

Weak, strong, and the ground it stands on

What we just used is weak (ordinary) induction: the step may assume only $P (k)$ . Sometimes one predecessor isn't enough - proving something about $n$ needs several smaller cases (think dividing a problem in half). Then you use strong induction, whose step may assume the whole run of earlier cases at once:

(\forall k, [P (1) \land P (2) \land \dots \land P (k)] \Rightarrow P (k + 1)) ⟹ \forall n \geq 1, P (n) .

They are equally powerful - anything one proves, the other can too - but strong induction is often more convenient. Both rest on the well-ordering principle: every non-empty set of positive integers has a smallest element. If some statement had a counterexample, there would be a least counterexample - but the base case rules out the very bottom and the step manufactures it from a smaller case, so no least counterexample can exist. That contradiction is why the dominoes can't secretly leave one standing.

Recursion is induction you can run

# sum_to(n) = 1 + 2 + ... + n
def sum_to(n):
    if n == 1:                  # BASE CASE   -> P(1): stops the recursion
        return 1
    return sum_to(n - 1) + n     # INDUCTIVE STEP -> assume P(n-1), build P(n)

# Correct because: base  sum_to(1) == 1                         OK
#                 step  if sum_to(n-1) == (n-1)*n/2, then
#                       sum_to(n) == (n-1)*n/2 + n == n(n+1)/2  OK

The recursion / induction mirror

A recursive function is an inductive proof you can execute: the base case of the code is the base case of the proof, and the recursive call on a smaller input is the inductive hypothesis. The same pairing certifies a loop: a loop invariant is a

P

true before the loop (base), preserved by each iteration (step), so it still holds when the loop ends. Prove those two and the loop is correct - no matter how many times it runs.

Check yourself

Assuming P(k) as the hypothesis, the inductive step must prove that:

Knocking the first domino by hand corresponds, in a proof, to the:

Recall: what two things must every induction proof establish, and what does each guarantee?

Try to state it, then check.

Lock it in

Induction certifies $P (n)$ for every $n \geq 1$ from just two facts: the base case $P (1)$ , and the inductive step $P (k) \Rightarrow P (k + 1)$ .
The base case gives you a place to stand; the inductive step is a reusable machine that turns any true case into the next one.
The inductive hypothesis is the assumption that $P (k)$ holds - you are borrowing one case to build the next, not assuming the conclusion.
Strong induction lets the step assume the whole run $P (1) \land \dots \land P (k)$ ; it is equally powerful, and both rest on the well-ordering principle.
Recursion is induction you can run: the code's base case is the proof's base case, and the recursive call on a smaller input is the inductive hypothesis.

Primary source

Chapter 10 of Richard Hammack's Book of Proof (free, and superb) walks through weak, strong, and well-ordering with worked examples. For the CS framing - induction as the tool for loop invariants and recursion - see MIT 6.042J, Mathematics for Computer Science, whose opening lectures are built around exactly this.

Ask your teacher

Induction is how you prove that recursion and divide & conquer actually work: the base case stops the dominoes, the inductive step guarantees all the rest. Want to see a full invariant proof for a real loop, or why strong induction is the natural fit for merge sort's correctness? Ask and I'll build the follow-up.