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\),

\[ 2^{n^2/4}<f(2^n)<2^{n^2/2}. \]

Official text of the problem. Official problem paper (PDF)

Solution

Set \(f(0)=1\), counting the empty representation. Appending a summand \(1\) gives an injection from representations of \(t\) to representations of \(t+1\), so \(f\) is nondecreasing.

Every representation of \(2m+1\) contains an odd number of summands equal to \(1\). Removing one such summand gives a bijection with representations of \(2m\). Thus \[ f(2m+1)=f(2m). \] In a representation of \(2m\), the number of summands equal to \(1\) is \(2(m-j)\) for some \(0\leq j\leq m\). Removing those summands and dividing all remaining summands by \(2\) gives a representation of \(j\). Consequently, \[ f(2m)=\sum_{j=0}^{m}f(j). \tag{1} \] In particular, \(f(1)=1\), \(f(2)=2\), and \(f(4)=4\).

We first prove the upper bound. For \(m\geq2\), monotonicity and \(f(m)\geq2\) give \[ f(2m) =2+\sum_{j=2}^{m}f(j) \leq2+(m-1)f(m) \leq m f(m). \] Applying this successively with \(m=2^{n-1},2^{n-2},\ldots,2\), we obtain \[ f(2^n)\leq 2^{(n-1)+(n-2)+\cdots+1}f(2) =2^{\,n(n-1)/2+1}. \] For \(n\geq3\), \[ \frac{n(n-1)}2+1<\frac{n^2}2, \] which proves the required strict upper bound.

For the lower bound, put \[ g(j)=f(2j)\qquad(j\geq0). \] By (1), \[ g(j)-g(j-1)=f(j)\qquad(j\geq1). \] Since \(f\) is nondecreasing, these successive differences are nondecreasing. More explicitly, for integers \(r\geq d\geq0\), \[ \begin{aligned} g(r+d)-g(r) &=\sum_{i=1}^{d}f(r+i)\\ &\geq\sum_{i=1}^{d}f(r-d+i) =g(r)-g(r-d). \end{aligned} \] Hence \[ g(r-d)+g(r+d)\geq2g(r). \tag{2} \]

Let \(n\geq3\) and \(m=2^{n-2}\), so \(m\) is even. Using (1) and \(f(2j+1)=f(2j)\), we find \[ \begin{aligned} f(2^n)=f(4m) &=\sum_{j=0}^{2m}f(j)\\ &=2\sum_{j=0}^{m-1}g(j)+g(m)\\ &=1+\sum_{j=0}^{m-1}\bigl(g(j)+g(m-j)\bigr), \end{aligned} \] where the last equality uses \(g(0)=1\). Applying (2) to each pair, whose indices have midpoint \(m/2\), gives \[ \begin{aligned} f(2^n) &\geq1+2m\,g(m/2)\\ &=1+2m\,f(m)\\ &>2^{n-1}f(2^{n-2}). \end{aligned}\tag{3} \]

We now prove \(f(2^n)>2^{n^2/4}\) by induction, using steps of two. The starting cases are \[ f(2)=2>2^{1/4}, \qquad f(4)=4>2^{4/4}. \] For \(n\geq3\), (3) and the induction hypothesis yield \[ f(2^n) >2^{n-1}f(2^{n-2}) >2^{\,n-1+(n-2)^2/4} =2^{n^2/4}. \] Together with the upper bound, this proves both inequalities for every integer \(n\geq3\).

The solution was checked against Evan Chen's published IMO solution notes.