(math) Alternating Binary Expansions are Unique

13 Aug, 2025

It is an undeniable truth of the universe that every natural number $n$ can be expressed uniquely as a sum of decreasing powers of 2. This decomposition is known as the binary expansion of $n$ . For instance, the number 45 can be written as $2^{5} + 2^{3} + 2^{2} + 2^{0}$ which is $32 + 8 + 4 + 1$ . We can write this snugly using binary notation as $45 = (101101)_{2}$ .

A natural number can can also be decomposed using an alternate binary expansion, which is an alternating sum of decreasing powers of 2. The word alternating here means that you add the first term, subtract the second, then add the third, then subtract the fourth and so on. The number 45 has the alternating binary expansion $2^{6} - 2^{5} + 2^{4} - 2^{2} + 2^{1} - 2^{0}$ which in numbers is $64 - 32 + 16 - 4 + 2 - 1$ . In alternating binary notation, we write $45 = [11^{'} 101^{'} 11^{'}]_{2}$ My emphasis on the in the previous sentence should convey that even this alternate binary expansion is unique. Let's see why. Take this time to think about the above example and if you can figure out what I did to come up with the expansion. We also pose the constraint that an alternating sum must contain at least two terms otherwise something like $2^{k} = 2^{k + 1} - 2^{k}$ messes up with uniqueness.

The following is due to my friend, C. Consider a section of repeating 1s in the binary expansion which begins with a 0 to the left. Note that the first chunk of 1s begins with an implicit 0. We replace each chunk of $01 \dots 1$ (containing $n$ 1s) by $10 \dots 01^{'}$ (containing $n - 1$ 0s). This is the same as replacing $2^{k} + 2^{k - 1} + \dots + 2^{l}$ by $2^{k + 1} - 2^{l}$ . To show that this indeed works, we add $2^{l}$ to the long expression, and the rightmost entry becomes $2^{l + 1}$ which then adds to the adjacent $2^{l + 1}$ to give $2^{l + 2}$ and so on. Much like the game 2048, all the terms collapse into each other leaving us with $2^{k + 1}$ . So, in the following example

(110011110110001)_{2} maps to [101^{'} 010001^{'} 101^{'} 0011^{'}]_{2}

Let us now show that the alternating binary expansions are unique using induction on the natural number $n$ for which we are finding the expansion. The base case of $n = 1$ is trivial as $1 = 2 - 1$ , and we assume uniqueness for all $k < n$ . What can the leading power of 2 in the expansion of $n$ be? If we begin with $2^{k}$ , then by the alternating condition it is not possible for us to bring the sum down below $2^{k - 1}$ . This constraint means that $2^{k}$ must be the binary power closest to $n$ and bigger than $n$ . Once we have that sorted, let $m = 2^{k} - n$ . As $n$ is bigger than $2^{k - 1}$ , we have $m < 2^{k - 1} < n$ . By the induction hypothesis, the alternating binary expansion of $m$ is unique! Let $m = 2^{r_{0}} - 2^{r_{1}} + \dots + (- 1)^{k} 2^{r_{k}}$ , which means that $n = 2^{k} - m$ has a unique alternating binary expansion given by $n = 2^{k} - 2^{r_{0}} + 2^{r_{1}} - \dots + (- 1)^{k + 1} 2^{r_{k}}$ .

And that shows our result! I don't think this statement is true for other bases. For instance in ternary, we have $5 = [21^{'}]_{3} = [12^{'} 2]_{3}$ as $2 \times 3 - 1 = 1 \times 9 - 2 \times 3 + 2$ . Maybe there is an analog of alternating that is true in these bases, but that remains to be seen!