Show that every positive integer is an alternating sum of
strictly increasing powers of 2.
For example, 5=2^0 2^2 +2^3 and 8=2^3 +2^4 are alternating sums of strictly increasing powers of 2 (8=2^3 is ok too).
10=2^1 2^2 +2^4 is a strictly increasing sum but not alternating.
4=2^1 2^1 +2^2 is alternating but not strictly increasing.
(author: prof Dan Shapiro of Ohio State University)
You can easily prove that each number can be expresed as a strictly increases sum of power of 2. I suppose it here and give a couple of examples: 13, 43
13 = 5 + 8 = 1 + 4 + 8= 2^0 + 2^1 + 2^2
43 = 11+32 = 3+8+32 = 1+2+8+32 = 2^0+2^1+2^3+2^5
So, each natural number n can be expressed as:
n= a1*2^0+a2*2^1+...+ap2^p (a1,.., ap =0 or 1)
You can express n as alternating sums of strictly increasing powers of 2, doing:
n= 2n n = 2(a1*2^0+ ...+ap*2^p)  (a1*2^0+ ...+ap*2^p)=
(a1*2^1+a2*2^2+...+ao*2^p+ap*2^q) (a1*2^0+...+ap*2^p)
= a1*2^0 + (a2a1)*2^1+...+(apao)*2^p+ap*2^q
The value of the expressions (ajai): or is 0 or it's 1, 1, alternating the sign.
Ej: 55 = 1+2+4+16+32 = (2+4+8+32+64)(1+2+4+16+32)=
= 1+816+64
Edited on June 15, 2005, 9:37 pm

Posted by armando
on 20050615 14:18:44 