## Challenge #12 solution, part III

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 $n = 2k + 1$ is odd, then any way of writing n must have at least one copy of $2^0$ (since otherwise the sum would be even). If we just remove one copy of $2^0$, we get a way to write $n - 1 = 2k$; conversely, any way to write $2k$ can be made into a way to write $2k + 1$ by adding $2^0$. Therefore, letting $p(n)$ denote the number of ways to write n as a sum of powers of two, we have $p(2k + 1) = p(2k)$.

On the other hand, suppose $n = 2k$ is even. For any particular way to write n, we consider two cases: either it includes at least one $2^0$, in which case we can remove it to give a way to write $n - 1$; or it doesn’t contain $2^0$, in which case we can divide everything else by 2 to yield a way to write $n/2 = k$. So, we have $p(2k) = p(2k - 1) + p(k)$.

Oh, and of course, for a base case, $p(1) = 1$. Let’s calculate a few values of $p(2k)$ (omitting odd values since they are simply equal to the previous value (boring!)): $\{p(2k)\}_{k=1,2,\dots} = \{ 2, 4, 6, 10, 14, 20, 26, 36, 46, \dots \}$

Notice how the first two differences ( $4 - 2$ and $6 - 4$) 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 $p(2k) = p(2k-1) + p(k)$. You can see more of the sequence on the Online Encyclopedia of Integer Sequences (one of my favorite web sites!). 