# How to prove it? (one of the Rogers-Ramanujan identities)

Prove the following identity (one of the Rogers-Ramanujan identities) on formal power series by interpreting each side as a generating function for partitions:

$$1+\sum_{k\geq1}\frac{z^k}{(1-z)(1-z^2)\cdots(1-z^k)}=\prod_{k\geq1}\frac{1}{1-z^k}$$

-
Above equation is not one of Rogers-Ramanujan identities see en.wikipedia.org/wiki/Rogers%E2%80%93Ramanujan_identities – Adi Dani Mar 27 '13 at 11:44

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

-
I want to prove it by interpreting each side as a generating function for partitions not by induction. Thank you anyway. – Geeeee Mar 27 '13 at 11:47
From your opinion what is generating function. The equation above is generating function of partition function $p(k)$ – Adi Dani Mar 27 '13 at 11:53
But what is $p(k)$ – Geeeee Mar 27 '13 at 12:08
$p(k)$ is number of partitions of natural number $k$ for example $p(3)=3$ because 3 has 3 partitions $3,1+2,1+1+1$ – Adi Dani Mar 27 '13 at 12:13
what does $1+\sum_{k\geq1}\frac{z^k}{(1-z)(1-z^2)...(1-z^k)}$ mean? – Geeeee Mar 27 '13 at 12:14

Notations: Let $[n]=\{1,2,\ldots n\}$

$P(n)$ is the number of partitions of $n$.

$P(k,[n])$ is the number of partitions of $k$ taking values from $[n]$. for example-$P(n)=P(n,[n])$

Note that coefficients of $x^n$ in left hand side is $\displaystyle\sum_{k=0}^{n-1}P(k,[n-k])$.Easy enough the coefficients of $x^n$ in the right hand side is $P(n)$.

We shall establish a bijection between them.

For some $m$, we shall denote any partition $<\lambda_1,\lambda_2,\ldots \lambda_m>_n$ among the set of partitions of $n$. With $\lambda_i\le\lambda_j$ for all $i\ge j$

Take any such partition $<\lambda_1,\lambda_2,\ldots \lambda_m>_k$. Construct a new partition $<\lambda_1,\lambda_2,\ldots \lambda_m,\lambda_{m+1}=n-k>_n$.

I claim by constructing new partitions like this from all the partitions of of each $i$, where $i\in[n-1]$ we get unique partitions of $n$.

Remark- For the case $k=0$ we add $n$ to get the trivial partition $<n>_n$.

Hence, on the contrary assume some two of the constructed partitions are equal. But the maximum element is $n-k$ for some partition constructed from $k$. Hence the two equal constructed partitions must be from the same $k$.

Easy enough to prove the partitions are equal.

Now, it remains to show in the other way, i.e. to show by subtracting the maximum element we get all such partitions. Whhich we can do by a very similar arguement.

-

Let us use the notation $[z^n] \sum_k a_k z^k$ to represent the operation of extracting $a_n$, the coefficients of $z^n$, from a formal power series $\sum_k a_k z^k$.

Let us look at the components in RHS of the identities we want to show: $$1+\sum_{k\geq1}\frac{z^k}{(1-z)(1-z^2)\cdots(1-z^k)}=\prod_{k\geq1}\frac{1}{1-z^k}\tag{*}$$

We know: $$[z^n]\frac{1}{1 - z^k} = \begin{cases}1,&k|n\\ 0,&\text{otherwise}\end{cases}$$ This represent the tautology that the number of ways to represent $n$ as a multiple of $k$ is $1$ if $k|n$ and $0$ otherwise. Similarly, the expression:

$$[z^n]\left(\frac{1}{1-z^k}\frac{1}{1-z^l}\right)$$

is the number of ways of breaking $n$ into 2 unordered pieces, one piece is a multiple of $k$ while the other is a multiple of $l$. In general,

$$[z^n] \prod_{k\ge 1}\frac{1}{1-z^k}$$ is the number of ways of breaking $n$ into sum of integers $\ge 1$. Once again, order of the breakdown doesn't matter.

In the LHS of $(*)$, the $k$-th term:

$$[z^n]\frac{z^k}{(1-z)(1-z^2)\cdots(1-z^{k})}$$

is the number of ways to represent $n$ as sum of positive integers $\le k$ and the factor $z^k$ in numerator constraints the sum to use the integer $k$ at least once. ie. if $n = c_0 + c_1 + \cdots + c_r$, is a breakdown of $n$ as sum of integers $c_s \ge 1$, the $k$ corresponds to $\max( \{ c_1, \ldots c_r \} )$, the maximum of integer appear in a breakdown.

The $\sum_{k}$ part in LHS of $(*)$ can now be interpreted as a sub sum of RHS with respect to the maximum of integer appear in a breakdown. The extra $1$ in LHS is used to cover the special case in RHS where $0$ is treated as a sum of zero number of positive integers.

-