Homework Help: Different statement of strong induction proof

1. Dec 3, 2013

amarch

1. The problem statement, all variables and given/known data

Let m, i be ﬁxed positive integers.

Prove: If we have P(m),P(m+1),...P(m+i) all true and [P(m)∧P(m+1)∧⋯∧P(k)]⟹P(m+1) true for every integer k≥m, then P(n) is true for all integers n≥m .

2. Relevant equations
strong induction, our book defines this as

1) if P(1) is true
2) If (P(1) ∧ P(2) ∧ ... ∧ P(k)) implies P(k+1)
then P(n) is true for all positive integers n.

3. The attempt at a solution

I figured out how to prove it using contradiction and well ordering. Suppose the statement is false, i.e. there exists a least No such that P(No) is false. But we know from the problem statement that P(m)∧P(m+2)∧...∧P(No-1) holds and by the given condition P(No) must also hold, which gives us a contradiction.

...but I was told there is a way to do it using strong induction on n. Isn't the proof trivial because this is just a special case of strong induction, i.e. since we can just set m=1 like in the formal statement of strong induction and let i=0 so that the statement is precisely the statement of strong induction.

Last edited: Dec 3, 2013