## [Soln] 2015 IMC Day 1 Problem 2

2015 IMC 1.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

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

When does equality hold?

(The solution to this problem involves a fair bit of straightforward but messy algebra, so I will skip some of the manipulations in an effort to make the key points clear.)

Let’s list out some small values:

Immediately a couple of things jump out at us:

1. In base 2, $n + f(n)$ consists of all 1s.
2. Looking at each “power of 2” group from $2^k$ to $2^{k+1} - 1$, the value of $f(n)$ decreases by 1 from $2^k - 1$ to $0$.
3. Equality holds at 2, 4 and 10. The fact that 8 is not on the list means that equality doesn’t necessarily hold when $n$ is a power of 2, and the fact that 10 is on the list means that it is not as simple as equality holding for some small values.

Observations 1 and 2 can be formalised in the following claim:

Claim 1: Let $2^a \leq n < 2^{a+1}$. Then $n + f(n) = 2^{a+1} - 1$.

Now that we have a relatively closed-form formula for $f(n)$, we can try to substitute it directly into the summation and simplify it. However, from observation 2, a slightly better way would be to start with $n$ such that the summation consists of complete “power of 2” groups.

The following claim gives the closed-form formula for a “power of 2” group (and is easily proved by summing up Claim 1 for various values of $n$:

Claim 2: $\displaystyle\sum_{k = 2^a}^{2^{a+1} - 1} f(k) = 2^{a-1}(2^a - 1)$.

We can then use Claim 2 repeated to calculate the given summation for $n$ of the form $2^a - 1$. When $n = 2^a - 1$,

\begin{aligned} \sum_{k = 1}^n f(k) &= \sum_{i = 0}^{a-1} \sum_{k=2^i}^{2^{i+1} - 1} f(k) \\ &= \sum_{i = 0}^{a-1} 2^{i-1}(2^i - 1) \\ &= ... \\ &= \frac{2}{3}(2^a + 1)(2^{a-2} - 1) + 1. \end{aligned}

Getting to the general case is just a matter of adding the incomplete “power of 2” group:

Claim 3: Let $n = 2^a + r$ with $0 \leq r < 2^a$. Then

$\displaystyle\sum_{k=1}^n f(k) = \frac{2}{3}(2^a + 1)(2^{a-2} - 1) + 1 + (r+1)(2^a-1) - \frac{r(r+1)}{2}.$

To complete the proof, it remains to show that

$\displaystyle\frac{2}{3}(2^a + 1)(2^{a-2} - 1) + 1 + (r+1)(2^a-1) - \frac{r(r+1)}{2} \leq \frac{(2^a + r)^2}{4}$

for all possible $a$ and $0 \geq r < 2^a$. After multiplying by 12 and canceling terms, the above is equivalent to proving that

$2^{2a} - 3\cdot 2^{a+1}r - 3 \cdot 2^{a+1} + 9r^2 + 18r + 8 \geq 0.$

The $2^{2a}$ and $9r^2$ terms should make one think about completing the square. In fact, it turns out that the above is equivalent to

\begin{aligned} [2^a - 3(r+1)]^2 - 1 &\geq 0, \\ [2^a - 3(r+1)]^2 &\geq 1. \end{aligned}

Can $2^a - 3(r+1)$ ever be zero? Well, it can’t because $2^a$ is never a multiple of 3 while $3(r+1)$ always is. Hence, $[2^a - 3(r+1)]^2$ can only take on positive square values, and so the inequality above is obvious.

When does equality hold? It holds when

\begin{aligned} [2^a - 3(r+1)]^2 &= 1, \text{ or} \\ 2^a &= 3(r+1) \pm 1. \end{aligned}

Done!