Question 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 nonnegative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. 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 for any integer $n \geq 3$ we have $2^{\frac{n^2}{4}} \lt f(2^n) \lt 2^{\frac{n^2}2}$.
Prove that for any integer $n \geq 3$ we have $2^{\frac{n^2}{4}} \lt f(2^n) \lt 2^{\frac{n^2}2}$.