Induction

Induction is used to prove a sequence of statements $P(1)$ , $P(2)$ , $P(3)$ , .... There may be finitely many statements, but often there are infinitely many.

Example. Consider the statement

$$1 + 2 + 3 + \cdots + n = \dfrac{n(n + 1)}{2} \quad\hbox{for}\quad n \ge 1.$$

This is actually an infinite set of statements, one for each integer $n \ge 1$ :

$$\eqalign{1 &= \dfrac{1(1 + 1)}{2} \cr 1 + 2 &= \dfrac{2(2 + 1)}{2} \cr 1 + 2 + 3 &= \dfrac{3(3 + 1)}{2} \cr 1 + 2 + 3 + 4 &= \dfrac{4(4 + 1)}{2} \cr &\vdots \cr}$$

You might think of proving this result by induction --- and in fact, I'll do so below.

On the other hand, the statement

$$x^2 + 1 \ge 2x \quad\hbox{for all}\quad x \in \real$$

is an infinite set of statements, but there is one for each real number. You are unlikely to prove this by induction.

The fact that a statement involves integers does not mean induction is appropriate. For example, consider the statement

"The sum of two even numbers is even."

It's true that this is a statement about an infinite set of pairs of integers.

$$\eqalign{2 + 2 & \quad\hbox{is even} \cr 6 + (-14) & \quad\hbox{is even} \cr 112 + 64 & \quad\hbox{is even} \cr &\vdots \cr}$$

However, the problem with using induction here is that there isn't an obvious way to arrange the statements in a sequence.

Likewise, consider the statement

"If n is an integer, then $4n + 1$ is odd."

While it's conceivable that you could give an induction proof, it would be overkill: $4n + 1 = 2(2n) + 1$ expresses $4n + 1$ as 2 times something plus 1, so it must be odd.

How does induction work? Suppose you have a sequence of statements $P(1)$ , $P(2)$ , ..., $P(n)$ , ..., one for each positive integer. (There's no harm in starting your numbering with 0 if it's convenient.) In the simplest case, to give a proof by induction:

  1. Prove $P(1)$ .
  2. Let $n > 1$ , and assume $P(n - 1)$ is true.
  3. Using the assumption that $P(n - 1)$ is true, prove that $P(n)$ must be true.

If you can complete these steps, you can conclude that $P(n)$ is true for all $n \ge 1$ , by induction.

The assumption that $P(n - 1)$ is true is often called the induction hypothesis, or the inductive assumption.

Why does it work? Induction follows from a fundamental fact about the positive integers called the Well-Ordering Principle.

Well-Ordering Principle. Every nonempty subset of the positive integers has a smallest element.

The Well-Ordering Principle is an axiom for the positive integers, so there's no question of proving it.

Example. Consider the subset of the positive integers consisting of the positive even integers: $\{2, 4, 6, \ldots\}$ . The smallest element of this set is 2.

Consider the subset of the positive integers which consists of positive integers whose decimal representations begin and end with "1". For example, 101, 128391, and 1651 are elements of this set. The smallest element of this set is 1.

Principle of Mathematical Induction. Let $P(1)$ , $P(2)$ , ... be a set of statements indexed by the positive integers. Suppose that:

  1. $P(1)$ is true.
  2. For every $n > 1$ , if $P(n - 1)$ is true, then $P(n)$ is true.

Then $P(n)$ is true for all $n \ge 1$ .

Proof. I'll prove the result by contradiction.

Assume that $P(1)$ is true, and for every $n > 1$ , if $P(n - 1)$ is true, then $P(n)$ is true. Suppose that it isn't true that $P(n)$ is true for all $n \ge 1$ .

Consider the set of integers $n \ge 1$ such that $P(n)$ is false. Since $P(n)$ is not true for all $n \ge 1$ , there must be some n for which $P(n)$ is false. Hence, the set of integers $n \ge 1$ such that $P(n)$ is false is nonempty.

Since this is a nonempty subset of the positive integers, it contains a smallest element MIN. Thus, $P(\hbox{MIN})$ is false, and $P(n)$ is not false (i.e. $P(n)$ is true) for all $n < \hbox{MIN}$ .

Now MIN can't be 1, because $P(1)$ is true by assumption. Thus, $\hbox{MIN} > 1$ . So $\hbox{MIN} - 1$ is a positive integer, and $P(\hbox{MIN} - 1)$ must be true.

But now my second assumption --- if a statement in the sequence is true, the following statement is true --- shows that $P(\hbox{MIN} - 1 + 1) = P(\hbox{MIN})$ must be true. This contradicts the fact that $P(\hbox{MIN})$ is false.

This contradiction proves that $P(n)$ is true for all $n \ge 1$ .

Example. Prove that

$$1 + 2 + 3 + \cdots + n = \dfrac{n(n + 1)}{2} \quad\hbox{for}\quad n \ge 1.$$

The formula is true for $n = 1$ , since

$$1 = \dfrac{1\cdot 2}{2}.$$

Assume $n > 1$ , and suppose the formula holds for $n - 1$ . This means that

$$1 + 2 + 3 + \cdots + (n - 1) = \dfrac{(n - 1)((n - 1) + 1)}{2} = \dfrac{(n - 1)n}{2}.$$

I want to prove that the formula holds for n.

$$\matrix{1 + 2 + 3 + \cdots + n & = & 1 + 2 + 3 + \cdots + (n - 1) + n \hfill & \cr & = & \dfrac{(n - 1)n}{2} + n \hfill & \hbox{Induction hypothesis} \cr & = & \dfrac{n^2 - n}{2} + n \hfill & \hbox{Algebra} \cr & = & \dfrac{n^2 - n + 2n}{2} \hfill & \hbox{Common denominator} \cr & = & \dfrac{n^2 + n}{2} \hfill & \hbox{Algebra} \cr & = & \dfrac{n(n + 1)}{2} \hfill & \hbox{Algebra} \cr}$$

This proves the formula for n. Hence, the result is true for all $n \ge 1$ , by induction.

Example. Let $x \in \real$ , $x \ne 1$ . Prove that

$$1 + x + x^2 + \cdots + x^n = \dfrac{1 - x^{n+1}}{1 - x} \quad\hbox{for}\quad n \ge 0.$$

You're allowed to "begin" an induction with $n = 0$ --- or any other integer --- if it's convenient to do so.

For $n = 0$ ,

$$1 + x + x^2 + \cdots + x^n = 1, \quad\hbox{while}\quad \dfrac{1 - x^{n+1}}{1 - x} = \dfrac{1 - x}{1 - x} = 1.$$

The result is true for $n = 0$ .

Assume that $n > 0$ , and that the result holds for $n - 1$ :

$$1 + x + x^2 + \cdots + x^{n-1} = \dfrac{1 - x^n}{1 - x}.$$

I want to show that the result holds for n.

$$\matrix{1 + x + x^2 + \cdots + x^{n-1} + x^n & = & \dfrac{1 - x^n}{1 - x} + x^n \hfill & \hbox{Induction hypothesis} \cr & = & \dfrac{1 - x^n}{1 - x} + \dfrac{x^n - x^{n+1}}{1 - x} \hfill & \hbox{Algebra} \cr & = & \dfrac{1 - x^n + x^n + x^{n+1}}{1 - x} \hfill & \hbox{Algebra} \cr & = & \dfrac{1 - x^{n+1}}{1 - x} \hfill & \hbox{Algebra} \cr}$$

This proves the result for n, so the result is true for all $n \ge 0$ , by induction.

Example. Let $n \in \integer$ , $n \ge 1$ . Prove that

$$\dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} + \cdots + \dfrac{1}{n(n + 1)} = 1 - \dfrac{1}{n + 1}.$$

You may have seen this idea when you learned about infinite series; it's called telescoping:

$$\dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} + \cdots + \dfrac{1}{n(n + 1)} = \left(\dfrac{1}{1} - \dfrac{1}{2}\right) + \left(\dfrac{1}{2} - \dfrac{1}{3}\right) + \cdots + \left(\dfrac{1}{n} - \dfrac{1}{n + 1}\right).$$

The "argument" is that the terms cancel in pairs, leaving $1 - \dfrac{1}{n + 1}$ .

Arguments where you say "and so on" are often justified rigorously by induction. That's what I'll do here.

For $n = 1$ ,

$$\dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} + \cdots + \dfrac{1}{n(n + 1)} = \dfrac{1}{1\cdot 2} = \dfrac{1}{2}, \quad\hbox{while}\quad \dfrac{1}{n(n + 1)} = \dfrac{1}{2}.$$

The result is true for $n = 1$ .

Assume that $n > 1$ , and suppose the result is true for $n - 1$ :

$$\dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} + \cdots + \dfrac{1}{(n - 1)n} = 1 - \dfrac{1}{n}.$$

I want to show that the result holds for n.

$$\matrix{\dfrac{1}{1\cdot 2} + \dfrac{1}{2\cdot 3} + \cdots + \dfrac{1}{(n - 1)n} + \dfrac{1}{n(n + 1)} & = & 1 - \dfrac{1}{n} + \dfrac{1}{n(n + 1)} \hfill & \hbox{Induction hypothesis} \cr & = & 1 - \dfrac{(n + 1) - 1}{n(n + 1)} \hfill & \hbox{Algebra} \cr & = & 1 - \dfrac{n}{n(n + 1)} \hfill & \hbox{Algebra} \cr & = & 1 - \dfrac{1}{n + 1} \hfill & \hbox{Algebra} \cr}$$

This proves the result for n, so the result is true for all $n \ge 1$ , by induction.

In some situations, it's convenient to give an induction proof in the following form:

  1. Prove $P(1)$ .
  2. Let $n > 1$ , and assume $P(k)$ is true for all $k < n$ .
  3. Using the assumption that $P(k)$ is true for all $k < n$ , prove that $P(n)$ must be true.

In other words, you can take as your induction hypothesis the truth of all the statements prior to the $n^{\rm th}$ statement, which you are trying to prove.

Example. Define a sequence of integers by

$$x_0 = 6, \quad x_1 = -4, \quad\hbox{and}\quad x_n = 4x_{n-1} + 12x_{n-2} \quad\hbox{for}\quad n \ge 2.$$

Prove that

$$x_n = 6^n + 5\cdot (-2)^n \quad\hbox{for}\quad n \ge 0.$$

Here is a table which shows $x_0$ through $x_{10}$ :

$$\vbox{\offinterlineskip \halign{& \vrule # & \strut \hfil \quad # \quad \hfil \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 6 & & -4 & & 56 & & 176 & & 1376 & & 7616 & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 6 & & 7 & & 8 & & 9 & & 10 & & & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr & 46976 & & 279296 & & 1680896 & & 10075136 & & 60471296 & & & \cr height2pt & \omit & & \omit & & \omit & & \omit & & \omit & & \omit & \cr \noalign{\hrule} }} $$

Each x after the first two is defined in terms of the preceding two x's via the equation $x_n = 4x_{n-1} + 12x_{n-2}$ , which is called a recursion formula. For example,

$$x_6 = 4x_5 + 12x_4 = 4\cdot 7616 + 12\cdot 1376 = 46976.$$

To get the induction started, I have to verify the formula $x_n = 6^n + 5\cdot (-2)^n$ for both $n = 0$ and $n = 1$ . The reason is that the recursion formula doesn't kick in till $n = 2$ .

For $n = 0$ , the formula gives

$$x_0 = 6^0 + 5\cdot (-2)^0 = 1 + 5 = 6.$$

For $n = 1$ , the formula gives

$$x_1 = 6^1 + 5\cdot (-2)^1 = -4.$$

Both of these check with the given values.

Now assume $n > 1$ , and assume the formula $x_k = 6^k + 5\cdot (-2)^k$ holds for all $k < n$ . (Notice that I replaced n with k in the formula to avoid confusion.) I want to prove the formula for n, i.e. $x_n = 6^n + 5\cdot (-2)^n$ .

I begin with the recursion formula

$$x_n = 4x_{n-1} + 12x_{n-2} \eqno{(*)}.$$

Now $x_k = 6^k + 5\cdot (-2)^k$ holds for all $k < n$ , so in particular it holds for $k = n - 1$ and $k = n - 2$ :

$$x_{n-1} = 6^{n-1} + 5\cdot (-2)^{n-1} \quad\hbox{and}\quad x_{n-2} = 6^{n-2} + 5\cdot (-2)^{n-2}.$$

Now plug these into $(*)$ and do some algebra:

$$x_n = 4x_{n-1} + 12x_{n-2} = 4\left(6^{n-1} + 5\cdot (-2)^{n-1}\right) + 12\left(6^{n-2} + 5\cdot (-2)^{n-2}\right) =$$

$$\left(4\cdot 6^{n-1} + 12\cdot 6^{n-2}\right) + \left(20\cdot (-2)^{n-1} + 60\cdot (-2)^{n-2}\right) = \left(4\cdot 6 + 12\right)\cdot 6^{n-2} + \left(20\cdot (-2) + 60\right)\cdot (-2)^{n-2} =$$

$$36\cdot 6^{n-2} + 20\cdot (-2)^{n-2} = 6^2\cdot 6^{n-2} + 5\cdot (-2)^2\cdot (-2)^{n-2} = 6^n + 5\cdot (-2)^n.$$

This proves the result for n, so the result is true for all $n \ge 0$ by induction.

While the algebra looks like a mess, there is some sense to it, and you should keep the general principle in mind: Make what you have look like what you want. I knew that I wanted to get $6^n + 5\cdot (-2)^n$ . This suggested, first of all, that I group the powers of 6 together and the powers of -2 together.

I factored out $6^{n-2}$ and $(-2)^{n-2}$ because I saw powers of 6 and -2 in $6^n + 5\cdot (-2)^n$ . When I got to $36\cdot 6^{n-2} + 20\cdot (-2)^{n-2}$ , I was pretty sure that $36\cdot 6^{n-2}$ was supposed to give me the $6^n$ , and $20\cdot (-2)^{n-2}$ was supposed to give me the $5\cdot (-2)^n$ . So it was just a matter of finding the $6^2$ and $(-2)^2$ that I needed to make it work.

Example. Prove that if $n \ge 5$ , then $5^n \ge n^5$ .

For $n = 5$ , $5^n = 3125$ and $n^5 = 3125$ . The statement is true.

Assume that $n \ge 5$ , and that the result is true for n. I'll prove it for $n + 1$ . I have

$$5^{n+1} = 5\cdot 5^n \ge 5n^5.$$

Now $n \ge 5$ , so multiplying both sides by $n^4$ gives

$$n^5 \ge 5n^4. \eqno{\rm (1)}$$

Also, $n \ge 5$ implies $n^2 \ge 25$ , and multiplying both sides by $n^3$ gives

$$n^5 \ge 25n^3 > 10n^3. \eqno{\rm (2)}$$

Also, $n \ge 5$ implies $n^3 \ge 125$ , and multiplying both sides by $n^2$ gives

$$n^5 \ge 125n^2 > 10n^2. \eqno{\rm (3)}$$

Also, $n \ge 5$ implies $n^4 \ge 625$ , and multiplying both sides by n gives

$$n^5 \ge 625n = 624n + n > 5n + 1. \eqno{\rm (4)}$$

To inequalities (1)--(4), add the inequality $n^5 \ge n^5$ to obtain

$$5n^5 > n^5 + 5n^4 + 10n^3 + 10n^2 + 5n + 1 = (n + 1)^5.$$

Combining this with the inequality $5^{n+1} \ge 5n^5$ that I derived above, I get

$$5^{n+1} \ge (n + 1)^5.$$

Obviously, I didn't pluck those intermediate inequalities out of thin air! I worked backwards by expanding the target $(n + 1)^5$ , then trying to see how to make the terms in the expansion less than each of the 5 copies of $n^5$ I had in "$5n^5$ ".

Send comments about this page to: Bruce.Ikenaga@millersville.edu.

Bruce Ikenaga's Home Page

Copyright 2008 by Bruce Ikenaga