I'd like to know how to prove the following identity,
$$\sum_{k=1}^n k\, p(n, k) = \sum_{r,s\ge 1, rs\le n} p(n-rs)$$
where $n\in N^+$. Here, $p(n)$ counts the number of possible partitions of $n$. Meanwhile, $p(n,k)$ is the restricted partition number, which counts the number of ways to partition $n$ into exactly $k$ parts.
I used Mathematica to directly verify this identity for $n=1,2…10$. So it should be correct. But I failed to give an analytical proof. It will be great if you can provide some hints or give your proof here : )
FYI, the context for me to show this identity is to justify the formula of Kac determinant in 2D conformal field theory. LHS is the power of Kac determinant computed from Virasoro algebra. RHS is also the power of Kac determinant but computed by using singular vectors. And I want to see they give the same answer(it should)
Here is my unsuccessful method. I tried to use induction and it goes as following:
(1) For $n=1,2$, we can do a direct calculation to see it is correct.
(2) For $n-1$, we assume it is correct. Then for $n$, we have,
\begin{align}
LHS &= \sum_{k=1}^n k\, p(n,k)=\sum_{k=1}^n k\, \left(p(n-k,k)+p(n-1,k-1) \right) \\
&= \sum_{k=1}^n k\,p(n-k,k) + (k-1)p(n-1,k-1) + p(n-1,k-1) \\
&= \sum_{k=1}^n k\,p(n-k,k) + p(n-1,k-1) + \sum_{k=1}^{n-1}k\,p(n-1,k)
\end{align}
\begin{align}
RHS =
\sum_{r,s\ge 1, rs\le n-1}p(n-rs)+\sum_{r,s\ge 1, n-1\le rs\le n}p(n-rs)
\end{align}
Now we have to show $\sum_{k=1}^n k\,p(n-k,k) + p(n-1,k-1) = \sum_{r,s\ge 1, n-1\le rs\le n}p(n-rs)$ to complete the proof. But I was stuck here.
Best Answer
The generating function of $\sum_{r,s\geq 1, \ rs\le n}p(n-rs)$ is $$\sum_{n=0}^\infty p(n)q^n\sum_{r=1}^\infty\frac{q^r}{1-q^r} =\sum_{r=1}^\infty\frac{q^r}{1-q^r} \prod_{j=1}^\infty\frac{1}{1-q^j}.\tag{1}$$ The $r$-th term in $(1)$ is $$\frac{q^r}{(1-q^r)^2}\prod_{j\ne r}\frac{1}{1-q^j} =\sum_{t=1}^\infty tq^{tr}\prod_{j\ne r}\frac{1}{1-q^j}.$$ This equals $$\sum_{\lambda\in\mathcal{P}}a_{r}(\lambda)q^{n_\lambda}$$ where $\mathcal{P}$ is the set of all partitions, $n_\lambda$ is the number partitioned by $\lambda$, and $a_r(\lambda)$ is the multiplicity of $r$ as a part of $\lambda$. Then $(1)$ is $$\sum_{\lambda\in\mathcal{P}}A(\lambda)q^{n_\lambda}$$ where $A(\lambda)$ is the number of parts of $\lambda$. But that is also $$\sum_{k=1}^\infty k\sum_{n=k}^\infty p(n,k)q^n=\sum_{n=0}^\infty\sum_{k=1}^n kp(n,k)q^n$$ which gives the desired result.