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 + (a2-a1)*2^1+...+(ap-ao)*2^p+ap*2^q

The value of the expressions (aj-ai): 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+8-16+64

Edited on June 15, 2005, 9:37 pm

Posted by armando on 2005-06-15 14:18:44