Proof by induction

  • #1

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


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.
 

Answers and Replies

  • #2
131
40
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
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)
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
888
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
780
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
2
Views
769
  • Last Post
Replies
3
Views
940
  • Last Post
Replies
2
Views
923
  • Last Post
Replies
5
Views
1K
Top