Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

up vote 1 down vote accepted

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?

share|improve this answer
    
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<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
    
Ahh it all makes sense now! Induction gets me every single time.. –  Wooooop Dec 12 '12 at 0:06
    
@kevlar: Oh, good! (For the makes sense part, not the gets me. :-)) –  Brian M. Scott Dec 12 '12 at 0:08

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.