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

[snaidu228]

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.

 

[schlunk]

14= 3+3+8
it's and/or

 

[Mark44]

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.

 

[D H]

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.

 

[D H]

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?