0
$\begingroup$

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?

  • 0
    If you can pay 8 pesos, then you can pay 3 more, using a 3-peso note.2012-12-11
  • 0
    Hint: to know that you can pay $n$ peso, it is enough to know that you can pay $n-3$ peso.2012-12-11
  • 0
    This is one of the problems discussed at http://math.stackexchange.com/questions/186356/non-trivial-induction-order2012-12-11
  • 0
    Very similar problems discussed at http://math.stackexchange.com/questions/102222/strong-mathematical-induction and http://math.stackexchange.com/questions/246943/mathematical-induction-stamps and http://math.stackexchange.com/questions/99712/representing-any-n-geq-4-as-a-sum-of-2s-and-5s and http://math.stackexchange.com/questions/235320/stamp-problem-homework and http://math.stackexchange.com/questions/145189/examples-of-mathematical-induction and probably several others.2012-12-11
  • 0
    this is an old Q.2012-12-11
  • 0
    In case you're curious, there is such a thing as a 3-peso note. http://en.wikipedia.org/wiki/File:Cuban3Pesos.jpg2012-12-11

2 Answers 2

1

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?

  • 0
    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..2012-12-11
  • 0
    @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, then $P(n)$ holds. It then follows immediately by strong induction that $P(n)$ holds for all $n\ge 8$.2012-12-12
  • 0
    Ahh it all makes sense now! Induction gets me every single time..2012-12-12
  • 0
    @kevlar: Oh, good! (For the *makes sense* part, not the *gets me*. :-))2012-12-12
0

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.