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: The answer is $2047$.

For convenience, we agree that $f(0) = 1$.
Then by considering cases on the first number in the representation,
we derive the recurrence
\[ f(n) = \sum_{k=0}^{\left\lfloor \log_2 n \right\rfloor} f(n-2^k).
  \qquad (\heartsuit) \]

We wish to understand the parity of $f$. The first few values are
\begin{align*}
  f(0) &= 1 \\
  f(1) &= 1 \\
  f(2) &= 2 \\
  f(3) &= 3 \\
  f(4) &= 6 \\
  f(5) &= 10 \\
  f(6) &= 18 \\
  f(7) &= 31.
\end{align*}

Inspired by the data we make the key claim that
\begin{claim*}
  $f(n)$ is odd if and only if $n+1$ is a power of $2$.
\end{claim*}
\begin{proof}
  We call a number \emph{repetitive} if it is zero or its binary representation
  consists entirely of $1$'s.
  So we want to prove that $f(n)$ is odd if and only if $n$ is repetitive.

  This only takes a few cases:
  \begin{itemize}
  \ii If $n = 2^k$, then $(\heartsuit)$
  has exactly two repetitive terms on the right-hand side, namely $0$ and $2^k-1$.

  \ii If $n = 2^k + 2^\ell - 1$, then $(\heartsuit)$
  has exactly two repetitive terms on the right-hand side,
  namely $2^{\ell+1}-1$ and $2^{\ell}-1$.

  \ii If $n = 2^k-1$, then $(\heartsuit)$
  has exactly one repetitive terms on the right-hand side, namely $2^{k-1}-1$.

  \ii For other $n$,
  there are no repetitive terms at all on the right-hand side of $(\heartsuit)$.
  \end{itemize}
  Thus the induction checks out.
\end{proof}

So the final answer to the problem is $2047$.