# Math Help - Sum

1. ## 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.

2. Originally Posted by usagi_killer
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