# a.2. mathematical induction

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.)

solution

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$.

solution

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$.

solution

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

1. 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$.

2. 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$.