Math Help - Induction Problem

1. Induction Problem

Suppose you are in a country that has bank notes of value $3 and$5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than $7. Thank you for your help in advance. 2. Originally Posted by MathStudent1 Suppose you are in a country that has bank notes of value$3 and $5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than$7.

This is the Frobenius coin problem for n=2.
The general idea is that whenever gcd(3,5)=1 you can go on forever eventually.

This formula in this case is,
(x-1)(y-1)=(5-1)(3-2)=8
Thus, 8 is the smallest number from where everything is obtainable, or you can think of it as 7 is the largest number from which no combination is possible.

3. Originally Posted by MathStudent1
Suppose you are in a country that has bank notes of value $3 and$5 only. Prove that it is possible to pay (without requiring change) for any item which is worth a whole number of dollars greater than $7. Thank you for your help in advance. Suppose that you can make some total n>15, If no 5's are used then convert 5x3's to 3x5's, So we can always make n with at least 1x5. Now add 2x3 and take away 1x5, so we have now made n+1. So if there is any total N>15 which we can make with 3's and 5's then by induction we have proven that we can make any total n>N. Let N=$20, then we can make it as 5x3+1x5, hence we have proven that
any total >$20 can be made with$3 and $5 bills by induction. (Note with a bit more care we can reduce the mimimum sum that can be made to the the$8 in ImPerfectHackers post, but the question does not
ask for a tight lower limit, so we don't need that complication).

RonL

4. Thank you CaptainBlack. I guess I don't see how this problem is an induction problem? I am familiar with doing induction problems that involve summation or inequalities. Thanks again.

5. Hello, MathStudent1!

I think I can hammer this into an Induction proof . . .

Suppose you are in a country that has bank notes of value $3 and$5 only.
Prove that it is possible to pay (without requiring change) for any item
which is worth a whole number of dollars greater than $7. Since the value (V) is greater than 7: .V > 8. S(1): The first case is V = 8, which can be made with 3 + 5. Assume S(k): that V = k can be expressed as a combination of 3's and/or 5's. We must prove S(k+1): that k + 1 can be expressed as a combination of 3's and/or 5's. There are two possible cases for the value of k: (1) k is a multiple of 3. .Then k = 3a, for some integer a. . . .Since k > 8, a must be at least 3. .There are at least three$3 bank notes.
Then we can create k + 1 by adding two $5 notes and removing three$3 notes.

(2) k is not a multiple of 3. .There is at least one $5 bank note. Then we can create k + 1 by adding two$3 bank notes and removing one \$5 dollar bank note.

In either case, given k dollars, we can create k+1 dollars.

We have proved that: .S(k) . .S(k+1).
. . The induction proof is complete.

6. Thank you Soroban. I am still working on the problem and trying to see it all.