I’ll begin by providing an answer to the first of the three questions I posed in a previous post.
To recap, the question in question went as follows:
Given a positive integer n, in how many ways can n be written as a sum of powers of two, when each power is allowed to occur at most once?
Before I give the solution, let me ask a slightly different question instead: given a positive integer n, in how many ways can n be written as a sum of powers of ten, when each power is allowed to occur at most nine times?
Well, let’s see… we’ll try an example. Let’s try writing 436 as a sum of powers of ten, with at most nine copies of each power. Well, notice that since all powers of ten from and up are divisible by ten, the only way to get the ’6′ at the end of 436 is to use six copies of , leaving us with 430. Now, about that 30… we can only use or , since any higher powers of ten will be divisible by 100. But we can’t use since we don’t have enough of them to add up to 30. So we’ll have to use three copies of . Finally, we have to use four copies of . So, all told, it seems as though there’s only one way to write 436:
…waaaait a minute…! That’s exactly what the notation ’436′ means — four hundreds, three tens, and six ones! And the answer to the question is, of course, that there is exactly one way to write any number n as a sum of powers of ten when at most nine copies of each power are allowed — and this is why our base-ten system of writing numbers works! We take it completely for granted, but it’s actually fairly remarkable that such a simple system for uniquely representing integers exists. And as natural as it seems to us, it isn’t obvious — it was invented by Indian mathematicians as early as 500 AD, but didn’t really catch on in Europe until about a thousand years later!
So, going back to the original question, it turns out that there is exactly one way to write any given positive integer as a sum of powers of two, with each power occurring at most once; this system of uniquely representing positive integers is called base two, or binary. As you may know, this is the system that computers use to represent data. Every single piece of data stored by a computer — videos, images, software, text, this blog post itself — is ultimately encoded as a series of numbers, which are in turn encoded in binary.
How can we prove this? Let denote the number of ways to write the positive integer n as a sum of powers of two with each power occurring at most once. Clearly (there’s only one way to write ). Now suppose we have some positive integer n which is even, so we can write for some integer k. Any way of expressing n as a sum of powers of two cannot include , since any sum that includes exactly once must be odd (all the other powers of two are even, and even + even = even, even + odd = odd). (Of course, a sum which includes twice could be even — but we are only allowed one copy of each power.) Therefore, given powers of two summing to n, we can just divide each of them by two (so e.g. becomes , and so on) to get a list of powers of two which add up to . Conversely, any powers of two summing to k can all be multiplied by two to give powers of two summing to n. Since each way of writing n corresponds to a way of writing k and vice versa, the number of ways of writing them must be the same: .
Now suppose is odd. Any list of powers of two summing to an odd number must include . If we remove the , we are left with ways of summing to . And vice versa, any way of summing to can be made into a way of summing to by just adding . So .
But since , and is always equal to the value of b for some smaller number, it is not hard to see that for all n. For example, .
All in all, this is a rather roundabout way to show that there is only one way to write each number as a sum of powers of two with at most one copy of each power! There are probably easier ways to demonstrate this. However, a generalization to the above approach can be used profitably to attack the other two problems, so you can additionally consider this post as a hint. =)