Results 1 to 2 of 2

Math Help - Sum

  1. #1
    Senior Member
    Joined
    Apr 2009
    Posts
    306

    Sum

    Prove that all natural numbers can be written as a sum of numbers of the form 2^a*3^b where a and b are non-negative integers and none of the summands divides another.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Apr 2009
    Posts
    677
    Quote Originally Posted by usagi_killer View Post
    Prove that all natural numbers can be written as a sum of numbers of the form 2^a*3^b where a and b are non-negative integers and none of the summands divides another.
    Trying a prove by induction. Let this be true for all numbers < n.
    case 1: n is even
    Express n as 2*[expression for (n/2)]
    This follows both the conditions above

    case 2: n is odd
    Express n as 3^b + expression for (n-3^b)
    where b is largest number such that 3^b <=n

    note (n-3^b) is even. so every summand in there will be even. so none of these will divide 3^b. what remains to prove is 3^b will divide none of these. if 3^b divides a summand it has to of the form 2.3^b.k
    consider 3^b+2.3^b.k = 3^b(1+2k) >=3^(b+1)
    thus n >=3^(b+1)
    invalidating the claim that b was the largest power of 3 such that 3^b <=n

    hope the above logic is good enough

    Thanks
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum