Proof of an identity about integer partition

Question

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.

Answer 1

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.

Answer 2

If you want a combinatorial proof, you can now find one in the solution to Exercise 6 (b) of UMN Fall 2018 Math 5705 midterm #3. Just to clarify why that exercise is equivalent to the question posted here:

• My $p_k\left(n\right)$ is exactly what is called $p\left(n, k\right)$ here.

• The left hand side of the equality in my exercise is $\sum\limits_{k=0}^n k p_k\left(n\right)$, while the question here uses $\sum\limits_{k=1}^n k p\left(n,k\right)$ = $\sum\limits_{k=1}^n k p_k\left(n\right)$ instead. In other words, my left hand side differs in the inclusion of the $k = 0$ addend. But this makes no difference, since this addend is $0 p_0\left(n\right) = 0$.

• The right hand side of the equality in my exercise is $\sum\limits_{k=1}^n \partial\left(k\right) p\left(n-k\right)$ (where $\partial\left(k\right)$ means the number of positive divisors of $k$), while the question here uses $\sum\limits_{r, s \geq 1,\ rs\leq n} p\left(n-rs\right)$ instead. These are the same thing, because \begin{align*} & \underbrace{\sum_{r,s\geq1,\ rs\leq n}}_{=\sum\limits_{k\geq1,\ k\leq n} \sum\limits_{\substack{r,s\geq1;\\rs=k}}}p\left( n-rs\right) \\ & =\sum_{k\geq1,\ k\leq n}\sum_{\substack{r,s\geq1;\\rs=k}}p\left( n-\underbrace{rs}_{=k}\right) \\ & =\sum_{k\geq1,\ k\leq n}\underbrace{\sum_{\substack{r,s\geq1;\\rs=k} }p\left( n-k\right) }_{=\left\vert \left\{ \left( r,s\right) \in\left\{ 1,2,3,\ldots\right\} ^{2}\ \mid\ rs=k\right\} \right\vert \cdot p\left( n-k\right) }\\ & =\sum_{k\geq1,\ k\leq n}\underbrace{\left\vert \left\{ \left( r,s\right) \in\left\{ 1,2,3,\ldots\right\} ^{2}\ \mid\ rs=k\right\} \right\vert }_{\substack{=\left\vert \left\{ \text{positive divisors of }k\right\} \right\vert \\\text{(since there exists a bijection from }\left\{ \left( r,s\right) \in\left\{ 1,2,3,\ldots\right\} ^{2}\ \mid\ rs=k\right\} \\\text{to }\left\{ \text{positive divisors of }k\right\} \text{ (namely, the map sending each }\left( r,s\right) \text{ to }r\text{)}}}\cdot p\left( n-k\right) \\ & =\underbrace{\sum_{k\geq1,\ k\leq n}}_{=\sum_{k=1}^{n}} \underbrace{\left\vert \left\{ \text{positive divisors of }k\right\} \right\vert }_{\substack{=\left( \text{the number of positive divisors of }k\right) =\partial\left( k\right) \\\text{(by the definition of } \partial\left( k\right) \text{)}}}\cdot p\left( n-k\right) \\ & =\sum_{k=1}^{n}\partial\left( k\right) p\left( n-k\right) . \end{align*}

• I allow $n$ to be $0$. Yes, the equality is still true in that case, for rather obvious reasons.