Thread: Stong induction

I find that I am confused by strong induction.

I thought I understood it, but now I'm not sure if I have this correct.

Prob: Prove that all postages of $0.20 and more can be formed using only 5 cent and 6 cent stamps.

Do I list all these in the basis step, or should P(21), P(22), P(23), and P(24) be listed in the induction step?

Basis step: P(20): A postage of 20 cents can be formed using 5 cent and 6 cent stamps. Four 5 cent stamps = 20 cents, so P(20) is true.

P(21): A postage of 21 cents can be formed using 5 cent and 6 cent stamps. Three 5 cent and one 6 cent stamps = 21 cents so P(21) is true.

P(22): A postage of 22 cents can be formed using 5 cent and 6 cent stamps. Two 5 cent and two 6 cent stamps = 22 cents, so P(22) is true.

P(23): A postage of 23 cents can be formed using 5 cent and 6 cent stamps. One 5 cent and three 6 cent stamps = 23 cents, so P(23) is true.

P(24): A postage of 24 cents can be formed using 5 cent and 6 cent stamps. Four 6 cent stamps = 24 cents, so P(24) is true.

Inductive step: A postage of n cents can be formed using 5 and 6 cent stamps for 20 <= n <= k, k >= 24.

We need to prove that if k postage can be formed, then k+1 postage can be formed using just 5 and 6 cent stamps.

For the k+1 postage, note that with k >= 24, we have P(k - 4) to be true.
Add one 5 cent stamp to k - 4 and we have proved k + 1.

Since the basis step is true and the inductive step are true, the original statement is true by strong MI.

Please tell me if the stucture, process, and conclusions are valid.

Thanks

You can show this easier by realizing that 5 and 6 are relatively prime.

Originally Posted by oldguynewstudent

I find that I am confused by strong induction.

I thought I understood it, but now I'm not sure if I have this correct.

Prob: Prove that all postages of $0.20 and more can be formed using only 5 cent and 6 cent stamps.

Do I list all these in the basis step, or should P(21), P(22), P(23), and P(24) be listed in the induction step?

Basis step: P(20): A postage of 20 cents can be formed using 5 cent and 6 cent stamps. Four 5 cent stamps = 20 cents, so P(20) is true.

P(21): A postage of 21 cents can be formed using 5 cent and 6 cent stamps. Three 5 cent and one 6 cent stamps = 21 cents so P(21) is true.

P(22): A postage of 22 cents can be formed using 5 cent and 6 cent stamps. Two 5 cent and two 6 cent stamps = 22 cents, so P(22) is true.

P(23): A postage of 23 cents can be formed using 5 cent and 6 cent stamps. One 5 cent and three 6 cent stamps = 23 cents, so P(23) is true.

P(24): A postage of 24 cents can be formed using 5 cent and 6 cent stamps. Four 6 cent stamps = 24 cents, so P(24) is true.

Inductive step: A postage of n cents can be formed using 5 and 6 cent stamps for 20 <= n <= k, k >= 24.

We need to prove that if k postage can be formed, then k+1 postage can be formed using just 5 and 6 cent stamps.

For the k+1 postage, note that with k >= 24, we have P(k - 4) to be true.
Add one 5 cent stamp to k - 4 and we have proved k + 1.

Since the basis step is true and the inductive step are true, the original statement is true by strong MI.

Please tell me if the stucture, process, and conclusions are valid.

Thanks

This is quite long, maybe another member is willing to read through it. I think that the most instructive example of how to use strong induction is the following proof that every natural number greater than two may be written as the "product" of primes.

Theorem: Every natural number may be written as the product of primes.

Proof:

Base case- Clearly it is true for

Inductive hypothesis- Assume that for all we may write as the product of priems .

Inductive step- If is prime then we are done for we may write . So suppose that isn't prime. Then by definition for some . By induction hypotehsis though . Thus . the conclusion follows.

We wouldn't have used weak induction, for if we know that there isn't much we can say about

Originally Posted by oldguynewstudent

I find that I am confused by strong induction.

I thought I understood it, but now I'm not sure if I have this correct.

Prob: Prove that all postages of $0.20 and more can be formed using only 5 cent and 6 cent stamps.

Do I list all these in the basis step, or should P(21), P(22), P(23), and P(24) be listed in the induction step?

Basis step: P(20): A postage of 20 cents can be formed using 5 cent and 6 cent stamps. Four 5 cent stamps = 20 cents, so P(20) is true.

P(21): A postage of 21 cents can be formed using 5 cent and 6 cent stamps. Three 5 cent and one 6 cent stamps = 21 cents so P(21) is true.

P(22): A postage of 22 cents can be formed using 5 cent and 6 cent stamps. Two 5 cent and two 6 cent stamps = 22 cents, so P(22) is true.

P(23): A postage of 23 cents can be formed using 5 cent and 6 cent stamps. One 5 cent and three 6 cent stamps = 23 cents, so P(23) is true.

P(24): A postage of 24 cents can be formed using 5 cent and 6 cent stamps. Four 6 cent stamps = 24 cents, so P(24) is true.

Inductive step: A postage of n cents can be formed using 5 and 6 cent stamps for 20 <= n <= k, k >= 24.

We need to prove that if k postage can be formed, then k+1 postage can be formed using just 5 and 6 cent stamps.

For the k+1 postage, note that with k >= 24, we have P(k - 4) to be true.
Add one 5 cent stamp to k - 4 and we have proved k + 1.

Since the basis step is true and the inductive step are true, the original statement is true by strong MI.

Please tell me if the stucture, process, and conclusions are valid.

Thanks

Perhap's what you are thinking is this:

The sequence,

Yes, showing factorization into primes is a paradigmatic example of the use of strong induction.

oldguynewstudent: I believe your solution is correct. Whether to put the five initial cases into the base case or into the induction step is a matter of preference. You could prove as the base case. Then, in the induction step while proving from you could say this: "If or , then we give an explicit representation. Otherwise ( ) [the following you already have], , so we apply and add a 5-cent stamp".

I personally think those initial five statements belong to the base case.

One small remark.

Inductive step: A postage of n cents can be formed using 5 and 6 cent stamps for 20 <= n <= k, k >= 24.

We need to prove that if k postage can be formed, then k+1 postage can be formed using just 5 and 6 cent stamps.

I would explicitly say that the first sentence is the induction hypothesis. Then there would be no ambiguity about the status of the sentence: whether it is the hypothesis or the whole statement that has to be proved in the induction step.

By the way, did you know that strong induction is not really stronger than regular one? Every proof that uses strong induction can be rewritten so that it uses only regular induction. One only has to find the appropriate induction statement .

Originally Posted by emakarov

Yes, showing factorization into primes is a paradigmatic example of the use of strong induction.

oldguynewstudent: I believe your solution is correct. Whether to put the five initial cases into the base case or into the induction step is a matter of preference. You could prove as the base case. Then, in the induction step while proving from you could say this: "If or , then we give an explicit representation. Otherwise ( ) [the following you already have], , so we apply and add a 5-cent stamp".

I personally think those initial five statements belong to the base case.

One small remark.
I would explicitly say that the first sentence is the induction hypothesis. Then there would be no ambiguity about the status of the sentence: whether it is the hypothesis or the whole statement that has to be proved in the induction step.

By the way, did you know that strong induction is not really stronger than regular one? Every proof that uses strong induction can be rewritten so that it uses only regular induction. One only has to find the appropriate induction statement .

Thank you very much for the information. I only wish my professor was as informative. Also the text is the worst I've ever dealt with. I have a secondary text to use for additional information but it is hard to coordinate between the two. Your answer clears up most of my confusion. Yes, I do realize that strong induction is not really "stronger" but is useful in cases where additional steps are needed to get from k to k+1.

Best wishes for the upcoming holidays.

Originally Posted by Drexel28

This is quite long, maybe another member is willing to read through it. I think that the most instructive example of how to use strong induction is the following proof that every natural number greater than two may be written as the "product" of primes.

Theorem: Every natural number may be written as the product of primes.

Proof:

Base case- Clearly it is true for

Inductive hypothesis- Assume that for all we may write as the product of priems .

Inductive step- If is prime then we are done for we may write . So suppose that isn't prime. Then by definition for some . By induction hypotehsis though . Thus . the conclusion follows.

We wouldn't have used weak induction, for if we know that there isn't much we can say about

Ah, yes I see that n is really the k+1 case. Thank you very much.

Happy holdiays!