# How to transform this infinite sum

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

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

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

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

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

-