The Principle of Mathematical Induction

Statement of the Principle

Let $P(n)$ be a mathematical statement involving a natural number $n$. The Principle of Mathematical Induction says $P(n)$ is true for every natural number $n$ provided both of the following hold:

1. Base case (basis step): $P(1)$ is true.
2. Inductive step: for every positive integer $k$, if $P(k)$ is true then $P(k+1)$ is also true, i.e. $P(k) \Rightarrow P(k+1)$.

When both conditions are verified, we conclude $P(n)$ is true for all $n \in \mathbb{N}$.

• The base case is a single, concrete check — confirm the statement for the starting value of $n$ (usually $n=1$, though a statement that only holds from a later point, say $n \ge 4$, instead has its base case at $P(4)$).
• The inductive step is conditional: it does not assert that $P(k)$ is actually true. It only proves the implication "if $P(k)$ holds, then $P(k+1)$ holds." The assumption "$P(k)$ is true," made purely to carry out this argument, is called the inductive hypothesis.

Together, the base case supplies the first domino, and the inductive step supplies the falling-tile rule that carries truth indefinitely forward — exactly the mechanism motivated in Section 4.2.

---

Worked Illustration: Sum of the First $n$ Odd Numbers

Observe the pattern:

This suggests the general claim

Base case. $P(1)$ says $1 = 1^2$, which is true.

Inductive step. Assume the inductive hypothesis $P(k)$ holds, i.e.

We must show $P(k+1)$ follows. Add the next odd number, $2(k+1)-1 = 2k+1$, to both sides of (1): …