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 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}$.

==============================

We always sort powers of two in non-decreasing order. 

For $0\le k\le n$, denote by $g(n,k)$ the number of ways of representing $2^n$ with the largest term $2^k$. So $$f(2^n)=g(n,0)+\dots+g(n,n).$$ Unless the representation has a single term $2^n$, two copies of $2^{n-1}$ are represented separately where the largest term $2^j$ of the first copy is no more than the smallest term of the second copy. Moreover, the problem of representing the second copy is reduced by $2^j$. This gives recurrence $$g(n,k)=\sum_{j=0}^k g(n-1,j)g(n-1-j,k-j), 0\le k<n$$ with boundary conditions $$g(n,n)=1,n\in\mathbb{Z}_{\ge0}.$$

$\boxed{2^{\frac {n^2}{4}} < f(2^n)}$

Lemma: $2^{k(n-k)}\le g(n,k)$.

Proof: it is true for $k\in\{0,n\}$. By induction, for $n>k$ we have $$g(n,k)\ge\sum_{j=0}^k 2^{j(n-1-j)}2^{(k-j)(n-1-k)}=2^{k(n-k)}2^{-k}\sum_{j=0}^k 2^{j(k-j)},$$ which is at least $$2^{k(n-k)}2^{-k}\left(2^0+2^1+\dots+2^{k-1}+2^0\right)\ge2^{k(n-k)}.$$

With this we have $$f(2^n)=g(n,0)+\dots+g(n,n)\ge 2^{0(n-0)}+2^{1(n-1)}+\dots+2^{(n-1)1}+2^{(n-0)0}.$$ If $n$ is even then one term is exactly $2^{\frac{n^2}{4}}$. Otherwise there are two identical terms with sum $$2\cdot2^{\frac{n-1}{2}\frac{n+1}{2}}=2^{\frac{n^2-1}{4}+1}>2^{\frac {n^2}{4}}.$$

$\boxed{f(2^n)<2^{\frac {n^2}{2}}}$

We will show that $$\frac{f(2^{n+1})}{f(2^{n})}\le2^n,$$ as this enables us to prove the upper bound inductively: $$f(2^{n+1})\le f(2^n)2^n<2^{\frac{n^2}{2}+n}<2^{\frac{(n+1)^2}{2}}.$$

Let $S$ be the set of decompositions of $2^{n+1}$ and $T$ be the set of decompositions of $2^{n+1}$ without $1$-term. Define a mapping $h:S\mapsto T$ as replacing every pair of $1$-terms by a $2$-term. Every element of $T$ is mapped from at most $2^n$ elements of $S$, except for the all-$2$ element, which is mapped from $2^n+1$ elements. This is because the number of $2$-terms in any element of $T$ is at most $2^{n}-1$, except that all-$2$ element for which it is $2^n$. Also any element of $T$ without $2$-terms is not mapped from $2^n$ elements of $S$. Hence $$f(2^{n+1})=|S|\le 2^n+1+\left(|T|-2\right)2^n+2^n-1\le2^n|T|=2^nf(2^n).$$