Mathematical induction

1. Introduction

This web page presents the idea of mathematical induction. It will explain the basic ideas, show how you can use induction in your proofs, and presents a framework or template for exemplary proofs by induction in first year mathematics.

The word induction refers to a type of reasoning in which one induces general principles and facts from specific examples. In other words, properly speaking, induction is the kind of argument that goes from specific examples to general principles. So this word might properly be applied to the scientific method of inducing facts about the world from observations and experiments, and as such is distinguished from deduction in which facts are deduced from axioms or other facts by strict logical laws.

You should have learnt, or been taught, that in written mathematics there is no place for a "proof by looking at examples". In fact, all mathematical proofs are deductions, since there is no place in mathematics for a proof that goes by guessing a rule from a few examples. However, for obscure historical reasons the kind of deduction we look at here is called mathematical induction, and it is usually just called induction by mathematicians—who, as just pointed out, don't use any sort of induction in the correct sense of the word.

So the word "induction" applied in this way is a misnomer, but the principle it refers to is especially important throughout all branches of mathematics.

The main idea of mathematical induction is that if a statement can be proved true for the number 1, and if we can also show that by assuming it true for 1,2,3,4,, we can prove it true for +1 , then our statement will therefore true for all natural numbers 1 . The power of this method is that a statement can be proved true for all natural numbers in finitely many steps, rather than having to prove it true for each 1,2,3,4, individually. Induction is the main method of proof for any statement involving natural numbers, and is also used extensively for proofs concerning other finite objects, such as finite graphs, groups, etc.

Actually there is nothing special about starting with the number 1. Inductions often start with some other integer as some of the following examples demonstrate.

2. Examples of proofs by induction

We start with some examples of results to be proved by induction.

Bernoulli's inequality.

Let -1 in and 0 . Then (1+) 1+ .

Proof.

The statement to be proved is, For all real numbers -1 and all the inequality (1+) 1+ is true.

We start by letting -1 be an arbitrary real number. That is, we are not allowed to assume anything at all about this number other than it is a real number greater than -1. This number is now fixed throughout this proof. The rest of the proof is by induction on .

We must define a particular statement to look at. In this case (as is usually the case for proofs by induction) we obtain this statement from the result we are trying to prove.

Let

()

be the statement (1+) 1+ .

Notice that

()

is a mathematical statement: it doesn't have a numerical value, but is instead true or false. In fact this statement depends on the value of in the sense that it might be true for some values of and false for others. (It also depends on , so perhaps we should write it as

(,)

, but since has been chosen and will not change again throughout this proof, it is acceptable to leave out of the notation and write

()

We must first prove that

(0)

is true.

Subproof.

The statement

(0)

is (1+)⁰¹⁺⁰ . Since 1+ 0 we have (1+)⁰⁼¹ and we also have 1+0 =1 . So this statement says that an expression with value 1 is greater or equal to another expression with value 1. Therefore

(0)

is true.

We now consider an arbitrary 0 and make an important assumption, that the following statement (called the induction hypothesis) is true.

(0)
,
(1)
,
(2)
, ,
()
are all true.

We claim that using this assumption that we can show that

(+1)

is also true.

Subproof.

Indeed, since 0 our induction hypothesis says that (1+) 1+ holds, since this is what

()

says and our induction hypothesis says that

()

is true. Since -1 we have 1+ 0 so we can multiply both sides of the inequality (1+) 1+ by 1+ giving

(1+)⁺¹ 1+ 1+

We can expand the right hand side of this as

1+ 1+ =1+(+1)+ ² 1+(+1)

Putting these together we have

(1+)⁺¹ 1+(+1)

which is precisely the statement

(+1)

. Therefore, for arbitrary 0 the induction hypothesis implies that

(+1)

is also true.

Summing up, we showed that

(0)

is true, and we also showed that if

(0)

holds then

(1)

is true. So we can deduce that

(0)

and

(1)

are both true. But by the argument just given it follows from this that

(0)

and

(1)

and

(2)

are all true. This process continues for as many times as required to show that

(0)

and

(1)

and and

()

are all true for any 0 . We deduce that

()

holds for all 0 by the principle of mathematical induction.

It may be worth commenting further: on the key argument in the last paragraph of this proof: it perhaps seems rather vague or imprecise that this step of the proof rests on some intuition that if

(0)

holds and

(0)

(1)

, ,

()

imply

(+1)

then

()

holds for all . Indeed this is a principle about the natural numbers that we believe intuitively, and one that we take as an axiom for the natural numbers. There are other approaches: for example this principle of induction can be justified from alternative principles or axioms about the natural numbers, such as the one that says that for any property

()

true for some natural number there is a least natural number with this property. This alternative axiom for the natural numbers (together with the assertion that every natural number except the very first one has a natural number one less than it) can be used to justify the principle of induction. A third approach, which takes us beyond the scope of these notes, is that in some circumstances the set of natural numbers can be defined to be the smallest set containing 0 and closed under +1 . Then if the conditions for induction are correct for some statement

()

, the set of objects satisfying

()

is such a set of natural numbers containing 0 and closed under +1 hence must be the whole of , since is the smallest such.

Here is another example of induction.

Proposition on triangle numbers.

Let 1 be a natural number. Then the th triangle number 1+2++ is equal to (+1)/2 .

Proof.

Let

()

be the statement =1 =(+1)/2 .

We first prove that

(1)

is true.

Subproof.

The statement

(1)

is =11=1(1+1)/2 . The summation on the left hand side has a single term where =1, so is 1. The formula on the right hand side evaluates to 1(1+1)/2=2/2=1. So the statement just says 1=1, which is true.

We now let 1 in the natural numbers be arbitrary and assume the following induction hypothesis.

(1)
,
(2)
, ,
()
are all true.

We show that using this assumption that

(+1)

is also true.

Subproof.

The expression =1 +1 equals ( =1 ) +(+1). By our assumption

()

is true so =1 =(+1)/2 so =1 +1 =(+1)/2 +(+1)=(+1).( 2 +1)=(+1).(+2)/2 . Therefore =1 +1 =(+1).(+2)/2 is true. But this is exactly the statement

(+1)

, so we have succeeded in showing what we claimed.

So we have showed that

(1)

is true, and we also showed that if 1 is arbitrary and

(1)

and

(2)

and and

()

are all true then

(+1)

is also true. We deduce that

()

holds for all 1 in by the principle of mathematical induction.

3. Induction

The previous section gave example proofs by induction. These proofs have similar structure, and it is worth highlighting the similarities (as well as the differences).

Both proofs use an integer variable to do the main work. In the first case this variable was called and in the second it was called . We often explain what we are doing as proving a statement by induction on (or in the second case).
In both proofs we defined a particular statement that is considered in the induction. We called it
()
or
()
but you can call it whatever you like. This statement is the induction statement.
In both proofs the variable we are doing induction on starts at some particular number. In the first it was convenient to start at 0, and in the second we started at 1. This is the starting value.
In both proofs we first proved that the statement
is true at the starting value of the induction variable. This step is called the base case of the induction.
In the first proof we assumed that was arbitrary and that a statement of the form
(0)
and
(1)
and and
()
is true. In the second this was only modified to change the name of the induction variable and the starting value of that variable. This assumption that we made is the induction hypothesis.
In both cases we showed that the induction hypothesis implies that the next instance of
is true (i.e.
(+1)
in the first case and
(+1)
in the second). This step in the argument is called the induction step.
In both cases there is a concluding short narrative that explains the use of the principle of induction.

There are some general comments about induction that we should make.

You should be prepared to do induction on any variable, whether it be called , or something else.
You should be prepared to start your induction at any integer. The most common places to start are 0 and 1, but any integer, even negative values, are valid places to start an induction.
You must always write down an induction statement. Often this is derived from the theorem being proved, but there are also many cases when it is not obvious what to take at all. The conclusion of the induction is that this statement is true for all values of the variable greater than or equal to the starting value. In some complicated proofs it may be necessary to explain why this conclusion implies the required result.
There are two steps to an induction proof: the base case and the induction step. Both must be included and nothing can be deduced until they are both done. It is not always the case that the base case is easier than the induction step. Sometimes it is the other way round.
The safest kind of induction hypothesis to use is the one here that says that
()
holds for all previous values . This is safest because it is the strongest hypothesis that is valid, and it makes sense to assume as much as possible to make the remaining argument as easy as possible. The two proofs above only used the immediately preceding case,
()
or
()
, and many other induction proofs work in the same way. But there are also plenty of induction proofs that require more than one previous case.

4. Other common forms of induction

For students who first see induction, the usual form it takes is the following:

Define a statement
()
;
Show that
(1)
is true;
Show that, assuming
()
is true one can derive
(+1)
;
State that by the principle of induction, the above steps show that
()
holds for all natural numbers .

This is the

()

implies

(+1)

form of induction and the examples given above are of this type. There is nothing wrong with this form of induction, except that it is not quite as powerful as the one given earlier. The point is that in the

()

implies

(+1)

form you assume

()

is true whereas you could have assumed the much stronger statement that

(1)

(2)

,...,

()

all hold instead. You would have had a little more to help you, which might have been useful (and often is), and there are no disadvantages. The example of the Least Number Principle discussed and proved below is one where the stronger form of induction is particularly useful.

As a useful rule of thumb, any proof that you see which contains an ellipsis looking like in a form such as 1,2,, should properly speaking be proved by an application of induction. Hopefully, if the work is not yours, the piece you are reading is sufficiently clear to understand what is happening and to be able to rephrase the proof in terms of induction. This section discusses other common types of argument, some of which are really induction in disguise.

Least number principle.

Suppose

()

is a statement and an integer such that

()

holds for some integer . Then there is a least integer such that

()

holds.

Proof.

This is by induction on the variable starting at . But the twist is that we also combine this proof with a use of proof by contradiction.

So we start by assuming that the statement we are trying to prove is false, and we then use induction to derive a contradiction. Assume therefore that

There is no least integer such that
()
holds.

Subproof.

We now derive a contradiction by induction. Our contradiction will be that there is in fact no integer such that

()

holds, and this is contrary to the assumptions in the proposition. Our induction statement () is the statement

()

is false. We must prove a base case and an induction step.

The base case, ().

Subproof.

If () were false, that would mean that

()

is false is false, i.e. that

()

is true. But then is the least integer greater than or equal to for which

()

is true, since there is no smaller integer to consider, contrary to our assumption that there is no such least integer.

Now assume that is arbitrary and assume the induction hypothesis that

(), (~~+1)~~, , () are all true.

We claim that it follows that (+1) is true.

Subproof.

Indeed, if (+1) were false, that would mean that

(+1)

is true. But by the induction hypothesis (), (~~+1)~~, , () are all true and hence

()

(~~+1)~~

, ,

()

are all false. So +1 would be the least integer greater than or equal to such that

(+1)

is true. This is contrary to our assumption that there is no such integer. So therefore

(+1)

cannot be true and hence (+1) is true.

It follows from the base case and the induction step that () is true for all integers by the principle of mathematical induction. Therefore

()

is false for all integers , and this is contrary to one of the assumptions in the proposition, giving us the required contradiction.

Minimal counter-example principle.

Suppose

()

is a statement that is false for some integer , where . Then there is some least integer value of such that

()

is false.

Proof.

Let () be the statement that

()

is false. So () is true for some since

()

is false for some such . But then by the previous proposition there is a least with and () is true. And this is the least integer such that

()

is false.

We conclude with an application: the Archimedean Property of the reals says that for any there is some such that . It follows from this that every has an integer part, . To see this, let and choose , such that and - . So - . and let

()

be the statement . Then the integer is an integer greater than or equal to - such that

()

is true. So there is a least integer - such that

()

. For this we have -1 since either -1- or else - -1 and therefore

(-1)

is false (since is least such that

()

holds). Therefore = , the upper integer part of . To get the lower integer-part = just argue that if = then = and if not then -1 so -1= .