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.

Results 1 to 2 of 2

- October 4th 2009, 01:31 AM #1

- Joined
- Apr 2009
- Posts
- 308

- October 4th 2009, 02:22 AM #2

- Joined
- Apr 2009
- Posts
- 678
- Thanks
- 1

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