1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Math Question ( not really homework) about strong induction

  1. Mar 20, 2012 #1
    For some questions strong induction would test for cases n+1, n+2 and for other n+1,n+2,n+3, or other ways, why is that? Here's two examples

    Suppose that the only paper money consists of 3-dollar bills and 10-dollar bills. Find what dollar amounts
    can be made from a combination of these bills. Prove your result.
    SOLUTION: Clearly the amounts $3, $6, $9, $10, $12, $13, $15, $16, $18 can all be made using 3-dollar bills and 10-dollar bills. In addition any amount greater than $17 be made as well. To prove this we use strong induction.
    Base case: $18 can be made from 6 3-dollar bills, $19 can be made from one 10-dollar bill and three 3-dollar
    bills. And of course, $20 can be made from two 10-dollar bills.

    and the other example,

    prove that every amount of postage of 12 cents or more can be formed using just 4-cent and

    base case

    we can form postage of 12, 13 ,14 ,15 cents using three 4-cent stamps, two 4- cents stamps ... etc this shows that P(12),P(13), P(14) and P(15) are true.
  2. jcsd
  3. Mar 20, 2012 #2


    User Avatar
    Science Advisor

    It is never necessary to "test for n+1, n+2, ...". You need to show a statement is true for n= 0, then show "if the statement is true for all [itex]k\le n[/itex] then it is true for n= k+1".

    (The difference between "strong induction" and "weak induction" is that strong induction allows you to assume "true for all [itex]k\le n[/itex]" while weak induction uses only "true for k= n".)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook