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,
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.
Bernoulli's inequality.
Let
Proof.
The statement to be proved is,
For all real numbers
We start by letting
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
(
(1+.)^{ } 1+
Notice that
(
(
(
We must first prove that
(0)
is true.Subproof.
The statement
(0)
is(1+. Since 1+)^{01+0 }
(0)
is true.We now consider an arbitrary
(0)
,(1)
,(2)
,(
We claim that using this assumption that we can show that
(
Subproof.
Indeed, since
(
(
We can expand the right hand side of this as
Putting these together we have
which is precisely the statement
(
(
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(
(
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)
,(
(
(
(
(
(
Here is another example of induction.
Proposition on triangle numbers.
Let
Proof.
Let
(
.=1 = ( +1)/2
We first prove that
(1)
is true.Subproof.
The statement
(1)
is. The summation on the left hand side has a single term where=1 1=1(1+1)/2
We now let
(1)
,(2)
,(
We show that using this assumption that
(
Subproof.
The expression
(
(
So we have showed that
(1)
is true, and we also showed that if(1)
and(2)
and(
(
(
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).
(
(
(0)
and(1)
and(
(
(
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,
(
(
For students who first see induction, the usual form it takes is the following:
(
(1)
is true;(
(
(
This is the
(
(
form you assume(
implies) (
+1)
(
(1)
,(2)
,...,(
As a useful rule of thumb, any proof that you see which
contains an ellipsis looking like
Least number principle.
Suppose
(
(
(
Proof.
This is by induction on the variable . 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
(
(is the statement)
. We must prove a base case and an induction step.(
is false)
The base case, (
.)
Subproof.
If (
were false, that would mean that
)
()
()
()
Now assume that
(,)
(,+1)
(are all true.)
We claim that it follows that (
is true.
Subproof.
Indeed, if (
were false, that would mean that
(
(,)
(,+1)
(are all true and hence)
()
(+1)
(
(
(
(is true.+1)
It follows from the base case and the induction step
that (
is true for all integers
(
Minimal counter-example principle.
Suppose
(
(
Proof.
Let (
be the statement that
(
(is true for some)
(
(is true. And this)
(
We conclude with an application: the
Archimedean Property
of the reals says that for any
(
. Then the integer
(
(
(
(