Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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