# Proof by induction

1. Sep 1, 2008

### duke_nemmerle

1. The problem statement, all variables and given/known data
Show, by induction, that for all whole number of Roubles greater than 7, the amount can be given without change by using only 3 rouble and 5 rouble notes.

2. Relevant equations
In other words for all $$n \in N, n > 7$$, there exist $$a, b \in N$$ such that $$n = 5a + 3b$$

3. The attempt at a solution
This is true for n = 8

I'm wondering if I can't use strong induction. I've noticed that all of these n's appear to be writable with $$a \in \{0,1,2\}$$ while letting b take on any value, and that when you express the integers greater than 7 in order the a's when thus constrained go 1, 0, 2, 1, 0, 2, etc and each time around the b increments by one for each repetition of a. So, I don't know if I can weasel something out of this like to go from n to n+1 means either going from 1 to 0, 0 to 2, or 2 to 1 in a with the associated incrementation, but I just get the feeling that this isn't the way to go. It seems I'm missing something easier.

2. Sep 1, 2008

### Tobias Funke

Looks like you're on the right track, and since it's true for n=8, it's true for n=18, n=28, etc. And if it's true for n=9...

3. Sep 2, 2008

### duke_nemmerle

I think the real trick on this was to use strong induction and notice that P(n+1) is implied by assuming P(1)...P(n) are true. Specifically, if P(n-2) is true, then P(n+1) is implied because it is three more than it, so if P(n-2) were written as 5a+3b, P(n+1) is 5a + 3(b+1)