The ninth of the Peano axioms is known as the principle of mathematical induction.
Principle of mathematical induction. If $ K $ is a set containing $ 0 $ that is closed under the successor function, then $ K $ is equal to the natural numbers $ \mathbb{N}_0 $.
We used this principle liberally in the Peano axioms exercises to prove various properties of the natural numbers.
example
For any natural number $ n $, prove that the number $ n^2 + n $ is even. (A natural number is even if and only if it can be expressed as a natural number multiplied by 2.)
We let $ K $ be the set of natural numbers satisfying the conclusion $$ K = \{ k \in \mathbb{N}_0 \mid k^2 + k \text { is even} \}. $$ We want to prove that $ K = \mathbb{N} $, and we will use the principle of mathematical induction to do so.
First we prove that $ 0 \in K $. Zero is even since $ 0 = 2 \cdot 0 $. Therefore, $ 0^2 + 0 = 0 $ is even, so $ 0 \in K $.
Next we prove that $ K $ is closed under the successor function. We need to prove: if $ k $ is in $ K $, then its successor $ k + 1 $ is also in $ K $. For any $ k \in K $, we have that $ k^2 + k $ is even, so $$ k^2 + k = 2 n $$ for some natural number $ n $. To prove that $ k + 1 \in K $, we calculate $$ \begin{align} (k + 1)^2 + (k + 1) &= (k^2 + 2k + 1) + (k + 1) \\ &= (k^2 + k) + (2k + 2) \\ &= 2n + 2k + 2 \\ &= 2(n + k + 1) \end{align} $$ and conclude that $ (k + 1)^2 + (k + 1) $ is even since it is a natural number multiplied by 2. This shows that $ k + 1 \in K $, so $ K $ is closed under the successor function.
Finally we conclude that $ K = \mathbb{N}_0 $ by the principle of mathematical induction.
Alternate characterization
A more familiar version of the principle of mathematical induction involves propositions about natural numbers.
Principle of mathematical induction. Let $ p(n) $ be a proposition about $ n \in \mathbb{N}_0 $. Suppose that
- Base case: the proposition $ p(0) $ is true;
- Inductive step: for any $ k \in \mathbb{N}_0 $, if $ p(k) $ is true, then $ p(k + 1) $ is also true.
Then $ p(n) $ is true for all $ n \in \mathbb{N}_0 $.
example
We'll prove the same example from above using this alternate characterization, that the number $ n^2 + n $ is even for any natural number $ n $.
For any natural number $ n $, let $ p(n) $ be the proposition that $ n^2 + n $ is even.
Base case. The proposition $ p(0) $ is true since $ 0^2 + 0 = 2 \cdot 0 $ is even.
Inductive step. Suppose that $ p(k) $ is true, ie, that $ k^2 + k $ is even. Then we can express $ k^2 + k $ as $ 2n $ for some natural number $ n $. We need to prove that $ p(k + 1) $ is true, ie, that $ (k + 1)^2 + (k + 1) $ is even. As before, $$ \begin{align} (k + 1)^2 + (k + 1) &= (k^2 + 2k + 1) + (k + 1) \\ &= (k^2 + k) + (2k + 2) \\ &= 2n + 2k + 2 \\ &= 2(n + k + 1) \end{align} $$ is even, so $ p(k + 1) $ is true.
By mathematical induction, since $ p(0) $ is true and $ p(k) $ implies $ p(k + 1) $ then $ p(n) $ is true for all $ n \in \mathbb{N}_0 $.
different base case
The principle of mathematical induction can also be used to prove that a proposition is true for all natural numbers above a certain threshold.
Principle of mathematical induction. Let $ p(n) $ be a proposition about $ n \in \mathbb{N}_c = \{ c, c + 1, c + 2, \dots \} $. Suppose that
- Base case: the proposition $ p(c) $ is true;
- Inductive step. for any $ k \in \mathbb{N}_c $, if $ p(k) $ is true, then $ p(k + 1) $ is also true.
Then $ p(n) $ is true for all $ n \in \mathbb{N}_c $.
example
For any natural number $ n \geq 1 $, prove that the sum of the first $ n $ odd natural numbers is equal to $ n^2 $.
For $ n \in \mathbb{N}_1 $, let $ p(n) $ be the proposition that the sum of the first $ n $ odd natural numbers is equal to $ n^2 $. For example, here are the first four propositions. $$ \begin{align} {}p(1) &: 1 = 1^2 \\ p(2) &: 1 + 3 = 2^2 \\ p(3) &: 1 + 3 + 5 = 3^2 \\ p(4) &: 1 + 3 + 5 + 7 = 4^2 \end{align} $$
To express the equation for $ p(n) $ in general, we need to know what the $ n^\text{th} $ odd number is. Note that $$ \begin{align} 1^\text{st} \text{ odd number: } & 1 = 2(1) - 1 \\ 2^\text{nd} \text{ odd number: } & 3 = 2(2) - 1 \\ 3^\text{rd} \text{ odd number: } & 5 = 2(3) - 1 \\ 4^\text{th} \text{ odd number: } & 7 = 2(4) - 1 \\ \end{align} $$ From this pattern, we conclude that the $ n^\text{th} $ odd number is $ 2n - 1 $. (This can be proven using mathematical induction, see the exercise below.) The proposition $ p(n) $ is the equation $$ 1 + 3 + 5 + \dots + (2n - 1) = n^2. $$
Base case. The base case $ p(1) $ (expressed above) is clearly true. (In fact, by inspection, we see that $ p(n) $ is true for those first four cases $ n = 1, 2, 3, 4 $.)
Inductive step. Assume that $ p(k) $ is true, so the sum of the first $ k $ odd numbers is equal to $ k^2 $, ie, $$ 1 + 3 + 5 + \dots + (2k - 1) = k^2. $$ To prove $ p(k + 1) $, we consider the sum of the first $ k + 1 $ odd numbers, which is $$ 1 + 3 + 5 + \dots + (2k + 1). $$ Notice that the first $ k $ odd numbers appear in this sum as well, $$ (1 + 3 + 5 + \dots + (2k - 1)) + (2k + 1). $$ Since $ p(k) $ is true, this is equal to $$ (k^2) + (2k + 1). $$ Factoring this expression, we get $$ (k + 1)^2 $$ so we conclude that the sum of the first $ k + 1 $ odd numbers is equal to $ (k + 1)^2 $; that is, we conclude that $ p(k + 1) $ is true.
By the principle of mathematical induction, $ p(n) $ is true for all natural numbers $ n \geq 1 $.
exercises
- For any $ n \in \mathbb{N}_1 $, prove that the $ n^\text{th} $ odd
number is equal to $ 2n - 1 $.solution
Let $ p(n) $ be the statement that the $ n^\text{th} $ odd number is $ 2n - 1 $.
Base case. The statement $ p(1) $ is true since the 1st odd number is $ 1 $ and $ 2(1) - 1 = 1 $.
Inductive step. Suppose that $ p(k) $ is true, ie, that $ 2k - 1 $ is the $ k^\text{th} $ odd number. Well, the $ (k + 1)^{st} $ odd number is just 2 more than the $ k^{th} $ odd number, so it is equal to $$ (2k - 1) + 2 = 2k + 1 = 2(k + 1) - 1, $$ which proves that $ p(k + 1) $ is true.
By mathematical induction, $ p(n) $ is true for all $ n \geq 1 $.
- For any $ n \in \mathbb{N}_0 $, prove that $ 3^n - 1 $ is even.solution
Let $ p(n) $ be the statement that $ 3^n - 1 $ is even.
Base case. The proposition $ p(0) $ is true since $ 3^0 - 1 = 1 - 1 = 0 = 2 \cdot 0 $ is even.
Inductive step. Suppose that $ p(k) $ is true, ie, that $ 3^k - 1 = 2n $ for some natural number $ n $. We compute $$ \begin{align} 3^{k + 1} - 1 &= 3 \cdot 3^k - 1 \\ &= (2 + 1) \cdot 3^k - 1 \\ &= 2 \cdot 3^k + 3^k - 1 \\ &= 2 \cdot 3^k + 2n \\ &= 2 (3^k + 2) \end{align} $$ to see that $ 3^{k + 1} - 1 $ is also even, hence $ p(k + 1) $ is true.
By mathematical induction, $ p(n) $ is true for all $ n \geq 0 $.