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 make a formal proof, but I'll give an example. Take any number,
for example, 25. Write it in binary: 25=11001. Twice 25 is then 110010.
"Subtract" 25 from 50 digit by digit: you get (1)(0)(-1)(0)(1)(-1), an
alternating sequence of 1's and -1's (if you disregard 0's) which gives
the desired answer.
|
|
Posted by e.g.
on 2005-06-14 20:18:19 |
Answer
