Graphics Reference
In-Depth Information
1
Mathematical induction
Prelimary reading:
Rosenbaum, Polya ch. 7.
Concurrent reading:
Sominskii.
Further reading:
Thurston chs 1 and 2, Ledermann and Weir.
The set of all whole numbers
1, 2, 3, . . .
is often denoted by N.We
will usually call N thest of
natural numbers
, and, sometimes, the set of
positive integers
. Notethat N excludes 0.
n
(
n
1)(2
n
1)
n
1
1
2
3
...
.
6
Is this proposition trueor fals?
Test it when
n
3.
How many values of
n
should you test if you want to besureit is
truefor all natural numbrs
n
?
1,
n
2 and
n
n
(
n
1)(2
n
1)
If wewrite
f
(
n
)
, show that
6
f
(
n
)
(
n
1)
f
(
n
1).
Now supposethat theproposition with which westarted holds for
someparticular valueof
n
: add (
n
1)
to both sides of the
equation and deduce that the proposition holds for the next value
of
n
.
Since we have already established that the proposition holds for
n
1, 2, and 3, the argument we have just formulated shows that it
must hold for
n
4, and then by the same argument for
n
5, and
so on.
2
When
n
is a natural number, 6
5
n
4 is divisibleby 5.
