Mathematical Induction¶

Definition¶

Let $P(n)$ be a statement about a natural number $n$ . The principle of mathematical induction says: if

base case: $P(0)$ is true, and
inductive step: for every natural number $k$ , $P(k)$ implies $P(k+1)$ $1)$ ,

then $P(n)$ is true for every $n\in\mathbb{N}$ $N$ .

This is the fifth Peano axiom, where the successor $S(k)$ is written $k+1$ once addition is available. A proof by induction checks the base case and proves the inductive step. In the step, $k$ is an arbitrary but fixed natural number, and the assumption that $P(k)$ holds is called the inductive hypothesis.

Interpretation¶

Induction works like a row of dominoes. The base case knocks over the first domino. The inductive step says that whichever domino falls, it knocks over the next one. Together they make every domino fall: $P(0)$ gives $P(1)$ , $P(1)$ gives $P(2)$ , and so on through all of $\mathbb{N}$ .

A row of dominoes labelled P(0), P(1), P(2), P(3), then P(k) and P(k+1); a green push arrow marks the base case and blue arcs from each domino to the next mark the inductive step.

The green arrow is the base case: it pushes $P(0)$ . Each blue arc is one instance of the inductive step, and the arc from $P(k)$ to $P(k+1)$ stands for all of them at once, because $k$ is arbitrary. The green line underneath is the conclusion: $P(n)$ holds for every natural number $n$ .

Neither part works alone. A step without a base case is a chain of dominoes that nobody pushes, and a base case without a step knocks over only the first domino. Checking $P(0),P(1),\ldots,P(40)$ one by one is still not a proof for every $n$ .

The inductive step proves an implication. It does not claim that $P(k)$ is true; it shows that $P(k+1)$ would follow if $P(k)$ were true. Assuming " $P(n)$ for every $n$ " in the step would assume the very statement to be proved.

Key Results¶

Set form. If $A\subseteq\mathbb{N}$ contains $0$ , and $k+1\in A$ whenever $k\in A$ $A$ , then $A=\mathbb{N}$ $N$ . Apply the principle to the statement " $n \in$ $n\in A$ $A$ ".
Starting at $n_0$ . If $P(n_0)$ is true and $P(k)$ implies $P(k+1)$ for every integer $k\ge n_0$ $n_{0}$ , then $P(n)$ is true for every integer $n\ge n_0$ $n_{0}$ . Apply the principle to $Q(m)$ : " $P (n_{0} +$ $P(n_0+m)$ $m)$ ". Statements about positive integers start at $n_0=1$ $1$ .
Both parts are needed. For $P(n)$ : " $n^{2} +$ $n^2+n+1$ is even", the step holds, since $(k+1)^2+(k+1)+1=(k^2+k+1)+2(k+1)$ $1)$ . But $P(0)$ fails, and in fact $n^2+n+1$ is odd for every $n$ . For $P(n)$ : " $n^{2} -$ $n^2-n+41$ is prime", the cases $n=0,1,\ldots,40$ are all true, but $n=41$ gives $41^2$ .
Recursion and induction go together. The factorial is defined recursively: $0!=1$ $1$ , and $(k+1)!=(k+1)\times k!$ for every $k\in\mathbb{N}$ $N$ . Statements about a recursively defined quantity are proved by induction: the value at $0$ settles the base case, and the rule from $k$ to $k+1$ drives the step. Powers ( $m^{0} =$ $m^0=1$ $1$ , $m^{k+1}=m^k m$ $m^{k} m$ ) and multiplication on $\mathbb{N}$ ( $0 \cdot$ $0\cdot m=0$ $0$ , $S(n)\cdot m=n\cdot m+m$ $m$ ) can be built the same way.
Several variables. For a statement about $n$ and $m$ , such as $n\cdot S(m)=n\cdot m+n$ $n$ , fix $m$ and induct on $n$ : the base case is $n=0$ for that $m$ , and the step goes from $n$ to $S(n)$ with the same $m$ .

Examples¶

A sum formula. For every $n\in\mathbb{N}$ $N$ ,

$0+1+2+\cdots+n=\frac{n(n+1)}{2}.$

Base case: for $n=0$ both sides are $0$ . Inductive step: assume $0+1+\cdots+k=k(k+1)/2$ for some $k\in\mathbb{N}$ $N$ . Then

$0+1+\cdots+k+(k+1) =\frac{k(k+1)}{2}+(k+1) =\frac{(k+1)(k+2)}{2},$

which is the formula for $n=k+1$ $1$ . This is the arithmetic series $1+2+\cdots+n$ $n$ .
Odd numbers. $1+3+\cdots+(2n-1)=n^2$ for every integer $n\ge1$ $1$ . For $n=1$ $1$ , $1=1^2$ $1^{2}$ . If $1+3+\cdots+(2k-1)=k^2$ $k^{2}$ , adding the next odd number $2k+1$ gives $k^2+2k+1=(k+1)^2$ $1)^{2}$ .
Divisibility. $3^{2n}-1$ is divisible by $8$ for every integer $n\ge1$ $1$ . For $n=1$ $1$ , $3^2-1=8$ $8$ . If $3^{2k}-1=8m$ for an integer $m$ , then

$\begin{aligned} 3^{2(k+1)}-1&=9\cdot3^{2k}-1\\ &=9(3^{2k}-1)+8\\ &=8(9m+1). \end{aligned}$
An inequality. $n+1\le2^n$ for every $n\in\mathbb{N}$ $N$ . For $n=0$ $0$ , $1\le1$ $1$ . If $k+1\le2^k$ $2^{k}$ , then, since $1\le2^k$ $2^{k}$ ,

$(k+1)+1\le2^k+2^k=2^{k+1}.$
From a recursive definition. With multiplication defined by $0\cdot m=0$ and $S(n)\cdot m=n\cdot m+m$ $m$ , the rule $n\cdot0=0$ needs a proof, because $0$ stands on the right. For $n=0$ it is the definition. If $n\cdot0=0$ $0$ , then $S(n)\cdot0=n\cdot0+0=0$ $0$ .

Prerequisites¶

Sources¶

Math I: Calculus · Lecture 1 (frames "Peano axiom 5: mathematical induction", "Proof by induction: example" and "Mathematical induction is like the domino effect")
Math I: Calculus · Tutorial 1

Aliases: proof by induction, principle of mathematical induction, induction proof Keywords: base case, inductive step, inductive hypothesis, induction hypothesis, domino effect, Peano axiom 5 Symbols: element of, natural numbers, subset

Last updated: 27 October 2026 11:52