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)
(In reply to
a slightly different proof by Paul)
A simpler version of Paul's good n=2n-n solution
Take any number's binary representation : 0111010011101
Double it (shift left) : 1110100111010
subract the original : -0111010011101
And you get the new rep : 100(-1)1(-1)0100(-1)1(-1)
Just reorder in increasing powers and it's done. It's obviously
in strictly increasing powers and the shift and subtract will yield an
alternating sum because any string of 0[1*]0 will begin with a positive
and end with a negative.
re: a slightly different proof
