IMC 2015 · Problem 2

For a positive integer $n$, let $f(n)$ be the number obtained by writing $n$ in binary and replacing every $0$ with $1$ and vice versa. For example, $n = 23$ is $10111$ in binary, so $f(n)$ is $1000$ in binary, therefore $f(23) = 8$. Prove that

$$\sum_{k=1}^{n} f(k) \le \frac{n^2}{4}.$$

When does equality hold?