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