The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

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 

See for instance:

   POLY007:  Amount that cannot be paid in bills of m and n dollars   

If you have more questions, just write back.

Best regards,
- Doctor Floor, The Math Forum   
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.