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.

How to transform this infinite sum

$$\sum_{i\geq0}\frac{x^i}{(1-x)(1-x^2)\cdots(1-x^i)}$$

to an infinite product

$$\prod_{i\geq1}\frac{1}{1-x^i}$$

share|improve this question
1  
You are forgetting a $x^i$ in the numerator of the summand in the first expression. –  anon Dec 10 '12 at 14:26
    
@anon. Thank you i will correct it –  Adi Dani Dec 10 '12 at 14:30
3  
Are you sure they're equal? Putting $x = 0$ suggests not. –  arkeet Dec 10 '12 at 14:39
    
My bad, it should be $x^{i-1}$. I am using a different description of the sum. –  anon Dec 10 '12 at 14:40
2  
The expression in the problem is not quite correct; the sum needs to start at $i=0$, or else the two expressions differ by $1$. –  mjqxxxx Dec 10 '12 at 15:32

3 Answers 3

up vote 5 down vote accepted

Let $$a_{n}=\frac{x^{n}}{(1-x)(1-x^2)\cdots(1-x^{n})}$$ and $S_{n}=\sum_{i=0}^{n}a_i$. We want to show that $$ S_{n}=\frac{1}{(1-x)(1-x^2)\cdots(1-x^{n})}.$$ Clearly this is true for $n=1$, since $S_0=a_0=1$; and assuming it's true for $n=k$, we have $$ \begin{eqnarray} S_{k+1}&=&S_{k}+a_{k+1} \\ &=&\frac{1}{(1-x)\cdots(1-x^{k})}+\frac{x^{k+1}}{(1-x)\cdots(1-x^{k})(1-x^{k+1})} \\ &=&\frac{1-x^{k+1}}{(1-x)\cdots(1-x^{k})(1-x^{k+1})}+\frac{x^{k+1}}{(1-x)\cdots(1-x^{k})(1-x^{k+1})} \\ &=& \frac{1}{(1-x)(1-x^2)\cdots(1-x^{k+1})}, \end{eqnarray} $$ i.e., it's true for $n=k+1$. So it's true for all $n$ by induction. In particular, the partial products are equal to the partial sums, and $$ \sum_{i=0}^{\infty}\frac{x^{i}}{(1-x)(1-x^2)\cdots(1-x^{i})}=\prod_{i=1}^{\infty}\frac{1}{1-x^{i}}. $$

share|improve this answer
    
Great and simple answer –  Adi Dani Dec 10 '12 at 18:32

Combinatorical arguments are a nice way to manipulate generating functions (and vice-versa); we can make convergence a non-issue by working over formal polynomial series rings if need be.

The $q$-Pochhammer symbol is defined by $(a,q)_n:=(1-a)(1-aq)\cdots(1-aq^{n-1})$. The inverse of $(q,q)_n$ is a generating function for partitions of a certain type:

$$\frac{1}{(q,q)_n}=\frac{1}{1-q}\frac{1}{1-q^2}\cdots\frac{1}{1-q^n}$$

$$=\left(1+q+q^2+\cdots\right)\left(1+q^2+q^4+\cdots\right)\cdots\left(1+q^n+q^{2n}+\cdots\right).$$

The coefficient of $q^\ell$ above will be the number of ways it can be expressed as

$$q^\ell=q^{1\cdot j_1}q^{2\cdot j_2}\cdots q^{n\cdot j_n}$$

for nonnegative integers $j_i$, $1\le i\le n$, which are in bijective correspondence with partitions

$$(\underbrace{n,\cdots,n}_{j_n},\cdots,\underbrace{2,\cdots,2}_{j_2},\underbrace{1,\cdots,1}_{j_1})\vdash n.$$

These are precisely the integer partitions of $\ell$ with parts having size at most $n$.

The function $(a,q)_\infty^{-1}$ will also be a generating function:

$$\frac{1}{(a,q)_\infty}=\prod_{k\ge0}\frac{1}{1-aq^k}=\prod_{k=0}^\infty\left(1+aq^k+a^2q^{2k}+\cdots\right).$$

Evidently the coefficient of $a^nq^\ell$ above will be the number of ways to express it as

$$a^nq^\ell=a^{(j_0+j_1+j_2+\cdots)}(q^{0\cdot j_0}q^{1\cdot j_1}q^{2\cdot j_2}\cdots).$$

(Obviously almost all $j_i$s will be $0$ in these expressions.) These correspond to the partitions

$$(\cdots,\underbrace{3,\cdots,3}_{j_3},\underbrace{2,\cdots,2}_{j_2},\underbrace{1,\cdots,1}_{j_1})\vdash \ell.$$

These are precisely the integer partitions of $\ell$ having at most $n=\cdots+j_1+j_0$ parts. The partitions of $\ell$ into at most $n$ parts are in bijective correspondence with the partitions of $\ell$ into parts of size at most $n$ - the bijection is given by conjugating, or flipping the axes of, the Young diagrams that are associated to the partitions.) Thus the $q$-coefficient of $a^n$ in $(a,q)_\infty^{-1}$ is the generating function (in $q$) for partitions of integers $\ell$ into parts of size at most $n$, which we have already established is $(q,q)_n^{-1}$.

Therefore,

$$\frac{1}{(a,q)_\infty}=\sum_{n=0}^\infty\frac{a^n}{(a,q)_n}.$$

Plugging in $a=q$ gives your identity as the particular case

$$\frac{1}{(1-q)(1-q^2)(1-q^3)\cdots}=1+\sum_{n=1}^\infty\frac{q^n}{(1-q)(1-q^2)\cdots(1-q^n)}.$$

share|improve this answer
    
don't know the truth, but the sum wants to be a collapsing sum as $\frac{x^i}{(1-x)(1-x^2)\cdots(1-x^i)} = - \frac{1}{(1-x)(1-x^2)\cdots(1-x^{i-1})} + \frac{1}{(1-x)(1-x^2)\cdots(1-x^i)} $ –  mike Dec 10 '12 at 15:22
    
@mike: Yes, the series is telescoping in the way you describe, which actually makes for a slick answer requiring no combinatorial thinking. If you spruced up your answer a bit, it would be nice and we'd benefit from you undeleting it. –  anon Dec 10 '12 at 15:26
    
Nevermind, it looks like mjqxxxx has posted it. –  anon Dec 10 '12 at 15:27

Start by taking the difference $$ \begin{align} \prod_{i=1}^k\frac1{1-x^i}-\prod_{i=1}^{k-1}\frac1{1-x^i} &=\left(\frac1{1-x^k}-1\right)\prod_{i=1}^{k-1}\frac1{1-x^i}\\ &=\frac{x^k}{1-x^k}\prod_{i=1}^{k-1}\frac1{1-x^i}\\ &=\frac{x^k}{\prod_{i=1}^k(1-x^i)}\tag{1} \end{align} $$ Summing both sides of $(1)$ yields $$ \begin{align} \prod_{i=1}^n\frac1{1-x^i}-1 &=\sum_{k=1}^n\left(\prod_{i=1}^k\frac1{1-x^i}-\prod_{i=1}^{k-1}\frac1{1-x^i}\right)\\ &=\sum_{k=1}^n\frac{x^k}{\prod_{i=1}^k(1-x^i)}\tag{2} \end{align} $$ This proves that $$ \prod_{i=1}^n\frac1{1-x^i}-1=\sum_{k=1}^n\frac{x^k}{\prod_{i=1}^k(1-x^i)}\tag{3} $$ Equation $(3)$ says that the product and sum in the question differ by $1$, which agrees with computation when $x=0$. Noting that the term for $k=0$ on the right side of $(3)$ is $1$, we get $$ \prod_{i=1}^n\frac1{1-x^i}=\sum_{k=0}^n\frac{x^k}{\prod_{i=1}^k(1-x^i)}\tag{4} $$

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.