2015 IMC 1.2. For a positive integer , let be the number obtained by writing in binary and replacing every with and vice versa. For example, is in binary, so is in binary, therefore . Prove that
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:
- In base 2, consists of all 1s.
- Looking at each “power of 2” group from to , the value of decreases by 1 from to .
- Equality holds at 2, 4 and 10. The fact that 8 is not on the list means that equality doesn’t necessarily hold when 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 . Then .
Now that we have a relatively closed-form formula for , 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 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 :
Claim 2: .
We can then use Claim 2 repeated to calculate the given summation for of the form . When ,
Getting to the general case is just a matter of adding the incomplete “power of 2” group:
Claim 3: Let with . Then
To complete the proof, it remains to show that
for all possible and . After multiplying by 12 and canceling terms, the above is equivalent to proving that
The and terms should make one think about completing the square. In fact, it turns out that the above is equivalent to
Can ever be zero? Well, it can’t because is never a multiple of 3 while always is. Hence, can only take on positive square values, and so the inequality above is obvious.
When does equality hold? It holds when