
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!

Proof by induction

  1. Sep 1, 2008 #1
    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)

Have something to add?

Similar Discussions: Proof by induction
  1. Proof by induction (Replies: 2)

  2. Proof by induction (Replies: 9)

  3. Proof by induction (Replies: 32)

  4. Induction Proof (Replies: 14)

  5. Proof by Induction (Replies: 6)