this assertion and set Sto be the set of all natural num-
bers for which this assertion is true:
P(n):1 + 2 + 3 +…+ n= n(n+ 1)
S= {n: the formula P(n) is true}
Our aim is to show that all natural numbers belong to
S(that is, that P(n) is true for all natural numbers n).
We must establish two things:
1. The number 1 belongs to S.
Entering n= 1 into the formula yields the patently
true statement 1 = ×1 ×(1 + 1). Thus P(1) is true
and 1 ∈S.
2. Assume that the number kbelongs to S. That is,
assume that the formula
1 + 2 +…+k= k(k+ 1)
is true. Does it necessarily follow that the corre-
sponding formula for k+ 1 is valid? That is, can we
then deduce, under this assumption, that
1 + 2 +…+ k+ (k+ 1) = (k+ 1)((k+ 1) + 1)
will hold?
To achieve this, start with the equation P(k),assumed
to be valid, and add the quantity k+ 1 to both sides.
This gives:
1 + 2 +…+ k+ (k+ 1) = k(k+ 1) + (k+ 1)
After rearranging and regrouping terms on the right,
this reads:
1 + 2 +…+ k+ (k+ 1) = (k+ 1)(k+ 2)
which is the statement P(k+ 1). By the principle of
mathematical induction, it now follows that the set S
does indeed contain all the natural numbers, that is,
P(n) is a valid formula for all values of n.
The principle of mathematical induction is a pow-
erful technique that can establish the validity of an infi-
nite number of statements in one fell swoop. As
illustrated above, it is particularly useful for establish-
ing formulae and equations involving the natural num-
bers. One disadvantage, however, is that this method of
proof gives no indication as to what the appropriate
formula to be proved should be: the inductive method
of proof offers no insight, for instance, as to why the
formula for the sum of the first ncounting numbers is
n(n+ 1). One must arrive at candidates for formulae
via other means.
The inductive process is often likened to knocking
down a chain of dominoes. To successfully topple a
row of standing dominoes one must:
1. Knock down the first domino
2. Be certain that the dominoes are appropriately
spaced so that when any one domino falls, it is sure
to knock down the next
If one can establish that these two properties hold,
then all dominoes in a chain (even an infinitely long
one) will fall.
Despite the elegance and simplicity of the principle,
one must still apply care when utilizing the principle of
mathematical induction. The following amusing argu-
ment, for instance, illustrates what can go wrong:
Claim: all horses are the same color.
We “prove” this as follows: Let Sbe the set of all natu-
ral numbers for which the following statement is true.
P(n):if nhorses stand in a field, then all horses
in that field are the same color.
Clearly P(1) is true: if only one horse is standing in a
field, then all horses in that field are the same color.
Now make the assumption, despite its absurdity, that
P(k) is true, that is, any khorses in a field must be the
same color. Now consider k+1 horses in a field. Remove
one horse, Chester, say. This leaves khorses in the field,
which, by our assumption, must all be the same color.
Return Chester to the field and remove a different
horse. This again leaves khorses in the field, which, by
assumption, must all be the same color. This shows that
Chester is the same color as the first khorses, and in
fact that all k+1 horses are the same color. We have,
from P(k),established that P(k+1) follows. By the prin-
ciple of mathematical induction, it now follows that
P(n) is true, no matter the value of n. In particular, all
the horses in the world are the same color.
1
–
2
1
–
2
1
–
2
1
–
2
1
–
2
1
–
2
1
–
2
266 induction