\'roblem 1 What numbers can be expressed as an alternating-sum of an increasing
ID: 3210088 • Letter: #
Question
'roblem 1 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, Note: The expression 5 =-1-2 + 8 is invalid because the signs are not alternating. (a) Is every positive integer expressible in this fashion? If so, give a convincing proof. (b) A number might have more than one expression of this type. For instance s-1-2+4 and 3=-1 +4. Given a numbern, how many different ways are there to write n in this way? Explain why your answer is correct (c) Please formulate another problem similar to this oneExplanation / Answer
P(n): we can write the numbers from 1 to 2^n as an alternating sum of an increasing sequence of powers
of 2.
Obviously, P(1) is true, because 1 = – 1 + 2 and 2 = – 2 + 4.
Now we suppose that P(k) is true, so all the numbers from 1 to 2^k can be written as an alternating sum of an increasing sequence of powers of 2.
Now we demonstrate P(k+1), so we have to demonstrate that 2^k, 2^k+1, 2^k+2, ... ,2^(k+1) can all be written this way.
2^(k+1) can obviously be written this way because it is a power of 2.
We get 2^(k+1)-1, if we take 2^(k+1) and add the way we built 1 with the signs changed (1-2), or if we take 2^k and add 2^k-1;
We get 2^(k+1)-2, if we take 2^(k+1) and add the way we built 2 with the signs changed (2-4), or if we take 2^k and add 2^k-2;
We get 2^(k+1)-3, if we take 2^(k+1) and add the way we built 3 with the signs changed (-1+2-4), or if we take 2^k and add 2^k-3;
....
We get 2^k+1, if we take 2^(k+1) and add the way we built 2^k-1 with the signs changed, or if we take 2^k and add 1;
So P(k) is true, so all integers can be written this way.
Now it should be very easy to demonstrate that there are infinite ways to write every number this way:
1=1=-1+2=-1-2+4=-1-2-4+8=......=-1-2-....
2=2=-2+4=-2-4+8=...=-2-..-2^k+2^(k+1)
3=1+2=1-2+4=1-2-3+8=..=1-2-..-2^k+2^(k...
and so on.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.