Results 1 to 7 of 7

Math Help - Stong induction

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2009
    Posts
    95
    You can show this easier by realizing that 5 and 6 are relatively prime.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by oldguynewstudent View Post
    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 n\ge2 may be written as the product of primes.

    Proof:

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

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

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

    We wouldn't have used weak induction, for if we know that n=p_1\cdots p_n there isn't much we can say about n+1
    Last edited by Plato; December 2nd 2009 at 01:39 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by oldguynewstudent View Post
    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, S_j= 6j+5(n-j), 0\leq j \leq n, 4 \leq n, n \in N
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,536
    Thanks
    778
    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 P(20) as the base case. Then, in the induction step while proving P(k+1) from \forall n.\,20\le n\le k\to P(k) you could say this: "If k +1 = 21, 22, 23, or 24, then we give an explicit representation. Otherwise ( k+1\ge 25) [the following you already have], 20\le k-4\le k, so we apply 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 P.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Smile I needed a sanity check before my test tomorrow

    Quote Originally Posted by emakarov View Post
    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 P(20) as the base case. Then, in the induction step while proving P(k+1) from \forall n.\,20\le n\le k\to P(k) you could say this: "If k +1 = 21, 22, 23, or 24, then we give an explicit representation. Otherwise ( k+1\ge 25) [the following you already have], 20\le k-4\le k, so we apply 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 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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Thank you, this makes things much clearer

    Quote Originally Posted by Drexel28 View Post
    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 n\ge2 may be written as the product of primes.

    Proof:

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

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

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

    We wouldn't have used weak induction, for if we know that n=p_1\cdots p_n there isn't much we can say about n+1
    Ah, yes I see that n is really the k+1 case. Thank you very much.

    Happy holdiays!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Induction help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 22nd 2010, 10:33 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 19th 2008, 05:12 PM

Search Tags


/mathhelpforum @mathhelpforum