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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How to transform this infinite sum


to an infinite product


share|cite|improve this question
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
up vote 7 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|cite|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:



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:


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



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


share|cite|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|cite|improve this answer

The usual technique is to study the function $$f(a, q) = \prod_{n = 1}^{\infty}\frac{1}{1 - aq^{n - 1}}\tag{1}$$ and then express it as a series $$f(a, q) = \sum_{n = 0}^{\infty}x_{n}a^{n}\tag{2}$$ Now we can see that $$f(aq, q) = (1 - a)f(a, q)\tag{3}$$ so that $$\sum_{n = 0}^{\infty}x_{n}a^{n}q^{n} = (1 - a)\sum_{n = 0}^{\infty}x_{n}a^{n}\tag{4}$$ and thus we have $$x_{n}q^{n} = x_{n} - x_{n - 1}$$ or $$x_{n} = \frac{x_{n - 1}}{1 - q^{n}} = \frac{x_{0}}{(1 - q)(1 - q^{2})\cdots(1 - q^{n})}$$ Putting $a = 0$ we can see that $x_{0} = 1$ and hence we have $$\prod_{n = 1}^{\infty}\frac{1}{1 - aq^{n - 1}} = \sum_{n = 0}^{\infty}\frac{a^{n}}{(1 - q)(1 - q^{2})\cdots(1 - q^{n})}\tag{5}$$ Putting $a = q$ we get $$\prod_{n = 1}^{\infty}\frac{1}{1 - q^{n}} = \sum_{n = 0}^{\infty}\frac{q^{n}}{(1 - q)(1 - q^{2})\cdots(1 - q^{n})}$$ which is what we need to prove (question uses $x$ in place of $q$).

The identity $(5)$ is a special case of the $q$-binomial theorem which says that $$\sum_{n = 0}^{\infty}\frac{(a;q)_{n}}{(q;q)_{n}}z^{n} = \frac{(az; q)_{\infty}}{(z; q)_{\infty}}\tag{6}$$ where $$(a;q)_{n} = \prod_{i = 1}^{n}(1 - aq^{i - 1}),\, (a;q)_{\infty} = \prod_{n = 1}^{\infty}(1 - aq^{n - 1})$$ Identity $(5)$ is derived when we put $a = 0$.

The above technique is a formal one (i.e. it does not deal with issues of convergence) which was perhaps championed by Euler and it can be used to prove many identities related to $q$-series.

share|cite|improve this answer

Your Answer


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.