<s>[INST] IMO 1997 problem 6 For each positive integer $n$ , let $f (n)$ denote the number of ways of representing $n$ as a sum of powers of $2$ with non-negative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. Prove that, for any integer $n \geqslant 3$, $$2^{n^2/4} < f (2^n) < 2^{n^2/2}.$$
 [/INST] Observe that $k f (2k) < f (4k) \leqslant 2k f (2k)$ for $k \geqslant 4$ a power of $2$. We use induction on $n$ to prove the inequality. If $n = 3$, then it is obvious that $$2^{3^2/4} < f(8) = 10 < 2^{3^2/2}.$$ Suppose the inequality holds for $n = m$, we now prove it for $n = m + 1$. Since $f (2^m) < 2^{m^2/2}$ and using $f (4k) \leqslant 2k f( 2k)$ with $k = 2^{m - 1}$, we have $$f (2^{m + 1}) \leqslant 2^m f (2^m) < 2^m 2^{m^2/2} = 2^{(m^2 + 2m)/2} < 2^ {(m + 1)^2/2},$$ as desired. Now, by $f (2^m) > 2^{m^2/4}$ and $f (4k) > k f (2^k)$ with $k = 2^{m - 1}$, we have $$f (2^{m + 1}) > 2^{m - 1} f (2^m) > 2^{m - 1} 2^{m^2/4} = 2 ^ {(m^2 + 4m - 4)/4} > 2^{(m + 1)^2/4}$$ for $m > 2$. Proof is complete. $\Box$
</s>