# Strong inducti0n with 3- and 5-peso notes and can pay any number greater than 7.

A bank has an unlimited supply of 3-peso and 5-peso notes. Prove that it can pay any number of pesos greater than 7.

So i'm not completely sure how to use strong induction, but the base case is pretty simple.

Base case:

n = 8,9,10

8 = 5 + 3; 9 = 3+3+3; 10= 5+5

Can anyone help me with the inductive step?

-
 If you can pay 8 pesos, then you can pay 3 more, using a 3-peso note. – Mario Carneiro Dec 11 '12 at 23:05 Hint: to know that you can pay $n$ peso, it is enough to know that you can pay $n-3$ peso. – dtldarek Dec 11 '12 at 23:07 This is one of the problems discussed at math.stackexchange.com/questions/186356/… – Gerry Myerson Dec 11 '12 at 23:09 Very similar problems discussed at math.stackexchange.com/questions/102222/… and math.stackexchange.com/questions/246943/… and math.stackexchange.com/questions/99712/… and math.stackexchange.com/questions/235320/stamp-problem-homework and math.stackexchange.com/questions/145189/… and probably several others. – Gerry Myerson Dec 11 '12 at 23:12 this is an old Q. – ashley Dec 11 '12 at 23:20
show 1 more comment

Suppose that $n>10$, and you can make any amount that is less than $n$ and greater than $8$; then you can certainly make $n-3$. Now, how can use that to make $n$? That is, if you can make $n-3$ with, say, $a$ $3$-peso and $b$ $5$-peso notes, how many of each can you use to make a total of $n$ pesos?
 So we can assume that every integer smaller than n but greater than 8, can be expressed as a combination of 3- and 5- pesos. My confusion lies in proving n+3.. – Wooooop Dec 11 '12 at 23:59 @kevlar: But that’s not what you should be doing. Let $P(k)$ be the statement that you can make the amount $k$ using only $3$- and $5$-peso notes. The induction step (as I would carry it out) consists in showing that if $n>10$, and $P(k)$ holds for $8\le k Hint: For$n$large (think about how large), how can we reduce the problem of paying$n\$ pesos into paying a smaller amount? If we can do that, we are done by induction.