Mathematical Induction

Mathematical induction is the backbone of essentially all reasoning about discretely-indexed structures. In computer science, it justifies the correctness of recursive algorithms and loop invariants: proving a loop invariant holds after each iteration is a direct instance of the inductive step, and induction underlies proofs of program correctness, termination arguments, and the analysis of recursively-defined data structures such as trees and lists. In combinatorics, virtually every identity involving binomial coefficients, Fibonacci-type recurrences, or partition counts is established by induction, often paired with recursively defined sequences. In number theory, induction proves divisibility results (as in the worked example above), properties of the Euclidean algorithm, and forms the scaffolding for proofs by Strong Induction of results like the existence part of the Fundamental Theorem of Arithmetic. In formal logic and model theory, induction on the structure of formulas (structural induction) is used to prove that every well-formed formula has some syntactic property, generalizing numerical induction to inductively defined sets. In cryptography, security proofs for protocols built from iterated hash constructions or recursive commitment schemes often use induction to propagate a security guarantee across rounds. In numerical analysis and engineering, induction justifies error bounds that compound predictably across iterative numerical schemes, and stability proofs for discrete-time control systems frequently proceed by induction on the time step.

Ask the tutor: Can you show me how the inductive step changes when I switch from ordinary induction to strong induction, using a concrete recurrence?

Picture the natural numbers as an infinite row of dominoes, one for each $n \ge n_0$, standing on end. The base case is the physical act of tipping over the very first domino, $n_0$. The inductive step is the guarantee, built into the spacing and height of every domino, that if domino $k$ falls, then domino $k+1$ falls too — for every $k$ in the row, not just one particular one. Once both facts are established, you know every single domino falls, all the way out to infinity, even though you personally only pushed the first one and only verified the "falls-implies-falls" mechanism in the abstract, once. The crucial subtlety, and the source of nearly every student error, is that the inductive step does not ask you to prove $P(k+1)$ from nothing. It asks you to prove the conditional statement $P(k) \Rightarrow P(k+1)$, for an arbitrary $k$, using $P(k)$ as an assumption you are entitled to use. You never verify $P(k)$ itself inside the inductive step — that verification is handled by the whole inductive chain reaching back to the base case. The proof of the inductive step is a Direct Proof of a universally quantified conditional, exactly the kind of proof studied for quantifiers in general: fix an arbitrary $k \ge n_0$, assume the antecedent $P(k)$, and derive the consequent $P(k+1)$.

The domino picture is intuitive but the real justification is a theorem, and it rests on a genuinely different-looking axiom about $\mathbb{N}$: every nonempty subset of $\mathbb{N}$ has a least element. This is the Well-Ordering Principle, and the theorem below shows induction is a logical consequence of it — induction is not an independent leap of faith, but a provable feature of the structure of $\mathbb{N}$.

Note the proof technique by name: proof by contradiction combined with the Well-Ordering Principle, applied to the set of counterexamples. It is not circular — well-ordering is an independent structural axiom about $\mathbb{N}$ (or a theorem from the Peano axioms, depending on foundational setup), and nowhere does the argument assume the very induction principle it is proving.

Example 1 — a summation identity with a non-symmetric closed form. Claim: for every integer $n \ge 1$,

Proof by induction on $n$, base case $n_0 = 1$.

Base case ($n=1$). The left side is $\sum_{i=1}^1 i(i+1) = 1 \cdot 2 = 2$. The right side is $\frac{1 \cdot 2 \cdot 3}{3} = \frac{6}{3} = 2$. Both sides equal $2$, so the base case holds.

Inductive step. Fix an arbitrary integer $k \ge 1$ and assume the inductive hypothesis

We must show $P(k+1)$: that $\displaystyle\sum_{i=1}^{k+1} i(i+1) = \frac{(k+1)(k+2)(k+3)}{3}$. Starting from the left side of $P(k+1)$ and splitting off the last term:

By the inductive hypothesis, the bracketed sum equals $\frac{k(k+1)(k+2)}{3}$, so

Factor out the common factor $(k+1)(k+2)$:

This is exactly the right side of $P(k+1)$. Since $k \ge 1$ was arbitrary, this proves $\forall k \ge 1\,(P(k) \Rightarrow P(k+1))$. By the Principle of Mathematical Induction (base case $n_0=1$ verified, inductive step verified for all $k \ge 1$), the identity holds for all integers $n \ge 1$. $\blacksquare$ Check with $n = 4$ directly, as a numerical sanity check (not part of the proof, just verification): left side $= 1\cdot2 + 2\cdot3 + 3\cdot4 + 4\cdot5 = 2+6+12+20 = 40$; right side $= \frac{4\cdot5\cdot6}{3} = \frac{120}{3} = 40$. They agree.

Example 2 — a divisibility statement (asymmetric base point). Claim: for every integer $n \ge 0$, $7$ divides $3^{2n+1} + 2^{n+2}$. Proof by induction on $n$, base case $n_0 = 0$.

Base case ($n = 0$). Compute $3^{2(0)+1} + 2^{0+2} = 3^1 + 2^2 = 3 + 4 = 7$. Since $7 \mid 7$, $P(0)$ holds.

Inductive step. Fix an arbitrary integer $k \ge 0$ and assume the inductive hypothesis: $7 \mid \left(3^{2k+1} + 2^{k+2}\right)$, i.e. there exists an integer $m$ with

We must show $P(k+1)$: that $7 \mid \left(3^{2(k+1)+1} + 2^{(k+1)+2}\right) = 3^{2k+3} + 2^{k+3}$. Rewrite the target expression to expose the inductive hypothesis. Since $3^{2k+3} = 3^2 \cdot 3^{2k+1} = 9 \cdot 3^{2k+1}$ and $2^{k+3} = 2 \cdot 2^{k+2}$:

Write $9 = 7 + 2$ to isolate a multiple of the inductive-hypothesis expression:

By the inductive hypothesis, $3^{2k+1} + 2^{k+2} = 7m$, so

This exhibits $3^{2k+3} + 2^{k+3}$ as $7$ times the integer $3^{2k+1} + 2m$, so $7 \mid \left(3^{2k+3}+2^{k+3}\right)$, i.e. $P(k+1)$ holds. Since $k \ge 0$ was arbitrary, $\forall k \ge 0\,(P(k)\Rightarrow P(k+1))$ is established. By induction, $7 \mid (3^{2n+1}+2^{n+2})$ for all integers $n \ge 0$. $\blacksquare$ Numerical check at $n=2$: $3^5 + 2^4 = 243 + 16 = 259 = 7 \times 37$. Indeed divisible by $7$.