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?
In the comments to Challenge #12, Jonathan posted some good thoughts, and Anand posted a thorough analysis, so if you want more details you can go read those.
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!).
[...] to analyze this? We can use a similar approach to that outlined in the solution to part III (which asked a similar question, but allowing any number of copies of each power of two). First [...]