Mathematical Induction

• Induction is a method for proving an infinite sequence of statements. In its easiest form, you start by proving that the first statement is true. Next, you show that if an arbitrary statement in the list is true, then the next statement in the list is true.
• Induction is a consequence of the Well-Ordering Axiom for the positive integers.

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

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:

Sometimes the first statement will be rather than . The numbering can start with any integer, but often the first statement is numbered 0 or 1.

First, do the basis step:

1. Prove the first statement --- let's say that it's .

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

Next, do the induction step:

2. Assume is true, and try to prove .

When you've completed both steps, all the statements , , , ... are true, by induction.

The statement 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:

2'. Assume that , , ..., are true, and try to prove .

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.

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

2. Assume is true, and try to prove .

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

2'. Assume that , , ..., are true, and try to prove .

Also, the first statement in the sequence need not be statement 1; it could be statement 0, or statement 5. The numbering depends on the situation.

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

Consider the case of a simple induction.

Well, if not all the statements are true, there must be a first statement which is false. Why? The numbers of the false 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 false statement.

Suppose the first false statement is . Then the statement before it ( ) is true. There must be some true statement before , because I've proved is true in the basis step.

But the induction step shows if a statement is true, then the next statement is true. Applying this to the true statement tells me that is true --- which contradicts the fact that it's false.

This contradiction shows that there can't be any false statements, so all the statements in the sequence must be true.

Here are some examples of induction proofs.

Example. Show that

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

The example shows that in general, boxes should be half of an n by 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 . Plugging into the formula, I find that

It's true for .

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

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

Start with the thing you know to be true.

Add n to both sides:

The left side is the sum from 1 to , so

Combine the terms on the right over a common denominator:

This is the statement for , which is what I wanted to prove. By induction, the result is true for all .

Example. ( The definition of sums and product) The definitions of and are as follows.

For , define

For , define

For example,

Likewise, for , define

For , define

Using these definitions, you can prove properties of and .

Prove: If c is a constant, then for every positive integer n.

If , then

Thus, the result is true for .

Assume that the result is true for n:

Then

(The first equality used the definition of , while the second equality used the induction hypothesis.) Since the result holds for , the result is true for all , by induction.

Example. For that if , then .

For , I have and . The result is true for .

Assume that the result is true for n:

I'll try to prove the result for .

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 , so .

Next,

Now , so , or . Multiplying the last inequality by , I get

So

Adding this inequality to , I get

Hence,

Combining this with (*), I get

This proves the result for , so the result is true for all , 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 , rather than just the . Why? Because is defined in terms of and , rather than just , so I need to know that the induction hypothesis holds for and , not just .

In addition, my basis step involves proving the result for and for , not just . Why? Because the recursive definition for doesn't apply unless .

Example. A sequence of integers is defined by

Prove that

Check the result for :

It works.

Check the result for :

It works.

Next, take . Assume the result is true for all numbers less than n. In particular, the result is assumed true for and , so

I want to prove the result for n, which is

I have

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

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

Contact information

Copyright 2016 by Bruce Ikenaga