The Infinite Product That Knows Binary

May 11, 2026 · by · in Uncategorized · Leave a comment

A standard way to prove that every nonnegative integer has a unique binary representation is to use the division algorithm. Repeatedly divide the number by 2, record the remainders, and continue until the quotient becomes zero. The remainders, read backwards, give the binary expansion. Uniqueness follows because at each step the quotient and remainder are uniquely determined. For example, take 13 and perform repeated division by 2:

13 = 2\cdot 6 + 1,

6 = 2\cdot 3 + 0,

3 = 2\cdot 1 + 1,

1 = 2\cdot 0 + 1.

Reading the remainders backwards gives 1101 which is indeed 2^3+2^2+2^0=8+4+1=13.

But there is a generatingfunctionology proof that feels almost magical: write down a generating function and let algebra do the bookkeeping. An interested reader can learn more about generating functions in Wilf’s book generatingfunctionology. It is helpful to reexpress the problem in terms of a weighing problem. If you are given all possible weights that are powers of two, namely 1,2,4,8,\ldots,2^k,\ldots and an arbitrary weight k, in how many ways can you weigh k? We consider the following infinite product

p(x) =(1+x)(1+x^2)(1+x^4)(1+x^8)\ldots = 1+a_1x+a_2x^2+\ldots+a_k x^k+\ldots. The power of generating functions lies first in observing that the coefficient a_k of the power x^k is exactly the number of different ways of representing k as a sum of different numbers from the set 2^0,2^1,2^2,2^3,\ldots. We already know the answer, namely a_k=1, which means that the answer should be p(x)=1+x+x^2+\ldots=\frac{1}{1-x}.

Let us verify this directly from the product. Consider the finite truncation

p_m(x)=(1+x)(1+x^2)(1+x^4)\cdots(1+x^{2^m}).

The useful identity is

(1-x)(1+x)=1-x^2.

Therefore,

(1-x)(1+x)(1+x^2)= (1-x^2)(1+x^2)=1-x^4.

Continuing in the same way, everything telescopes:

(1-x)(1+x)(1+x^2)(1+x^4)\cdots(1+x^{2^m})=1-x^{2^{m+1}}.

Hence

p_m(x)=\frac{1-x^{2^{m+1}}}{1-x}.

But the right-hand side is just

p_m(x)=1+x+x^2+\cdots+x^{2^{m+1}-1}.

So the finite product already tells us something striking: using the powers

1,2,4,\ldots,2^m

every integer from 0 up to 2^{m+1}-1 is represented exactly once as a sum of distinct powers of two.

Now let m grow. For any fixed exponent k, once 2^{m+1}>k, the coefficient of x^k has already stabilized. Thus in the infinite limit,

p(x)=(1+x)(1+x^2)(1+x^4)\cdots=\frac{1}{1-x}=1+x+x^2+x^3+\cdots.

Therefore every coefficient is equal to 1. In other words, every nonnegative integer has exactly one representation as a sum of distinct powers of two. This is precisely the uniqueness of binary representation in generatingfunctionology terms.

Tags:

Leave a comment