Introduction to Induction (1.2.1, 1)

Knuth asks

Explain how to modify the idea of proof by mathematical induction, in case we want to prove some statement P(n) for all nonnegative integers - that is, for n = 0, 1, 2, ... instead of n = 1, 2, 3, ... .

To prove by induction



where n is a natural number and P is predicate we first prove P.0. We then prove



By renaming the dummy we can see that this is the same as saying