Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Mar 11, 2010 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    Induction Hypothesis

    3. 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.
     
  2. jcsd
  3. Mar 11, 2010 #2
    14= 3+3+8
    it's and/or
     
  4. Mar 11, 2010 #3

    Mark44

    Staff: Mentor

    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.
     
  5. Mar 11, 2010 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  6. Mar 11, 2010 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook