• Support PF! Buy your school textbooks, materials and every day products Here!

Prove that every integer n>= 14 is a sum of 3's and/ or 8's.

  • Thread starter snaidu228
  • Start date
  • #1
9
0

Homework Statement



Prove that every integer n>= 14 is a sum of 3's and/ or 8's.

Homework Equations



Induction Hypothesis

The Attempt at a Solution



Base Case: P(0):

Suppose n= 14, and k is an integer representing number of times 3 or 8 is added:
14= 3k;
k=14/3 ( this shows that 14 is not a sum of 3's)

But the question says to show that. I'm confused on how to show that.
 

Answers and Replies

  • #2
27
0
14= 3+3+8
it's and/or
 
  • #3
33,481
5,169
You need to be able to show that every number >= 14 is a linear combination of 3s and 8s. IOW, that n = 3a + 8b for some integer values of a and b, with a >= 0, b >= 0. (I don't think that either a or b can be negative, but either one could be zero.)

That's what you need to show, but I don't have any idea right now of how to go about doing this.
 
  • #4
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
IOW, that n = 3a + 8b for some integer values of a and b, with a >= 0, b >= 0. (I don't think that either a or b can be negative, but either one could be zero.)
That parenthetical remark is essential. Consider n=13. This has solutions for a,b in the integers. For example, a,b = -1,2 and 7,-1 are both solutions to 3a+8b=13. In fact, given any integer n, there are an infinite number of solutions a,b in Z such that 3a+8b=n. So the problem is to not only show that integer solutions a,b exist but also to show that at least one such solution has both a and b non-negative.
 
  • #5
D H
Staff Emeritus
Science Advisor
Insights Author
15,393
683
BTW, induction might not be the best choice here. Start with multiples of 3, n=3m. This obviously has a,b=m,0 as one solution to 3a+8b=n, and this a,b is in the non-negative integers if n is non-negative. What can you say about the two adjacent integers, n-1 and n+1?
 

Related Threads on Prove that every integer n>= 14 is a sum of 3's and/ or 8's.

Replies
1
Views
1K
  • Last Post
Replies
1
Views
4K
Replies
1
Views
439
Replies
1
Views
3K
Replies
18
Views
3K
Replies
3
Views
1K
Replies
2
Views
798
Replies
0
Views
1K
Replies
23
Views
33K
Top