Mathematical Induction

At its most basic, mathematical induction is a style of proof that proves statements about the natural numbers $\mathbb{N} = \{1, 2, 3, \ldots\}$, in other words, statements of the form

For all natural numbers $n$, $P(n)$ is true.

for some predicate $P$. Now, without induction, you might think that to prove it, you will need to prove the statements

individually. Well, there is an infinite list of things to prove, so this will only work if you have an infinite amount of time.

With induction, we do this a little differently; We instead prove the following infinite list of things:

Notice that when all of these are simultaneously true, then we can infer that $P(n)$ is true for any natural number $n$. However, there are still an infinite number of things to prove. Instead, what we really need to do is to first prove $P(1)$ and then simultaneously prove that $P(1) \Rightarrow P(2)$, $P(2) \Rightarrow P(3)$, $P(3) \Rightarrow P(4)$, etc., with a single argument. In other words, we only need to prove the following two statements:

which makes our task infinitely easier!

Here's an example.


Proposition 1. For every natural number $n$, the sum of the first $n$ odd numbers is $n^2$.

For example, say $n = 5$. Then the sum of the first $5$ odd numbers is $1 + 3 + 5 + 7 + 9 = 25$, which is indeed equal to $5^2$.

Proof. We will prove this by induction. Our predicate will be $P(n)$ which means “the sum of the first $n$ odd numbers is $n^2$”.

For the base case, we will show that $P(1)$ is true. True enough, the sum of the first $1$ odd numbers is just $1$ and it is equal to $1^2$.

Now, for the inductive case. Assume $P(n)$ for a natural number $n$, and we want to show that $P(n+1)$. The sum of the first $n+1$ odd numbers is equal to the sum of the first $n$ odd numbers plus the $(n+1)$th odd number. Now, by assumption, the sum of the first $n$ odd numbers is $n^2$. Also, note that the $(n+1)$th odd number is equal to $2n+1$. Thus, the sum of the first $n+1$ odd numbers is $n^2 + (2n+1)$. But $n^2+2n+1 = (n+1)^2$. Thus, $P(n+1)$ is true, and the inductive case is proven!

This is just the tip of the iceberg; Induction proofs are very powerful! I encourage you to read Chapter 3 of MIT 6.042 for a more thorough introduction to induction. It also explains the well-ordering principle, which simply says that

Well-ordering principle Every nonempty set of natural numbers has a smallest element.

This is very useful too, and it may sound very obvious, but as you may have learned by now, true statements are not necessarily obvious, and obvious statements are not necessarily true.

Exercises

As exercises, you can try proving the following statements using induction (or well-ordering theorem if you like).

Proposition 2. For every integer $x$, either $x$ is even or $x$ is odd, but not both.

Proposition 3. Any integer is of exactly one of the following forms: $5k$, $5k+1$, $5k+2$, $5k+3$, $5k+4$

This one is a little trickier.

Proposition 4. For any $n$, $(1+2+\ldots+n)^2 = (1^3+2^3+\ldots+n^3)$.

Problems