Could you tell me how can I prove that every non-zero integer has an unique binary expansion using the generating functions, please?
Proving that every non-negative integer has an unique binary expansion with generating functions
1 Answers
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.