# Partitions-Sum of divisors identity

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!

-

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).$$

-
I thought there world be direct proof of the identity, but I ended up counting two different thing, so deleted my answer. This survey math.ucla.edu/~pak/papers/psurvey.pdf by Igor Pak also contains the proof of the first identity, and tons of bijective proof of other identities. – i707107 Apr 9 '13 at 21:14

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}$.

-
Yes, this is much nicer than saying "by regrouping etc.". I also find the paper of Erdös ireally beautiful. Erdös says that this identity was already known to Hardy and Ramanujan, who had given the asymtptotic formula for $p(n)$ before. So perhaps we could call it the Hardy-Ramanujan-Erdös identity. – Dietrich Burde Apr 10 '13 at 8:15
Thank you! I will have a look at the paper by Erdos. – Gian Maria Dall'Ara Apr 10 '13 at 10:00

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 1 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.

-

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.

-