And now for the solution to problem #3 from Challenge #12, which asked: how many ways are there to write a positive integer n as a sum of powers of two, with no restrictions on how many powers of two may be used?
The main idea is to break our analysis down into two cases based on whether n is even or odd, like we did in our analysis of the solution to problem #1. If is odd, then any way of writing n must have at least one copy of (since otherwise the sum would be even). If we just remove one copy of , we get a way to write ; conversely, any way to write can be made into a way to write by adding . Therefore, letting denote the number of ways to write n as a sum of powers of two, we have .
On the other hand, suppose is even. For any particular way to write n, we consider two cases: either it includes at least one , in which case we can remove it to give a way to write ; or it doesn’t contain , in which case we can divide everything else by 2 to yield a way to write . So, we have .
Oh, and of course, for a base case, . Let’s calculate a few values of (omitting odd values since they are simply equal to the previous value (boring!)):
Notice how the first two differences ( and ) are equal to 2; the next two differences are 4; then 6, then 10… and yes, then 14, and so on. Interesting! This self-similar structure is a direct result of the recurrence . You can see more of the sequence on the Online Encyclopedia of Integer Sequences (one of my favorite web sites!).