1. Not finding help here? Sign up for a free 30min 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!

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)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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)

Loading...