1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by induction

  1. Sep 1, 2008 #1
    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 [tex]n \in N, n > 7[/tex], there exist [tex] a, b \in N [/tex] such that [tex] n = 5a + 3b [/tex]

    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 [tex]a \in \{0,1,2\}[/tex] 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. jcsd
  3. Sep 1, 2008 #2
    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...
  4. Sep 2, 2008 #3
    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)
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook