Induction
Justification of Second Principle
The second principle of induction
can also be used to prove assertions of the form
x P(x) .
This form of induction does not require the basis step, and in the inductive step
P(n) is proved assuming that
P(k) holds for all k
< n .
To see that this method is correct, note that the differences between the first and the second principles are
that the basis step is missing in the second principle and that the induction hypothesis assumes that
P(k) holds for all k < n.
Thus all we need to show to justify the second principle is that the basis case is implicitly included
in a proof by the second principle.
Suppose that
n [
k [ k < n
P(k) ]
P(n) ]
has been proven. We are going to show that this implies P(0).
Let n = 0 (or the smallest value being considered for n) here.
Then
k [ k < 0
P(k) ]
P(0) holds.
In this statement, k < 0 is false because 0 is the smallest value that is
being considered. Hence
[ k < 0
P(k) ]
is true for all values of k .
Hence for k [ k < 0
P(k) ]
P(0) ]
to hold true, P(0) must be true, which is the basis case.
Back to Second Principle
Next -- General Induction
Back to Schedule
Back to Table of Contents