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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.