Mathematical InductionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/