Partitions-sum of divisors identity

Question

A few years ago I first read about the marvelous Euler identity:

$\sum_{n\in\mathbb{N}}p(n)z^n=\prod_{k\geq1}\frac{1}{1-z^k}$,

where $p(n)$ is the number of partitions of $n$ ($p(0)=1$ by convention) and some of its beautiful consequences (like the pentagonal number theorem). Taking log of both sides of Euler identity and differentiating, the following nice recursive formula magically appears:

$np(n)=\sum_{k=0}^{n-1}p(k)\sigma(n-k)$,

where $\sigma(n)$ denotes the sum of the divisors of $n$. After some googling I found this identity quoted in a few places, but always without any reference. Since I am quite ignorant about the theory of partitions and related matters, I would like very much to know:

1) Who discovered this identity? Does it have a name?

and the much more interesting:

2) Is there a proof without generating functions?

Thank you!

Answer 1

2.) There is a proof, due to P. Erdös, in the Annals of Mathematics (2), 43, 1942, pp. 437-450, which does not use the generating function, but rather proves the identity $$ np(n)=\sum_{m=1}^n \sum_{k=1}^{n/m}mp(n-km) $$ by elementary regrouping etc. From this identity, it follows with $km=r$, $$ np(n)=\sum_{r=1}^np(n-r)\sum_{m\mid r}m=\sum_{r=1}^np(n-r)\sigma(r). $$

Answer 2

The proof by Erdös cited in D. Burde's answer can be made explicitly bijective. Interpret $np(n)$ as the number of ways to choose a partition $\lambda$ of $n$ and a box $B$ in the Young diagram of $\lambda$. Suppose that $B$ is in a row of length $m$ and that there are exactly $k$ rows of length $m$ below $B$, including the row containing $B$. Let $\mu$ be the partition of $n-km$ whose Young diagram is obtained from the Young diagram of $\lambda$ by removing these rows. Let $c \in \lbrace 1,\ldots , m\rbrace$ be the column containing $B$. Then $\lambda$ and $B$ are determined by $\mu$ and $c$, and so the map sending $(\lambda, B)$ to $(\mu, c)$ is a bijection. Hence

$$ np(n) = \sum_{m=1}^n \sum_k p(n-km)m = \sum_{r=1}^n p(n-r)\sigma(r) $$

where the final step is as in D. Burde's answer.

Erdös' paper includes a beautiful application of this identity, in which he uses induction on $n$ to show that $p(n) \le \exp c \sqrt{n}$ where $c = 2 \sqrt{\pi^2 /6}$.

Answer 3

Part 1.) R. Stanley mentions on page 59 (in the answer to exercise 24a, which is the identity mentioned in the OP) in Enumerative Combinatorics vol. 1 (exercise is 78a in later edition) the following somewhat inconclusive fact:

Some related results are due to Euler and recounted in $\S$303 of P.A. MacMahon, Combinatory Analysis, vol. 2, Cambridge University Press, 1916...

Searching the Euler archive showed a few similar results (but those were on the generating function of $\sigma(n)$ being related to the logarithmic derivative of the Euler generating function.

Answer 4

This idenity can be proved using symmetric functions, this is an exercise in the first chapter of Macdonald's book Symmetric Functions and Hall Polynomials.