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.

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.


share|improve this question
    
More generally, every positive integer can be written uniquely as a sum of powers of $p\in \Bbb N_{>1}$. On a side note, Euler used this method to prove that the number partitions of an integer $n$ is the same as the number of odd partitions with repetitions. –  Pedro Tamaroff Mar 9 '13 at 19:42
    
You can think analytically: take $|x| < 1$ and the infinite product converges and the manipulation gets you within epsilon of 1. –  user58512 Mar 9 '13 at 20:00
add comment

3 Answers

up vote 1 down vote accepted

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$.

share|improve this answer
    
How is one supposed to realize that it is to make sense for $n \leq 2^m$? Its sort of misleading o.w. since the dots indicate it goes on forever. –  AlanH Mar 10 '13 at 2:49
1  
@Alan: It does go on forever. The point is that when you multiply a partial product, say $$\prod_{k=0}^m\left(1+x^{2^k}\right)\;,$$ by a later factor, say $1+x^{2^\ell}$, the only powers of $x$ that you can get are ones that you already had in the partial product and are muliplying by $1$, and ones that are at least $x^{2^\ell}$. Thus, you get no new $x^n$ terms for any $n\le 2^m$. Ever. You already have all of the possible $x^n$ terms for all $n\le 2^m$: longer partial products don’t change that part of the product. –  Brian M. Scott Mar 10 '13 at 13:47
add comment

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$.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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.