General strong induction question

[Syrus]

Homework Statement

I have been studying induction for a few days now and am able to produce some proofs, but have some inquiries as to its theory. First, in strong induction, it seems that different sources disagree on whether base cases are necessary to include within the proofs. Is there any clarification which may be provided for this? My main text says they are not required due to the structure of the inductive step. I do, nonetheless, see strong induction proofs with 1 or more base cases displayed.

Also, what is wrong with the following strong induction "counterexampe" I have come up with as a contradiction to this method?

Show that for all natural numbers x, 0 + x = 0 . [natural numbers = 0, 1, 2,...]

by strong induction, for x = 0, there are no the natural numbers less than 0, so 0 + x = 0 is true since the statement (if, for any x, for all k less than x, P(k) holds, then p(x) holds) is vacuously true. Thus, since it is true for 0, we may use strong induction with x = 1 to show that 0 + 1 = 0, an obvious contradiction.

Homework Equations

The Attempt at a Solution

 

[Oriako]

I was under the impression that 0 is not a natural number?

In any case, I believe some books define it to be so, so if we show that it is true for the basis step: 0+0=0, which is true. Then by induction we assume for any arbitrary integer k, that $$0 + k = 0$$. Using this assumption we need to show that for $$0 + (k+1) = 0$$. So, we can then say that in the k+1 case, $$0 + k + (k+1) = 0 + 2k +1 \neq 0$$ and so, this is just a faulty "proof" of that assumption you wanted to prove, namely 0 + k = 0. The dominion of mathematical induction has not crumbled as by assuming induction works we got an inconsistent proof to affirm a result we knew was false. In fact, to show that for all number numbers, 0 + k = 0 is false; we just need to say that let k = 2 and $$0 + 2 \neq 0$$, so the statement, "For all natural numbers, 0 + k = 0", is false.

 

[Syrus]

I see what your saying. However, I was referring to the strong induction case in which the hypothesis is vacuously true and thus implies the result for all natural numbers.. I know this is a trivial case... but I'm wondering if there is a deeper matter with the proof or theory (i.e. if this were a more complicated matter it may not be as readily detectable).

 

[Oriako]

I'm not picking up what you're putting down in regards to the deeper nature of the proof technique here.

Induction says that if P(1) is true, and you can prove P(k+1) is true by assuming P(k) is true for an arbitrary element k, then it is true for P(n).

Strong induction says that if P(1),...,P(a) is true and for an arbitrary k > a or k= a, if P(i) is true for all $$i \in {1,2,...,k}$$ Then P(k+1) is true. So, P(n) is true.