2013 USAJMO Problems/Problem 4

Problem

Let $f(n)$ be the number of ways to write $n$ as a sum of powers of $2$ , where we keep track of the order of the summation. For example, $f(4)=6$ because $4$ can be written as $4$ , $2+2$ , $2+1+1$ , $1+2+1$ , $1+1+2$ , and $1+1+1+1$ . Find the smallest $n$ greater than $2013$ for which $f(n)$ is odd.

Solution

First of all, note that $f(n)$ = $\sum_{i=0}^{k} f(n-2^{i})$ where $k$ is the largest integer such that $2^k \le n$ . We let $f(0) = 1$ for convenience.

From here, we proceed by induction, with our claim being that the only $n$ such that $f(n)$ is odd are $n$ representable of the form $2^{a} - 1, a \in \mathbb{Z}$

We induct on $a$ . It is trivially true for $a = 0$ and $a = 1$ . From here, we show that, if the only numbers $n \le 2^{a-1} - 1$ where $f(n)$ is odd are of the form described above, then the only numbers $n \le 2^{a} -1$ that are odd are of that form. We first consider all numbers $b$ , such that $2^{a-1} \le b \le 2^{a} - 2$ , going from the lower bound to the upper bound (a mini induction, you might say). We know that $f(b) = \sum_{i=0}^{a-1} f(b-2^{i})$ . For a number in this summation to be odd, $b - 2^i = 2^m -1 \rightarrow b = 2^i + 2^m - 1$ . However, we know that $b > 2^{a-1}$ , so $m$ must be equal to $a-1$ , or else $b$ cannot be in that interval. Now, from this, we know that $i < a-1$ , as $n<2^{a} - 1$ . Therefore, $i$ and $m$ are distinct, and thus $f(b - 2^i)$ and $f(b- 2^{a-1})$ are odd; since there are just two odd numbers, the ending sum for any $b$ is even. Finally, considering $2^{a} - 1$ , the only odd number is $f(2^{a} - 1 - 2^{a-1})$ , so the ending sum is odd. $\Box$