Proof by Mathematical Induction

Section 6.1 Proof by Mathematical Induction

Mathematical induction is a method for proving statements about the set of natural numbers. Since there are infinitely many natural numbers, a general statement about the natural numbers cannot be proven by showing it for particular cases. Math induction allows us to prove a statement for all natural numbers, in a relatively concise way.

Example 6.1.1. Motivational example.

The method of mathematical induction was first used by Francesco Maurolico (1494-1575), Italian mathematician and astronomer, in his work Arithmeticorum libri duo, published in 1575. He used it to prove the closed form formula for the sum of the first $n$ odd positive integers.

Consider the sum of the first odd positive integers,

\begin{align*} 1 \amp = 1\\ 1 + 3 \amp = 4\\ 1 + 3 + 5 \amp = 9\\ 1 + 3 + 5 + 7 \amp = 16\\ 1 + 3 + 5 + 7 + 9 \amp = 25\\ \vdots \amp = \vdots \end{align*}

Notice that the resulting numbers are the squares of natural numbers,

\begin{align*} 1 \amp = 1 = 1^2\\ 1 + 3 \amp = 4 = 2^2\\ 1 + 3 + 5 \amp = 9 = 3^2\\ 1 + 3 + 5 + 7 \amp = 16 = 4^2\\ 1 + 3 + 5 + 7 + 9 \amp = 25 = 5^2\\ \vdots \amp = \vdots \end{align*}

This pattern seems to continue, which leads to a conjecture. That is, the sum of the first $n$ natural numbers is equal to $n^2\text{.}$ The $i$th odd positive number can be written as $2i-1$ for $i = 1, 2, 3, \dots\text{.}$ So, this means,

\begin{equation*} 1 + 3 + 5 + \dots + (2n - 1) = n^2 \end{equation*}

Or, in summation notation,

\begin{equation*} \sum_{i=1}^n (2i - 1) = n^2 \end{equation*}

We want to prove this formula for every $n\text{.}$ At first, it seems like as $n$ get larger, the arithmetic will become more tedious, and more difficult. However, notice that each case depends on the previous case. For example, for the $n = 5$ case,

\begin{align*} 1 + 3 + 5 + 7 + 9 \amp = (1 + 3 + 5 + 7) + 9\\ \amp = 4^2 + 9 \amp\amp \text{by the previous case $n = 4$}\\ \amp = 25 \end{align*}

That is, if we know the conjecture holds for the previous case, we only need to add one additional number to verify it is true for the next case.

The idea with induction is that we will prove this for a general case, where $n$ is some arbirary positive integer $k\text{.}$ If we can show that in general, if the statement is true for some $n = k\text{,}$ then it is also true for $n = k+1\text{,}$ then the statement will proven for all $n\text{.}$

This is because, since we've shown its true for $n = 1\text{,}$ it's also true for $n = 2\text{.}$ Because it's true for $n = 2\text{,}$ it's also true for $n = 3\text{.}$ Similarly, because it's true for $n = 4\text{,}$ it's also true for $n = 5\text{.}$ And so on. For any integer $n\text{,}$ we can continue this reasoning until up to that $n\text{.}$

In summary, we want to show that if $P(k)$ is true, then $P(k+1)$ is true. To do this, first suppose that $P(k)$ is true. That is, for this arbitrary but particular positive integer $k\text{,}$

\begin{equation*} 1 + 3 + 5 + \dots + (2k-1) = k^2 \qquad \text{or,} \qquad \sum_{i=1}^k (2i-1) = k^2 \end{equation*}

Then, we want to show that,

\begin{equation*} 1 + 3 + 5 + \dots + (2k-1) + (2k+1) = (k+1)^2 \qquad \text{or,} \qquad \sum_{i=1}^{k+1} (2i-1) = (k+1)^2 \end{equation*}

Here, note that the next odd number in the summation is $2(k + 1) - 1 = 2k + 1\text{.}$ As before, the key insight is that this next sum can be written in terms of the previous sum, as,

\begin{gather*} \underbrace{1 + 3 + 5 + \dots + (2k-1)}_{\sum_{i=1}^k (2i-1)} + (2k+1) \end{gather*}

Then, since we have assumed that $\sum_{i=1}^k (2i-1) = k^2\text{,}$ we have that,

\begin{equation*} 1 + 3 + 5 + \dots + (2k-1) + (2k+1) = k^2 + (2k + 1) \end{equation*}

Finally, notice that $k^2 + 2k + 1 = (k + 1)^2$ can be factored as a perfect square trinomial. This is exactly what we wanted to show,

\begin{equation*} 1 + 3 + 5 + \dots + (2k-1) + (2k+1) = (k+1)^2 \end{equation*}

This proves the statement for any natural number $n\text{.}$

Subsection 6.1.1 Principle of Mathematical Induction

Let $P(n)$ be a statement depending on $n\text{,}$ where $n \in \mathbb{N}\text{.}$ Then, for each $n\text{,}$ $P(n)$ is either true or false. Then,

Theorem 6.1.2. Principle of mathematical induction.

A statement $P(n)$ is true for all natural numbers $n$ if,

$P(1)$ is true (called the base case).
For all $k \in \mathbb{N}\text{,}$ if $P(k)$ is true, then $P(k+1)$ is true (called the induction step). The assumption that $P(k)$ is true is called the inductive hypothesis.

In 1654, Blaise Pascal more precisely specified the method, and in 1883, Augustus De Morgan gave it the modern name “mathematical induction”.

Subsection 6.1.2 Intuition for Math Induction

Math induction makes intuitive sense. Suppose that $P(1)$ is true, and for all $k\text{,}$ if $P(k)$ is true implies $P(k+1)$ is true. Then, applying this for $k = 1$ means that $P(2)$ is true. Then, since $P(2)$ is true, this implies that $P(3)$ is true. Since $P(3)$ is true, $P(4)$ is true, and so on. Then, for any $n \in \mathbb{N}\text{,}$ we can apply the implication enough times to show that $P(n)$ is true.

Math induction is like an infinite sequence of dominoes. To ensure that “all” of the dominoes will be knocked, we must be certain that,

The first domino will be knocked over (the base case).
The dominoes are set up such that if one domino falls, then the next domino will fall (the induction step).

In a similar way, the principle of math induction can be thought of as climbing a ladder. If you can climb onto the first rung, and also always climb one rung higher, then you can climb the “entire” ladder.

Also, note that mathematical induction is unrelated to inductive reasoning, which is in contrast to deductive reasoning. Inductive reasoning involves using many specific observations to make a conclusion about a general principle. Deductive reasoning involves using premises to logically infer a conclusion. Mathematical induction is a form of deductive reasoning.

Subsection 6.1.3 More Basic Examples

Example 6.1.3. Motivational example revisited.

Fact 6.1.4.

The sum of the first $n$ odd natural numbers is $n^2\text{.}$ In other words,

\begin{equation*} 1 + 3 + 5 + \dots + (2n - 3) + (2n - 1) = \sum_{k=1}^n (2k - 1) = n^2 \end{equation*}

Proof.

By induction, for $n = 1\text{,}$ we have,

\begin{equation*} \sum_{i=1}^1 (2i - 1) = 1 = 1^2 \end{equation*}

Then, assume the result is true for some $n = k \in \mathbb{N}\text{,}$ and we want to show that,

\begin{equation*} 1 + 3 + \dots + (2k - 1) + (2(k + 1) + 1) = \sum_{i=1}^{k+1} (2i - 1) = (k + 1)^2 \end{equation*}

Then,

\begin{align*} 1 + 3 + \dots + (2k - 1) + (2k + 1) \amp = \sum_{i=1}^{k+1} (2i - 1)\\ \amp = \sum_{i=1}^k (2i - 1) + (2k + 1) \amp\amp \text{separating off the final term}\\ \amp = k^2 + (2k + 1) \amp\amp \text{by the induction hypothesis}\\ \amp = (k + 1)^2 \amp\amp \text{by factoring} \end{align*}

Thus, by induction, the result is true for all $n \in \mathbb{N}\text{.}$

Fact 6.1.5. Product of consecutive integers is even.

For all $n \in \mathbb{N}\text{,}$ $n(n + 1)$ is even.

This is true for all $n \in \mathbb{Z}$ however we will only prove it for positive integers. This can be proved without induction. This is because at least one of $n$ and $(n + 1)$ is even, using proof by cases. If $n$ is even, then $(n + 1)$ is odd, and if $n$ is odd, then $(n + 1)$ is even. Thus, $n(n + 1)$ is the product of an even and odd integer, which is even.

Proof.

By induction, for $n = 1\text{,}$ we have $1 \cdot (1 + 1) = 2$ which is even. Then, assume the result is true for some $n = k \in \mathbb{N}\text{,}$ that is, $k(k + 1)$ is even. Then, we want to show that $(k + 1)((k + 1) + 1) = (k + 1)(k + 2)$ is even. Then,

\begin{align*} (k + 1)(k + 2) \amp = k^2 + 3k + 2 \amp\amp \text{expanding} \end{align*}

Then, to use the induction hypothesis, split up $k(k + 1) = k^2 + k\text{,}$ and the leftover terms,

\begin{align*} \amp = (k^2 + k) + (2k + 2) \amp\amp \text{splitting up the terms}\\ \amp = k(k + 1) + 2(k + 1) \end{align*}

By the induction hypothesis, $n(n + 1)$ is even, and also $2(n + 1)$ is even, so their sum $(n + 1)(n + 2)$ is even.

Subsection 6.1.4 Using Proof by Induction

State that you are using a proof by induction, by saying “By induction, ...” or similar. If there are multiple variables that are natural numbers, then specify explicitly which is being used as the index by saying for example, “By induction on $n\text{,}$ ...”.
Show the base case is true.
Assume that $P(k)$ is true for some $k \in \mathbb{N}\text{.}$ Then, use that assumption with some mathematical reasoning to prove that $P(k+1)$ is true.
Finally, recall again the conclusion of the proof, that by induction, the statement is true for all natural numbers.

The most difficult and important part of induction is the inductive step. Often, the inductive step involves showing that the $(k+1)$th case can be written in terms of the $k$th case, in some way. This will allow you to use the inductive assumption.

Subsection 6.1.5 General Principle of Math Induction

Sometimes, we only want to prove a statement for all natural numbers, starting at some integer that is not 1. Perhaps that for smaller natural numbers, the statement is false or is undefined. The principle of math induction still holds.

For $b \in \mathbb{Z}\text{,}$ a statement $P(n)$ is true for all $n \in \mathbb{Z}\text{,}$ $n \geq b$ if,

$P(b)$ is true, and,
For all $k \in \mathbb{Z}\text{,}$ $k \geq b\text{,}$ if $P(k)$ is true, then $P(k + 1)$ is true.

Fact 6.1.6. Factorials are even.

For all $n \in \mathbb{N}, n \geq 2\text{,}$ $n!$ is even.

Of course, this is trivial since $n!$ contains a factor of 2 for all $n \geq 2\text{,}$ and so is even. However, we can also prove this by induction.

Proof.

By induction, for $n = 2\text{,}$ $2! = 2$ is even. Then, assume the result is true for some $n \geq 2\text{,}$ that $n!$ is even. Then,

\begin{equation*} (n + 1)! = (n + 1) \cdot n! \end{equation*}

Since $n!$ is even, $(n + 1) \cdot n!$ is even, as any multiple of an even integer is even.

Subsection 6.1.6 Remarks

Math induction can be used to quite easily prove that formulas are correct. However, it doesn't provide any insight into how to actually derive those formulas.

To develop a formula, it is often helpful to consider particular cases, especially with small numbers. Then, try to determine the pattern, and conjecture a formula. Then, with math induction, you can prove it is true.

It turns out that with math induction, if the result is true (the formula is correct), then math induction is guarenteed to work.