Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

4 Answers 4

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

share|improve this answer
1  
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}$.

share|improve this answer
    
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

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.