Background Research

Unlike our current number system, which uses the digits 0 through 9, the binary number system only uses two digits, 0 and 1. How can we represent any number by using just 0's and 1's? The answer is quite simple. Imagine a set of powers of two, starting from 2 raised to the zeroth power. A binary number, such as 0101, can be read as powers of two. Starting from right to left, the first digit is simply 2 raised to the zeroth power, the second digit is 2 raised the the first, the third digit is 2 squared, and the fourth digit is 2 cubed. If the digit is a 1, we add the power of two. If the digit is a 0, we ignore it. For example, 0101 is simply the sum of two raised to the zeroth power and 2 squared, or 1 plus 4, which is equal to 5.

Binary numbers can be represented as an infinite series of powers of two. Leonhard Euler developed a proof as follows:

Let P(x) = (1 + x)(1 + x²)(1 + x⁴)(1 + x⁸)..., which is an infinite product.

Multiplying out the terms of the product results in an infinite series:

(1 + x)(1 + x²)(1 + x⁴)(1 + x⁸)... = 1 + αx + βx² + γx³ + δx⁴ + ...

where the coefficients α, β, γ, δ, ... are yet to be determined. Note that,

P(x)/(1 + x) = (1 + x²)(1 + x⁴)(1 + x⁸)...

which is just P(x²). In other words,

P(x) = (1 + x)(1 + αx² + βx⁴ + γx⁶ + δx⁸ + ...)

Cross-multiplication yields another identity,

P(x) = 1 + x + αx² + αx³ + βx⁴ + βx⁵ + γx⁶ + γx⁷ + ...

Compare this with the original expansion P(x) = 1 + αx + βx² + γx³ + δx⁴ + ... As with finite polynomials, if two series are equal, their coefficients must coincide term-wise. In which we obtain, α = 1, β = α, γ = α δ = β ε = β, ... which means all the coefficients in the expansion of P(x) are equal to 1. Therefore,

(1 + x)(1 + x²)(1 + x⁴)(1 + x⁸)... = 1 + x + x² + x³ + x⁴ + x⁵ + ...

But what is the meaning of coefficients α, β, γ δ, ε, ...? Each tells us in how many ways the corresponding term (a power of x) can be obtained as the product of powers of x with exponents 1, 2, 4, 8, 16, ... Since, x^ax^b = x^{a + b} and all the coefficients were found to equal 1, this is the same as saying that every (counting) number - exponents on the right - have a unique representation as a sum of powers of 2.