* 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:

* Axiom.* * (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.* Prove that for ,

For , the left side is and the right side is . The result holds for .

Assume that the result is true for n:

Prove the result for :

This proves the result for , so the result holds for all by induction.

* Example.* Prove 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 :

In order to see better what I'm trying to prove, I'll expand :

Now I'll start the proof:

(There are many ways to proceed from here. I decided to just use algebra, and to figure out what to do, I fiddled around on scratch paper! See if you can find another way to do this.)

The idea will be to rearrange the last expression into a sum of 4 terms, each of which I'll show is larger than the corresponding term in . To do this, I'll break the term up into and rearrange the last two 's:

Now I compare this to .

The first terms match: .

For the second terms, I have .

For the third terms, I have to do a little work:

For the fourth terms, I do something similar:

Adding up the equalities and inequalities, I have

Now I can wind up my proof:

This proves the result for , so the result is true for 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.

Copyright 2019 by Bruce Ikenaga