Q2 Matemática  (IMC 2015)

Para um inteiro positivo $n$, seja $f(n)$ o número obtido escrevendo $n$ em binário e substituindo cada 0 por 1 e vice-versa. Por exemplo, $n=23$ é 10111 em binário, então $f(n)$ é 1000 em binário, portanto $f(23)=8$. Prove que $$\sum _{k=1}^{n}f(k)\le \frac{n^2}{4}.$$ Quando a igualdade é válida? (Proposto por Stephan Wagner, Universidade de Stellenbosch)