For each positive integer
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
, let
![f(n)](/media/m/d/3/e/d3e47283bffbbf24c97f0c6474d5a82d.png)
denote the number of ways of representing
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
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](/media/m/1/d/d/1ddf2f667cf760000f093db09bd7b25b.png)
, 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](/media/m/5/4/8/54807b3bf99aa939833fe57bf8d891d3.png)
we have
![2^{\frac {n^2}{4}} < f(2^n) < 2^{\frac {n^2}2}](/media/m/6/7/8/678a337d845e47e29bb37535ba17d2e4.png)
.
%V0
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}} < f(2^n) < 2^{\frac {n^2}2}$.