Proof by Induction: 3 & 5 Rouble Notes for All N>7

[duke_nemmerle]

Homework Statement

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.

Homework Equations

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

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.

 

[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...

 

[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)