0

In 1.2.1 Mathematical Induction section, Knuth presents mathematical induction as a two steps process to prove that P(n) is true for all positive integers n:

a) Give a proof that P(1) is true;

b) Give a proof that "if all P(1), P(2),..., P(n) are true, then P(n+1) is also true";

I have serious doubt about that. Indeed, I believe that point b) should be:

b) Give a proof that "if P(n) is true, then P(n+1) is also true". The major difference here is that you are only assuming that P(n) is true, not P(n-1), etc.

However, these books are old and have been read by many people (most of them being much more clever than I am^^).

So what is my confusion here?

4

1 回答 1

3

The entire point here is that the choice of n is arbitrary. Since P(n) implies P(n+1) is the conerstone of induction, then all the intermediate values between 1 and n will also hold under the assumption of P(n). You are supposed to show that if P(0) implies P(1) and P(n) implies P(n+1) then all conditions hold by the nature of n being arbitrary.

于 2013-03-15T08:17:30.310 回答