# 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
this is an old Q. – ashley Dec 11 '12 at 23:20

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?
@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<n$, then $P(n)$ holds. It then follows immediately by strong induction that $P(n)$ holds for all $n\ge 8$. – Brian M. Scott Dec 12 '12 at 0:04
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.