Solution at http://www.kalva.demon.co.uk/imo/isoln/isoln976.html The key is to derive a recurrence relation for f(n) [not for f(2n)]. If n is odd, then the sum must have a 1. In fact, there is a one-to-one correspondence between sums for n and sums for n-1. So: f(2n+1) = f(2n) Now consider n even. The same argument shows that there is a one-to-one correspondence between sums for n-1 and sums for n which have a 1. Sums which do not have a 1 are in one-to-one correspondence with sums for n/2 (just halve each term). So: f(2n) = f(2n - 1) + f(n) = f(2n - 2) + f(n). The upper limit is now almost immediate. First, the recurrence relations show that f is monotonic increasing. Now apply the second relation repeatedly to f(2n+1) to get: f(2n+1) = f(2n+1 - 2n) + f(2n - 2n-1 + 1) + ... + f(2n - 1) + f(2n) = f(2n) + f(2n - 1 ) + ... + f(2n-1 + 1) + f(2n) (*) and hence f(2n+1) ≥ (2n-1 + 1)f(2n) We can now establish the upper limit by induction. It is false for n = 1 and 2, but almost true for n = 2, in that: f(22) = 222/2. Now if f(2n) ≤ 2n2/2, then the inequality just established shows that f(2n+1) < 2n2n2/2 < 2(n2+2n+1)/2 = 2(n+1)2/2, so it is true for n + 1. Hence it is true for all n > 2. Applying the same idea to the lower limit does not work. We need something stronger. We may continue (*) inductively to obtain f(2n+1) = f(2n) + f(2n - 1) + ... + f(3) + f(2) + f(1) + 1. (**) We now use the following lemma: f(1) + f(2) + ... + f(2r) ≥ 2r f(r) We group the terms on the lhs into pairs and claim that f(1) + f(2r) ≥ f(2) + f(2r-1) ≥ f(3) + f(2r-2) ≥ ... ≥ f(r) + f(r+1). If k is even, then f(k) = f(k+1) and f(2r-k) = f(2r+1-k), so f(k) + f(2r+1-k) = f(k+1) + f(2r-k). If k is odd, then f(k+1) = f(k) + f((k+1)/2) and f(2r+1-k) = f(2r-k) + f((2r-k+1)/2), but f is monotone so f((k+1)/2) ≤ f((2r+1-k)/2) and hence f(k) + f(2r+1-k) ≥ f(k+1) + f(2r-k), as required. Applying the lemma to (**) gives f(2n+1) > 2n+1f(2n-1). This is sufficient to prove the lower limit by induction. It is true for n = 1. Suppose it is true for n. Then f(2n+1) > 2n+12(n-1)2/4 = 2(n2-2n+1+4n+4)/4 > 2(n+1)2/4, so it is true for n+1.

The link in chien than's answer no longer works. Also, his proof can be a bit hard to read because copying exponents went wrong apparently. Here is my version. We will first look at the function $f(m)$, where $m$ can be any non-negative integer and is not required to be a power of two itself. Define $f_k(m)$ as the number of ways of representing $m$ as a sum of powers of two where we use $1$ in the sum exactly $k$ times. With the definition of $f_k(m)$, we clearly get $f(m) = \displaystyle \sum_{k=0}^m f_k(m)$. We also have $f_k(m) = f_0(m-k)$ and, if $m$ is odd, $f_0(m) = 0$, while if $m$ is even, $f_0(m) = f\left(\frac{m}{2}\right)$. The latter equality can be seen by noticing that one can put the expressions for $m$ that do not contain a $1$ in a one-to-one correspondence with all expressions for $\frac{m}{2}$, by simply dividing every term by two. Applying these properties one can obtain the following way to recursively calculate $f(m)$: \begin{align} f(m) &= \sum_{k=0}^m f_k(m) \nonumber \\ &= \sum_{k=0}^m f_0(m-k) \nonumber \\ &= \sum_{k=0}^m f_0(k) \nonumber \\ &= \sum_{k=0}^{\left \lfloor \frac{m}{2} \right \rfloor} f_0(2k) \nonumber \\ &= \sum_{k=0}^{\left \lfloor \frac{m}{2} \right \rfloor} f(k) \end{align} We will now start our proof of the upper bound. With equality (1) it is straightforward to check $f(8) = f(0) + f(1) + f(2) + f(3) + f(4) = 1 + 1 + 2 + 2 + 4 = 10$, so that the inequality $f(2^n) < 2^{n^2/2}$ is seen to hold for $n = 3$. Let us therefore assume $n \ge 4$ and by induction we may assume $f(2^{n-1}) < 2^{(n-1)^2/2}$. Furthermore note that $f$ is a monotonically increasing function. \begin{align*} f(2^n) &= \sum_{k=0}^{2^{n-1}} f(k) \\ &= 1 + 1 + \sum_{k=2}^{2^{n-1}} f(k) \\ &< f(2^{n-1}) + \sum_{k=2}^{2^{n-1}} f(2^{n-1}) \\ &= 2^{n-1} f(2^{n-1}) \\ &< 2^{n-1} 2^{(n-1)^2/2} \\ &= 2^{n^2/2 - n + 1/2 + n - 1} \\ &= 2^{n^2/2 - 1/2} \\ &< 2^{n^2/2} \end{align*} For the lower bound, we first need to show a little lemma. Lemma. For all $n \ge 2$ and all $i$ with $1 \le i \le 2^{n-2}$ we have the following inequality: $$ f(i) + f(2^{n-1} - i + 1) \ge 2f(2^{n-2}) $$ Proof. We will actually prove $f(i) + f(2^{n-1} - i + 1) \ge f(i + 1) + f(2^{n-1} - i)$, which implies $f(i) + f(2^{n-1} - i + 1) \ge f(2^{n-2}) + f(2^{n-2} + 1) = 2f(2^{n-2})$ by iteration. To show $f(i) + f(2^{n-1} - i + 1) \ge f(i + 1) + f(2^{n-1} - i)$, note that when $i$ is even we have $f(i) = f(i+1)$ and $f(2^{n-1} - i + 1) = f(2^{n-1} - i)$, so that we actually have equality. When $i$ is odd, we have $f(i+1) - f(i) = f\left(\frac{i+1}{2}\right)$ and $f(2^{n-1} - i + 1) - f(2^{n-1} - i) = f\left(\frac{2^{n-1} - i + 1}{2}\right)$, both by equation (1), so that: \begin{align*} f(i) + f(2^{n-1} - i + 1) &= f(i+1) - f\left(\frac{i+1}{2}\right) + f(2^{n-1} - i) + f\left(\frac{2^{n-1} - i + 1}{2}\right) \\ &= f(i+1) + f(2^{n-1} - i) + \left(f\left(\frac{2^{n-1} - i + 1}{2}\right) - f\left(\frac{i+1}{2}\right)\right) \\ &\ge f(i+1) + f(2^{n-1} - i) \end{align*} Where the final inequality follows from that fact that $f$ is monotonically increasing and $\frac{2^{n-1} - i + 1}{2} \ge \frac{i+1}{2}$ since $i \le 2^{n-2}$. This finishes the proof of the lemma. Now we can finally prove the lower bound. Since $f(2) = 2$, the inequality $2^{n^2/4} < f(2^n)$ is seen to hold for $n = 1$, so assume $n \ge 2$. By applying equation (1) and the above lemma we get: \begin{align*} f(2^n) &= \sum_{k=0}^{2^{n-1}} f(k) \\ &> \sum_{i=1}^{2^{n-2}} \left(f(i) + f(2^{n-1} - i + 1) \right) \\ &\ge 2^{n-1} f(2^{n-2}) \\ &> 2^{n-1} 2^{(n-2)^2/4} \\ &= 2^{n^2/4 - n + 1 + n - 1} \\ &= 2^{n^2/4} \end{align*}