**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

**Done!**

### Like this:

Like Loading...

*Related*