Unique Binary Representation of Integers Explained

This article explores the fundamental mathematical properties that guarantee every integer can be uniquely represented as a sum of distinct powers of two. At the core of this binary system is the Radix Representation Theorem, supported by Euclidean division and the distinct bounding behavior of geometric series. Understanding these principles clarifies why binary notation works reliably across computer science and discrete mathematics.

The Radix Representation Theorem

The primary mathematical framework ensuring this behavior is the Radix Representation Theorem (or Base Representation Theorem). This theorem states that given any integer base \(b > 1\), every positive integer \(N\) can be expressed uniquely in the form:

\[N = \sum_{i=0}^{k} d_i b^i\]

where each digit \(d_i\) satisfies \(0 \le d_i < b\), and the leading coefficient \(d_k\) is non-zero.

In the binary numeral system, the base is \(b = 2\). Consequently, the only allowed coefficients (digits) are \(0\) and \(1\). Because each coefficient is either present (\(1\)) or absent (\(0\)), the expression directly simplifies to a sum of distinct powers of two.

Proof of Existence via Euclidean Division

The existence of such a partition for any integer relies on repeated application of Euclidean Division (the Division Algorithm).

1. Given an integer \(N\), dividing by 2 yields a unique quotient \(q_0\) and a remainder \(r_0 \in \{0, 1\}\) such that \(N = 2q_0 + r_0\).
2. Repeating this process on successive quotients produces a sequence of remainders: \(q_0 = 2q_1 + r_1\), \(q_1 = 2q_2 + r_2\), and so on.
3. Because the quotients strictly decrease (\(N > q_0 > q_1 > \dots \ge 0\)), the process terminates when the quotient reaches zero.

Reconstructing the substitutions demonstrates that \(N = r_k 2^k + \dots + r_1 2^1 + r_0 2^0\), proving that at least one valid representation always exists.

Proof of Uniqueness via Geometric Series Inequality

The uniqueness of this partition is guaranteed by a critical property of geometric progressions: the sum of any set of distinct powers of two up to \(2^{k-1}\) is always strictly less than the next power of two, \(2^k\).

\[\sum_{i=0}^{k-1} 2^i = 2^k - 1 < 2^k\]

Because the largest single power of two in any subset exceeds the sum of all smaller powers combined, no power of two can be substituted by or equated to any combination of smaller distinct powers.

If an integer \(N\) had two different representations, subtracting the identical terms from both sides would leave an equality where the largest remaining power of two must equal a sum of strictly smaller powers of two. The geometric inequality proves this scenario is impossible, thereby ensuring that the binary partition for any given integer is strictly unique.