3
$\begingroup$

Could you tell me how can I prove that every non-zero integer has an unique binary expansion using the generating functions, please?

1 Answers 1

4

Consider the infinite product

$P=\prod_{n=0}^\infty (1+x^{2^n}).$

This is a convergent product in the $x$-adic metric (under which the formal power series ring $R[[x]]$ is complete for any ring $R$, more or less by definition). Indeed, the $n^{\text{th}}$ term of the products affects only terms with degree $\geq 2^n$.

If you expand it out, you find that it can be written as

$\sum_{m=0}^\infty c_mx^m$

where $c_m$ is the number of ways of writing $m$ as a sum of distinct powers of $2$.

On the other hand, consider $(1-x)P_N$, where $P_N$ denotes the $N$th partial product of the infinite product above. It is easy to see that $(1-x)P_N=1-x^{2^{N}}$. Hence, taking the limit, we see that $(1-x)P=1$. This implies $P=1+x+x^2+\dots$, hence $c_m=1$ for all $m$ and $m$ has a unique binary representation.