9
$\begingroup$

How to transform this infinite sum

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

to an infinite product

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

  • 0
    @robjohn, could you please email me? I sent something to six mods, lack addresses for you and mixedmath2012-12-10

4 Answers 4

7

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

  • 0
    Great and simple answer2012-12-10
6

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}{(q,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)}.$

  • 0
    Nevermind, it looks like mjqxxxx has posted it.2012-12-10
4

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

1

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.