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.
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
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
induction, and it is usually just called
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 , and if we can also show that by assuming it true for we can prove it true for , then our statement will therefore true for all natural numbers . 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 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.
We start with some examples of results to be proved by induction.
Let in and . Then .
The statement to be proved is,
For all real numbers and all
the inequality is true.
We start by letting 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 . 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
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 is true.
The statement is
We now consider an arbitrary 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 is also true.
Indeed, since our induction hypothesis says that holds, since this is what says and our induction hypothesis says that is true. Since we have so we can multiply both sides of the inequality by giving
We can expand the right hand side of this as
Putting these together we have
which is precisely the statement . Therefore, for arbitrary the induction hypothesis implies that is also true.
Summing up, we showed that is true, and we also showed that if holds then is true. So we can deduce that and are both true. But by the argument just given it follows from this that and and are all true. This process continues for as many times as required to show that and and and are all true for any . We deduce that holds for all 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 holds and , , , imply 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 and closed under . Then if the conditions for induction are correct for some statement , the set of objects satisfying is such a set of natural numbers containing and closed under hence must be the whole of , since is the smallest such.
Here is another example of induction.
Proposition on triangle numbers.
Let be a natural number. Then the th triangle number is equal to .
Let be the statement
We first prove that is true.
The statement is
We now let in the natural numbers be arbitrary and assume the following induction hypothesis.
We show that using this assumption that is also true.
The expression equals . By our assumption is true so so . Therefore is true. But this is exactly the statement , so we have succeeded in showing what we claimed.
So we have showed that is true, and we also showed that if is arbitrary and and and and are all true then is also true. We deduce that holds for all in by the principle of mathematical 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.
safestbecause 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.
For students who first see induction, the usual form it takes is the following:
This is the
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
form you assume is true whereas
you could have assumed the much stronger statement that ,
,..., 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
As a useful rule of thumb, any proof that you see which contains an ellipsis looking like in a form such as 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.
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
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, .
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
We claim that it follows that is true.
Indeed, if were false, that would mean that is true. But by the induction hypothesis , , , are all true and hence , , , are all false. So would be the least integer greater than or equal to such that is true. This is contrary to our assumption that there is no such integer. So therefore cannot be true and hence 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.
Let be the statement that
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
of the reals says that for any there is
some such that . It follows
from this that every has an
. To see this, let
and choose such that
and . So . and let
be the statement