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. So it 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. 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 will 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.

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 , , n we can prove it true for n + 1 , then our statement will therefore true for all natural numbers n 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 n 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.

Proposition 2.1 (Bernoulli's inequality)

Let x > -1 in and n 0 . Then ( 1 + x ) n 1 + n x .

Proof

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

We start by letting x > -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 . The rest of the proof is by induction on n .

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 P ( n ) be the statement ( 1 + x ) n 1 + n x .

Notice that P ( n ) 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 n in the sense that it might be true for some values of n and false for others. (It also depends on x , so perhaps we should write it as P ( x , n ) , but since x has been chosen and will not change again throughout this proof, it is acceptable to leave x out of the notation and write P ( n ) .)

We must first prove that P ( 0 ) is true.

Subproof

The statement P ( 0 ) is ( 1 + x ) 0 1 + 0 x . Since 1 + x > 0 we have ( 1 + x ) 0 = 1 and we also have 1 + 0 x = 1 . So this statement says that an expression with value 1 is greater or equal to another expression with value 1 . Therefore P ( 0 ) is true.

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

We claim that using this assumption that we can show that P ( n + 1 ) is also true.

Subproof

Indeed, since n 0 our induction hypothesis says that ( 1 + x ) n 1 + n x holds, since this is what P ( n ) says and our induction hypothesis says that P ( n ) is true. Since x > -1 we have 1 + x > 0 so we can multiply both sides of the inequality ( 1 + x ) n 1 + n x by 1 + x giving

( 1 + x ) n + 1 1 + n x 1 + x

We can expand the right hand side of this as

1 + n x 1 + x = 1 + ( n + 1 ) x + n x 2 1 + ( n + 1 ) x

Putting these together we have

( 1 + x ) n + 1 1 + ( n + 1 ) x

which is precisely the statement P ( n + 1 ) . Therefore, for arbitrary n 0 the induction hypothesis implies that P ( n + 1 ) is also true.

Summing up, we showed that P ( 0 ) is true, and we also showed that if P ( 0 ) holds then P ( 1 ) is true. So we can deduce that P ( 0 ) and P ( 1 ) are both true. But by the argument just given it follows from this that P ( 0 ) and P ( 1 ) and P ( 2 ) are all true. This process continues for as many times as required to show that P ( 0 ) and P ( 1 ) and and P ( n ) are all true for any n 0 . We deduce that P ( n ) holds for all n 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 P ( 0 ) holds and P ( 0 ) , P ( 1 ) , , P ( n ) imply P ( n + 1 ) then P ( n ) holds for all n . 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 P ( n ) 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 x x + 1 . Then if the conditions for induction are correct for some statement P ( n ) , the set of objects satisfying P ( n ) is such a set of natural numbers containing 0 and closed under x x + 1 hence must be the whole of , since is the smallest such.

Here is another example of induction.

Proposition 2.2 (Triangle numbers)

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

Proof

Let P ( k ) be the statement n = 1 k n = k ( k + 1 ) / 2 .

We first prove that P ( 1 ) is true.

Subproof

The statement P ( 1 ) is n = 1 1 n = 1 ( 1 + 1 ) / 2 . The summation on the left hand side has a single term where n = 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 k 1 in the natural numbers be arbitrary and assume the following induction hypothesis.

We show that using this assumption that P ( k + 1 ) is also true.

Subproof

The expression n = 1 k + 1 n equals ( n = 1 k n ) + ( k + 1 ) . By our assumption P ( k ) is true so n = 1 k n = k ( k + 1 ) / 2 so n = 1 k + 1 n = k ( k + 1 ) / 2 + ( k + 1 ) = ( k + 1 ) ( k 2 + 1 ) = ( k + 1 ) ( k + 2 ) / 2 . Therefore n = 1 k + 1 n = ( k + 1 ) ( k + 2 ) / 2 is true. But this is exactly the statement P ( k + 1 ) , so we have succeeded in showing what we claimed.

So we have showed that P ( 1 ) is true, and we also showed that if k 1 is arbitrary and P ( 1 ) and P ( 2 ) and and P ( k ) are all true then P ( k + 1 ) is also true. We deduce that P ( k ) holds for all k 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).

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

4 Other common forms of induction

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

This is the P ( n ) implies P ( n + 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 P ( n ) implies P ( n + 1 ) form you assume P ( n ) is true whereas you could have assumed the much stronger statement that P ( 1 ) , P ( 2 ) ,..., P ( n ) 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 in the form something like 1 , 2 , , n 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.

Proposition 4.1 (Least number principle)

Suppose P ( x ) is a statement and s such that P ( k ) holds for some integer k s . Then there is a least integer k s such that P ( k ) holds.

Proof

This is by induction on the variable k starting at s . 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

Subproof

We now derive a contradiction by induction. Our contradiction will be that there is in fact no integer k s such that P ( k ) holds, and this is contrary to the assumptions in the proposition. Our induction statement Q ( k ) is the statement P ( k ) is false. We must prove a base case and an induction step.

The base case, Q ( s ) .

Subproof

If Q ( s ) were false, that would mean that P ( s ) is false is false, i.e. that P ( s ) is true. But then s is the least integer greater than or equal to s for which P ( s ) is true, since there is no smaller integer to consider, contrary to our assumption that there is no such least integer.

Now assume that k s is arbitrary and assume the induction hypothesis that

  • Q ( s ) , Q ( s + 1 ) , , Q ( k ) are all true.

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

Subproof

Indeed, if Q ( k + 1 ) were false, that would mean that P ( k + 1 ) is true. But by the induction hypothesis Q ( s ) , Q ( s + 1 ) , , Q ( k ) are all true and hence P ( s ) , P ( s + 1 ) , , P ( k ) are all false. So k + 1 would be the least integer greater than or equal to s such that P ( k + 1 ) is true. This is contrary to our assumption that there is no such integer. So therefore P ( k + 1 ) cannot be true and hence Q ( k + 1 ) is true.

It follows from the base case and the induction step that Q ( k ) is true for all integers k s by the principle of mathematical induction. Therefore P ( k ) is false for all integers k s , and this is contrary to one of the assumptions in the proposition, giving us the required contradiction.

Proposition 4.2 (Minimal counter-example)

Suppose P ( k ) is a statement that is false for some integer k s , where s . Then there is some least integer value of k s such that P ( k ) is false.

Proof

Let Q ( k ) be the statement that P ( k ) is false. So Q ( k ) is true for some k s since P ( k ) is false for some such k . But then by the previous proposition there is a least k with k s and Q ( k ) is true. And this k is the least integer k s such that P ( k ) is false.

We conclude with an application: the Archimedean Property of the reals says that for any x there is some n such that x n . It follows from this that every x has an integer part, [ x ] . To see this, let x and choose n , m such that x n and - x m . So - m x n . and let P ( k ) be the statement x k . Then the integer n is an integer greater than or equal to - m such that P ( n ) is true. So there is a least integer k - m such that P ( k ) . For this k we have k - 1 < x k since either k - 1 < - m x or else - m k - 1 and therefore P ( k - 1 ) is false (since k is least such that P ( k ) holds). Therefore k = x , the upper integer part of x . To get the lower integer-part x = [ x ] just argue that if x = k then k = x and if not then k - 1 < x < k so k - 1 = x .

This web page is available in xhtml, html and pdf. It is copyright and is one of Richard Kaye's Sequences and Series Web Pages. It may be copied under the terms of the Gnu Free Documentation Licence (http://www.gnu.org/copyleft/fdl.html). There is no warranty. Web page design and creation are by GLOSS.