- #1
amarch
- 7
- 0
Homework Statement
Let m, i be fixed 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 .
Homework 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.
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: