Question 24
(LIT) IMO6. For a positive integer $n$, let $f(n)$ denote the number of ways to represent $n$ as the sum of powers of $2$ with nonnegative integer exponents. Representations that differ only in the ordering in their summands are not considered to be distinct. (For instance, $f(4)=4$ because the number $4$ can be represented in the following four ways: $4;\ 2+2;\ 2+1+1;\ 1+1+1+1$.) Prove that the inequality
$$2^{n^2/4}\lt f(2^n)\lt 2^{n^2/2}$$
holds for any integer $n\ge3$.
$$2^{n^2/4}\lt f(2^n)\lt 2^{n^2/2}$$
holds for any integer $n\ge3$.