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.

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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search