What numbers can be expressed as an alternating-sum of an increasing sequence of
powers of 2 ?
To form such a sum, choose a subset of the sequence 1, 2, 4, 8, 16, 32, 64, . . . (these are
the powers of 2). List the numbers in that subset in increasing order (no repetitions
allowed), and combine them with alternating plus and minus signs. For example,
1 = – 1 + 2; 2 = – 2 + 4; 3 = 1 – 2 + 4;
4 = – 4 + 8; 5 = 1 – 4 + 8; 6 = – 2 + 8; etc.
(a) Is every positive integer expressible in this fashion? If so, give a convincing proof.
(b) There can be more than one expression of this type for a given number. For
instance 5 = 1 – 4 + 8 and 5 = –1 + 2 – 4 + 8. Given a number n, how many different
ways are there to write n in this way? Explain why your answer is correct.
(9) Which of the problems here did you enjoy the most? Why?
We hope
2 answers