# Thread: Stong induction

1. ## 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 2. You can show this easier by realizing that 5 and 6 are relatively prime. 3. 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 $\displaystyle n\ge2$ may be written as the product of primes.

Proof:

Base case- Clearly it is true for $\displaystyle n=2=2\cdot 1$

Inductive hypothesis- Assume that for all $\displaystyle k<n$ we may write $\displaystyle k$ as the product of priems $\displaystyle p_1\cdots p_\ell$.

Inductive step- If $\displaystyle n$ is prime then we are done for we may write $\displaystyle n=n\cdot 1$. So suppose that $\displaystyle n$ isn't prime. Then by definition $\displaystyle n=a\cdot b$ for some $\displaystyle a,b<n$. By induction hypotehsis though $\displaystyle a=p_1\cdots p_n,b=p'_1\cdots p'_m$. Thus $\displaystyle n=a\cdot b=p_1\cdots p_n\cdot p'_1\cdots p'_m$. the conclusion follows.$\displaystyle \square$

We wouldn't have used weak induction, for if we know that $\displaystyle n=p_1\cdots p_n$ there isn't much we can say about $\displaystyle n+1$

4. 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,$\displaystyle S_j= 6j+5(n-j), 0\leq j \leq n, 4 \leq n, n \in N$5. 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$\displaystyle P(20)$as the base case. Then, in the induction step while proving$\displaystyle P(k+1)$from$\displaystyle \forall n.\,20\le n\le k\to P(k)$you could say this: "If$\displaystyle k +1 = 21, 22, 23,$or$\displaystyle 24$, then we give an explicit representation. Otherwise ($\displaystyle k+1\ge 25$) [the following you already have],$\displaystyle 20\le k-4\le k$, so we apply$\displaystyle P(k-4)$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$\displaystyle P$. 6. ## I needed a sanity check before my test tomorrow 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$\displaystyle P(20)$as the base case. Then, in the induction step while proving$\displaystyle P(k+1)$from$\displaystyle \forall n.\,20\le n\le k\to P(k)$you could say this: "If$\displaystyle k +1 = 21, 22, 23,$or$\displaystyle 24$, then we give an explicit representation. Otherwise ($\displaystyle k+1\ge 25$) [the following you already have],$\displaystyle 20\le k-4\le k$, so we apply$\displaystyle P(k-4)$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$\displaystyle P$. 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. 7. ## Thank you, this makes things much clearer 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$\displaystyle n\ge2$may be written as the product of primes. Proof: Base case- Clearly it is true for$\displaystyle n=2=2\cdot 1$Inductive hypothesis- Assume that for all$\displaystyle k<n$we may write$\displaystyle k$as the product of priems$\displaystyle p_1\cdots p_\ell$. Inductive step- If$\displaystyle n$is prime then we are done for we may write$\displaystyle n=n\cdot 1$. So suppose that$\displaystyle n$isn't prime. Then by definition$\displaystyle n=a\cdot b$for some$\displaystyle a,b<n$. By induction hypotehsis though$\displaystyle a=p_1\cdots p_n,b=p'_1\cdots p'_m$. Thus$\displaystyle n=a\cdot b=p_1\cdots p_n\cdot p'_1\cdots p'_m$. the conclusion follows.$\displaystyle \square$We wouldn't have used weak induction, for if we know that$\displaystyle n=p_1\cdots p_n$there isn't much we can say about$\displaystyle n+1\$
Ah, yes I see that n is really the k+1 case. Thank you very much.

Happy holdiays!