1. Limited time only! Sign up for a free 30min personal 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!

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