Stamp Example

Show that you can make any amount of stamps from  >= 8-cents from 
any amount of 3- and 5-cent stamps.

Base Case: one 3-cent and one 5-cent stamp makes 8-cents.

Inductive hypothesis: Assume you can k-cents >= 8-cents.

Inductive step(s): 
   Break into two sub-problems:
  
   (1) k is a multiple of 3:
       k=3*a, where x >= 3

       So, can you get k+1 cents where k is a multiple of 3?

       To get (k+1), take away three 3-cent stamps and add two 5-cent stamps.

       Huh? Try this: 3k+1 = 3a+1
            Add and take away stamps: 
            3a+1-2+2*5 = 3a+9
            Since 9 is divisible by 3 and 3k is too, 3k+9 is divisible by 3.

   (2) k is not a multiple of 3:
       Assume x 3-cent stamps. 
       Assume y 5-cent stamps. y>=1 becase we're assuming k is not div. by 3.
       k = 3x+5y

       So, can you get (k+1)?

       To get k+1, take away a 5-cent stamp and put in two 3-cent stamps.
   
       Huh? Try this: k+1=3x+5y+1
            Add and take away stamps:
            3x+5y+1-2*3 = 3x+5y-5
            If x=0, divisible by 5, so OK
            If y=1, divisilbe by 3, which we already prooved.

Conclusion: Since every integer k is either a multiple of 3 or not, 
            we have prooved the statement.


Alternative solutions:
- do three bases cases: 8, 9, 10
- assume k is multiple of 5 or not