Mathematical Induction

Mathematical induction is a method for proving a result which consists of a sequence of statements:

$$\hbox{statement}_1, \hbox{statement}_2, \hbox{statement}_3, \ldots .$$

It applies when the statements in the sequence are related or similar. The idea is that if you can get started, and if you can make each step from one statement to the next, you can prove all of them.

Induction depends on the following fundamental property of the positive integers:

Well-Ordering. Every nonempty set of positive integers has a smallest element.

This may seem obvious, and it is. There is no question of proving the Well-Ordering Principle; it's essentially an axiom which defines the positive integers. As simple as it sounds, it has very important consequences: Induction, which I'll discuss here, is one, and the Division Algorithm is another.

Induction will work like this. Suppose you have a sequence of statements:

$$\hbox{statement}_1, \hbox{statement}_2, \hbox{statement}_3, \ldots.$$

Sometimes the first statement will be $\hbox{statement}_0$ rather than $\hbox{statement}_1$ . The numbering can start with any integer, but often the first statement is numbered 0 or 1.

First, do the basis step:

(Sometimes the basis step involves proving more than one statement. I'll give an example of this later.)

Next, do the induction step:

When you've completed both steps, all the statements $\hbox{statement}_1$ , $\hbox{statement}_2$ , $\hbox{statement}_3$ , ... are true, by induction.

The statement $\hbox{statement}_n$ which you're assuming to be true is called the induction hypothesis or induction assumption.

The procedure I've given is often called simple induction. You may also do a general induction (also called a strong induction), in which case the induction step above is replaced by:

That is, in simple induction you assume the last statement is true and try to prove the next statement. In general induction, you assume that all the preceding statements are true, and try to prove the next statement. Which one you use depends on the situation.

Remark. The labelling of the statements is arbitrary, so some people prefer to do the induction step this way:

In this case, the induction step for a general or strong induction would be:

Before I give some examples, let me explain how induction is related to well-ordering. Why does proving the basis and induction steps to prove all the statements?

Consider the case of a simple induction.

Well, if not all the statements are true, there must be a first statement which is not true. Why? The numbers of the untrue statements form a subset of the positive integers, so by Well-Ordering, this subset has the smallest element. This smallest element is the number of the first untrue statement.

Suppose then that the first untrue statement is $\hbox{statement}_{53}$ . Now I've proved $\hbox{statement}_1$ (the basis step), and I also proved that if I know a given statement is true, then I know the next statement is true (the induction step). Applying the induction step to $\hbox{statement}_1$ , I know that $\hbox{statement}_2$ is true. Applying induction step to $\hbox{statement}_2$ , I know that $\hbox{statement}_3$ is true. And so on. Eventually, I find out that $\hbox{statement}_{53}$ is true, but I assumed it was untrue. This contradiction means that all the statements must be true.

Before I give some induction proofs, I'll give examples of statements that you might try to prove by induction.

Example. ( The Binomial Theorem)

$$(x + y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k},$$

where $n = 0, 1, 2, \ldots$ .

This is a sequence of statements:

$$(x + y)^0 = \sum_{k=0}^0 {0 \choose k} x^k y^{0-k},$$

$$(x + y)^1 = \sum_{k=0}^1 {1 \choose k} x^k y^{1-k},$$

$$(x + y)^2 = \sum_{k=0}^2 {2 \choose k} x^k y^{2-k},$$

and so on.

The idea is that if I know that a given statement in the sequence is true, I can use it to prove the next one.

Example. ( Fibonacci numbers) Let $x_0 = 1$ , $x_1 = 1$ , $x_2 = 2$ , $x_3 = 3$ , and in general

$$x_{n+1} = x_n + x_{n-1} \quad\hbox{for}\quad n \ge 2.$$

This is a recursive formula for the Fibonacci numbers. There is an explicit formula for $x_n$ which is somewhat unexpected:

$$x_n = \dfrac{1}{\sqrt{5}} \left(\dfrac{1 + \sqrt{5}}{2}\right)^{n+1} - \dfrac{1}{\sqrt{5}} \left(\dfrac{1 - \sqrt{5}}{2}\right)^{n+1} \quad\hbox{for}\quad n \ge 0.$$

Again, this is a sequence of statements:

$$x_0 = \dfrac{1}{\sqrt{5}} \left(\dfrac{1 + \sqrt{5}}{2}\right) - \dfrac{1}{\sqrt{5}} \left(\dfrac{1 - \sqrt{5}}{2}\right),$$

$$x_1 = \dfrac{1}{\sqrt{5}} \left(\dfrac{1 + \sqrt{5}}{2}\right)^2 - \dfrac{1}{\sqrt{5}} \left(\dfrac{1 - \sqrt{5}}{2}\right)^2,$$

$$x_2 = \dfrac{1}{\sqrt{5}} \left(\dfrac{1 + \sqrt{5}}{2}\right)^3 - \dfrac{1}{\sqrt{5}} \left(\dfrac{1 - \sqrt{5}}{2}\right)^3,$$

and so on.

Example. ( A statement you wouldn't prove by induction) In calculus, you learned the following result: A continuous function on a closed interval has an absolute maximum and an absolute minimum on the interval. This is not a statement you'd try to prove using induction.

There is no obvious way to express the result as a sequence of statements, where each one depends on the one (or ones) before it. In fact, the result is a statement about all continuous functions and all closed intervals, and these are both uncountable sets. If anything, the result seems to be an uncountable collection of statements (whereas a sequence or list of statements must be countable).

Here are some examples of induction proofs.

Example. Show that

$$\sum_{k=1}^n k = \dfrac{n(n + 1)}{2} \quad\hbox{for}\quad n \ge 1.$$

Here's a geometric argument which makes the result plausible.

$$\hbox{\epsfysize=3in \epsffile{induction1.eps}}$$

The example shows that in general, $1 + 2 + \cdots + n$ boxes should be half of an n by $n + 1$ rectangle.

However convincing the pictures may be, they aren't really a proof. I'll prove the result using induction.

First, I prove the result for $n = 1$ . Plugging $n = 1$ into the formula, I find that

$$\sum_{k=1}^1 k = 1 \quad\hbox{while}\quad \dfrac{1\cdot(1 + 1)}{2} = 1.$$

It's true for $n = 1$ .

I'll use the first form of the induction step. Assume the result is true for n:

$$\sum_{k=1}^n k = \dfrac{n(n + 1)}{2}.$$

Note that I'm assuming that this is true! I want to prove the next statement, which is the statement for $n + 1$ :

$$\sum_{k=1}^{n+1} k = \dfrac{(n + 1)(n + 2)}{2}.$$

Start with the thing you know to be true.

$$\sum_{k=1}^n k = \dfrac{n(n + 1)}{2}.$$

Add n to both sides:

$$\sum_{k=1}^n k + (n + 1) = \dfrac{n(n + 1)}{2} + (n + 1).$$

The left side is the sum from 1 to $n + 1$ , so

$$\sum_{k=1}^{n+1} k = \dfrac{n(n + 1)}{2} + (n + 1).$$

Combine the terms on the right over a common denominator:

$$\sum_{k=1}^{n+1} k = \dfrac{n(n + 1)}{2} + (n + 1) = \dfrac{n(n + 1) + 2(n + 1)}{2} = \dfrac{n^2 + n + 2n + 2}{2} = \dfrac{n^2 + 3n + 2}{2} = \dfrac{(n + 1)(n + 2)}{2}.$$

This is the statement for $n + 1$ , which is what I wanted to prove. By induction, the result is true for all $n \ge 1$ .

Example. ( The definition of sums and product) Here are precise definitions of $\displaystyle \sum_{i=1}^n a_i$ and $\displaystyle \prod_{i=1}^n a_i$ .

For $n = 1$ , define

$$\sum_{i=1}^1 a_i = a_1.$$

For $n > 1$ , define

$$\sum_{i=1}^n a_i = \sum_{i=1}^{n-1} a_i + a_n.$$

For example,

$$\sum_{i=1}^2 a_i = \sum_{i=1}^1 a_i + a_2 = a_1 + a_2.$$

Likewise, for $n = 1$ , define

$$\prod_{i=1}^1 a_i = a_1.$$

For $n > 1$ , define

$$\prod_{i=1}^n a_i = \left(\prod_{i=1}^{n-1} a_i\right)\cdot a_n.$$

Using these definitions, you can prove properties of $\displaystyle \sum$ and $\displaystyle \prod$ .

For example, I'll prove that if c is a constant, then $\displaystyle \prod_{i=1}^n c = c^n$ for every positive integer n.

If $n = 1$ , then

$$\prod_{i=1}^n c = \prod_{i=1}^1 c = c = c^1.$$

Thus, the result is true for $n = 1$ .

Assume that the result is true for n:

$$\prod_{i=1}^n c = c^n.$$

Then

$$\prod_{i=1}^{n+1} c = \left(\prod_{i=1}^n c\right)\cdot c = c^n\cdot c = c^{n+1}.$$

(The first equality used the definition of $\displaystyle \prod$ , while the second equality used the induction hypothesis.) Since the result holds for $n + 1$ , the result is true for all $n \ge 1$ , by induction.

Example. For that if $n \ge 5$ , then $3^n > (n + 1)^3$ .

For $n = 5$ , I have $3^n = 3^5 = 243$ and $(n + 1)^3 = 6^3 = 216$ . The result is true for $n = 5$ .

Assume that the result is true for n:

$$3^n > (n + 1)^3.$$

I'll try to prove the result for $n + 1$ .

$$3^{n+1} = 3\cdot 3^n = 3^n + 2\cdot 3^n > (n + 1)^3 + 2\cdot 3^n. \eqno{\rm (*)}$$

To go on, I'll prove two inequalities, which I'll add to get the one I want. You should be able to follow the steps, but you might wonder how I knew what to do. As is often the case in proofs, I worked backwards on scratch paper to figure out what I had to prove. What you're seeing is the cleaned-up version, written forward.

First, I have $n \ge 5$ , so $3^n \ge 243 > 7$ .

Next,

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

Now $n \ge 5$ , so $n^2 \ge 25 > 6$ , or $n^2 - 6 > 0$ . Multiplying the last inequality by $n \ge 5$ , I get

$$\eqalign{n(n^2 - 6) &> 0 \cr n^3 - 6n &> 0 \cr n^3 + 3n^2 + 3n &> 3n^2 + 9n \cr}$$

So

$$3^n > (n + 1)^3 = n^3 + 3n^2 + 3n + 1 > n^3 + 3n^2 + 3n > 3n^2 + 9n.$$

Adding this inequality to $3^n > 7$ , I get

$$2\cdot 3^n > 3n^2 + 9n + 7 = (n^3 + 6n^2 + 12n + 8) - (n^3 + 3n^2 + 3n + 1) = (n + 2)^3 - (n + 1)^3.$$

Hence,

$$(n + 1)^3 + 2\cdot 3^n > (n + 2)^3.$$

Combining this with (*), I get

$$3^{n+1} > (n + 2)^3.$$

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

I'll do the next example using general or strong induction --- that is, I'll assume the truth of all the statements preceding the $n^{\rm th}$ , rather than just the $(n - 1)^{\rm st}$ . Why? Because $a_n$ is defined in terms of $a_{n-1}$ and $a_{n-2}$ , rather than just $a_{n-1}$ , so I need to know that the induction hypothesis holds for $n - 2$ and $n - 1$ , not just $n - 1$ .

In addition, my basis step involves proving the result for $n = 0$ and for $n = 1$ , not just $n = 0$ . Why? Because the recursive definition for $a_n$ doesn't apply unless $n \ge 2$ .

Example. Define

$$a_0 = 2, \quad a_1 = 2, \quad\hbox{and}\quad a_n = 2a_{n-1} + 8a_{n-2} \quad\hbox{for}\quad n \ge 2.$$

Prove that

$$a_n = 4^n + (-2)^n \hbox{ for } n \ge 0.$$

Check the result for $n = 0$ :

$$a_0 = 2 \quad\hbox{and}\quad 4^0 + (-2)^0 = 1 + 1 = 2.$$

It works.

Check the result for $n = 1$ :

$$a_1 = 2 \quad\hbox{and}\quad 4^1 + (-2)^1 = 4 - 2 = 2.$$

It works.

Next, take $n > 1$ . Assume the result is true for all numbers less than n. I want to prove the result for n, which is

$$a_n = 4^n + (-2)^n.$$

By definition,

$$a_n = 2a_{n-1} + 8a_{n-2}.$$

By my inductive assumption, the result is true for $n - 1$ and for $n - 2$ , because they are less than n. So these statements are true:

$$a_{n-1} = 4^{n-1} + (-2)^{n-1}, \quad a_{n-2} = 4^{n-2} + (-2)^{n-2}.$$

Plug these in above and simplify:

$$a_n = 2\cdot\left[4^{n-1} + (-2)^{n-1}\right] + 8\cdot\left[4^{n-2} + (-2)^{n-2}\right] = \left(2\cdot 4^{n-1} + 8\cdot 4^{n-2}\right) + \left(2\cdot (-2)^{n-1} + 8\cdot (-2)^{n-2}\right) =$$

$$4^{n-2}(8 + 8) + 2^{n-2}(-4 + 8) = 4^n + (-2)^n.$$

The keys to the simplification are to group "like" terms together (the powers of 4 and the powers of -2 to get the second equality) and to make what you've got look like what you want (factoring out the powers of 4 and -2 to get the third equality).

This proves the statement for n, so the result is true for all n, by induction.

Send comments about this page to: bikenaga@marauder.millersville.edu.

Last updated: June 7, 2008

Bruce Ikenaga's Home Page

Math Department Home Page

Millersville University Home Page

Copyright 2007 by Bruce Ikenaga