Further clarification needed on proof invovling generating functions and partitions (or alternative proof)

Question

Show with generating functions that every positive integer can be written as a unique sum of distinct powers of $2$.

There are 2 parts to the proof that I don't understand. I will point them out as I outline the proof:

The generating function given is $$ g^*(x) = (1+x)(1+x^2)(1+x^4)\cdots (1+x^{2^k}) \cdots. $$

Then I don't understand where the following comes from:

To show that every integer can be written as a unique sum of disticnt powers of $2$, we must show that the coefficient of every power of $x$ in $g^*(x) = 1 + x + x^2 + x^3 + \cdots = (1-x)^{-1} $ or equivalently, $(1-x)g^*(x)=1$.

Then they use the identity $(1-x^k)(1+x^k) = 1 - x^{2k}$ to manipulate $g^*(x)$: $$\begin{align*} (1-x)g^*(x) &= (1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\cdots\\ &= (1-x^2)(1+x^2) (1+x^4)(1+x^8)\cdots \\ &= (1-x^4)(1+x^4)(1+x^8)\cdots \\ &= \quad \quad \vdots\\ &= 1 \end{align*}$$

That is the the second part that I don't understand. If it's an infinite product, why can they "eventually eliminate all factors of $(1-x)g^*(x)$"?

---

Update: Alternative proofs are more than welcome.

---

Answer 1

For your second question, first note that

$$g^*(x)=\prod_{k\ge 0}\left(1+x^{2^k}\right)=(1+x)(1+x^2)(1+x^4)(1+x^8)\dots$$

makes sense: if $n\le 2^m$, the coefficient of $x^n$ in $g^*(x)$ is its coefficient in the polynomial $$\prod_{k=0}^m\left(1+x^{2^k}\right)\;,$$ because the contribution of any factor $1+x^{2^k}$ with $k>m$ must be a factor of $1$, not of $x^{2^k}$. Similarly, the coefficient of $x^n$ in the product

$$(1-x)g^*(x)=(1-x)(1+x)(1+x^2)(1+x^4)(1+x^8)\dots$$

is its coefficient in the polynomial

$$(1-x)\prod_{k=0}^m\left(1+x^{2^k}\right)\;,$$

for exactly the same reason. And by an easy induction

$$(1-x)\prod_{k=0}^m\left(1+x^{2^k}\right)=1-x^{2^{m+1}}\;,$$

so the coefficient of $x^0=1$ is $1$, and the coefficient of $x^n$ for $1\le n\le 2^m$ is $0$. Since this is true for every $m\in\Bbb Z^+$, for each $n>0$ the coefficient of $x^n$ in $(1-x)g^*(x)$ must be $0$, and since the constant term is $1$, $(1-x)g^*(x)=1$.

Answer 2

The $24$ makes no sense; perhaps it was meant to be $2^4$ or $2^k$ or something like that?

On your first question: The coefficient of $x^n$ in $g^*$ counts the number of ways that $n$ can be written as a sum of distinct non-negative powers of $2$. The claim is that this is $1$ for every $n$, so the claim is that $g^*$ is in fact $1+x+x^2+\dotso=(1-x)^{-1}$.

On your second question: Good question. Certainly if the product makes any sense it can only be $1$, since for each $n\gt1$ there's a stage where all powers of $x$ up to $x^n$ have already been eliminated, so no such $x^n$ can appear in the result; but that doesn't prove that the product makes any sense.

One way to make this rigorous would be to terminate the product at some point, interpret multiplying by $1-x$ as forming the differences of the coefficients of $x^n$ and $x^{n-1}$, and unravel the product until you arrive at $1-x^{2^k}$, which shows that all these differences are zero for $1\lt n\lt 2^k$, which shows that all integers up to $2^k$ have the same number of representations as sums of distinct non-negative powers of $2$ as $n=1$, which obviously has exactly one. Since you can choose $k$ arbitrarily high, it follows that this is true for all $n$.

Answer 3

The answer is binary: 0,1,10,11,100,101,110,111,1000,...

to prove every number has a unique binary expansion is easy. More generally every number has a unique base $b$ expansion: just iterate the division algorithm which uniquely splits any number $n$ into $n = m b + c$ with $0 \le c < b$.

---

The reason for using generating functions to show this is to get to grips with generating functions, rather than actually proving this result.

The most basic thing about these products is that whenever we have $$\cdots(a+b)(c+d)\cdots$$ multiplying it out will gives terms with $ac$ in it - or whatever choice we want. You should know the combinatorial interpretation of the coefficient of $x^k$ in $(1+x)^n$ for example: In the product $(1+x)(1+x)(1+x)$ we can get $x^2$ by choosing 1,x,x or x,1,x or x,x,1, so 3 ways.. so $3 x^2$ appears when you multiply it out.

So multiplying out $$(\color{blue}1+x)(1+\color{blue}{x^{2}})(1+\color{blue}{x^{4}})(\color{blue}1+x^{8})(\color{blue}1+x^{16})(1+\color{blue}{x^{32}})\cdots$$ will give you a sum with lots of terms in it, and it will surely contain the term $$1\cdot x^{2}\cdot x^{4} \cdot 1 \cdot 1 \cdot x^{32} = x^{2 + 4 + 32}$$ for example.

In fact multiplying out this product will give terms $x$ to the power of every sum if powers of two. So we know from the previous section that it's $$1 + x + x^2 + x^3 + x^4 + x^5 + \ldots$$ because each number can be written only once as a sum of powers of two.

---

It can be proved directly with the generating functions too, you should know this $$\frac{1}{1-x} = 1 + x + x^2 + x^3 + x^4 + x^5 + \ldots$$ if not it is very important to understand that before continuing.

So take our product and divide it by that, if we get $1$ we prove they are equal:

$$\begin{array}{lll} && (1-x)(1+x)(1+x^{2})(1+x^{4})(1+x^{8})(1+x^{16})(1+x^{32})\cdots \\ &=& (1-x^2)(1+x^{2})(1+x^{4})(1+x^{8})(1+x^{16})(1+x^{32})(1+x^{64})\cdots \\ &=& (1-x^4)(1+x^{4})(1+x^{8})(1+x^{16})(1+x^{32})(1+x^{64})(1+x^{128})\cdots \\ &=& (1-x^8)(1+x^{8})(1+x^{16})(1+x^{32})(1+x^{64})(1+x^{128})(1+x^{256})\cdots \\ &=& \cdots \\ \end{array}$$

this clearly proceeds by induction.

How does this prove the product is 1? Well what is the coefficient of $x^{7}$ in there for example? Take the series $\mod x^{8}$ to find out. In the same way any $n > 1$ you will find the coefficient of $x^{n}$ is $0$.