Different statement of strong induction proof

In summary, the conversation discusses how to prove a statement using strong induction on a fixed positive integer. The statement is proven by contradiction and well ordering, but it is also mentioned that there is a way to prove it using strong induction directly. It is suggested to use the statement of strong induction with m=1 and i=0.
  • #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:
Physics news on Phys.org
  • #2
If so, am I allowed to just say that?I feel like there should be more to it, but can't think of anything else...
 

FAQ: Different statement of strong induction proof

1. What is a statement of strong induction?

A statement of strong induction is a mathematical proof technique used to show that a statement is true for all natural numbers. It is based on the principle of mathematical induction, but involves considering multiple base cases instead of just one.

2. How does strong induction differ from regular induction?

Regular induction only requires proving a statement for one base case and then showing that it holds for the next case. Strong induction, on the other hand, requires proving the statement for multiple base cases and showing that it holds for all subsequent cases.

3. When is strong induction necessary?

Strong induction is necessary when a statement cannot be proven using regular induction. This usually occurs when the statement involves multiple base cases or relies on previous cases to be true.

4. What is the general format for a strong induction proof?

The general format for a strong induction proof is as follows:

  1. State the statement to be proven.
  2. Identify the base cases (usually the first few natural numbers).
  3. Prove the statement for the base cases.
  4. Assume the statement holds for all natural numbers up to some arbitrary number k.
  5. Show that the statement holds for the next natural number (k+1).
  6. Conclude that the statement holds for all natural numbers by strong induction.

5. Can strong induction be used to prove any statement?

No, strong induction can only be used to prove statements that are true for all natural numbers. It cannot be used for statements that are only true for a specific range of natural numbers or for real numbers.

Back
Top