Mathematical Induction

Date: 01/28/2002 at 17:24:11
From: Ali
Subject: Mathematical Induction

Here is my question:

Use Mathemetical Induction to prove that any postage of at least 8 
cents can be obtained using 3- and 5-cent stamps.

Date: 01/29/2002 at 06:39:24
From: Doctor Floor
Subject: Re: Mathematical Induction

Hi, Ali,

Thanks for your question. This will be a pretty weird use of 
mathematical induction!

First we check the correctness of the theorem for 8, 9 and 10 cents:

  8 = 3+5 okay
  9 = 3*3 okay
 10 = 2*5 okay

Now our induction hypothesis will be that the theorem is correct for 
m = 8 up to m = n, for n > 10. So for all these m we can use stamps of 
3 and 5 cents.

More specifically, if the theorem is correct for m = 8 up to m = n, 
then it is correct for m = n-3. Let's say that n-3 = a*3 + b*5 for 
some positive integers a and b. Then of course n = (a+1)*3 + b*5 can 
be paid with stamps of 3 and 5 cents as well.

That proves our theorem with mathematical induction.

The problem can be made more general, when we start with stamps of a 
and b cents, and ask what amounts cannot be paid with these stamps. 
This is sometimes referred to as the Frobenius Problem or Sylvester's 
theorem.

See for instance:

   POLY007:  Amount that cannot be paid in bills of m and n dollars 
   http://forumgeom.fau.edu/POLYA/ProblemCenter/POLYA007.html   

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum
  http://mathforum.org/dr.math/