# Proof of an identity about integer partition

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.

• A comment on writing style: whenever possible, avoid starting a sentence with a mathematical expression. It's very confusing to read $n\in N^+.p(n)$ and $n.p(n,k)$, for example. A good alternative here would be to combine your first several sentences into one: "$\ldots$ where $n\in N^+$, $p(n)$ counts the number of possible partitions of $n$, and $p(n, k)$ is $\ldots$". Another possibility: "$\ldots$ where $n$ is a positive integer, $p(n)$ counts $\ldots$". – Théophile Jul 29 '18 at 23:26
• I see. Thanks for your comments! @Théophile – Edward Jul 30 '18 at 0:25

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.

• Thanks for your smart answer! Another question is how do you get that generating function, the Eqn(1)? I verified it is correct but I'm lack of intuition of why it works. Thanks! – Edward Jul 29 '18 at 19:43
• The inner sum is the double sum of $q^{rs}$ over $r$ and $s$. – Lord Shark the Unknown Jul 29 '18 at 19:44
• I see your point. Thank you so much! – Edward Jul 29 '18 at 20:31

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.