Euler, Erdős

Today, I'll prove Euler's Pentagonal Number Theorem and show how he used it to find recurrence formulae for the sum of \(n\)'s positive divisors and the partitions of \(n\). This post will be based on two papers I read last week: “An Observation on the Sums of Divisors” and “Euler and the Pentagonal Number Theorem”.

Definition 1. The generalized pentagonal numbers are those of the form \[ p(n) = \dfrac{3n^2-n}{2} \] for any integer \(n\).

Pentagonal Number Theorem. \[ \begin{aligned}(1-x)(1-x^2)(1-x^3)\cdots &= 1 - x - x^2 + x^5 +x^7- x^{12} -x^{15}+x^{22}+\cdots \\ &\text{or} \\ \prod_{i=1}^\infty (1-x^i) &= \sum_{i \in {\mathbb Z}} (-1)^i x^{p(i)} \end{aligned} \]

Apparently, Euler conjectured this theorem in \(1740\) (or earlier) but it was not until \(1750\) that he proved it; I am really awed by how long it took. What follows is a variation of the Euler's first proof. For the sake of brevity, my proof is very heavy with notation. Read the Proposition 3 for Euler's original proof; it's simple and elegant.

Proof: Let us define the series \(F_n\) as: \[ \begin{aligned} F_n &= 1 - x^{2n-1} - \sum_{i=3}^\infty x^{in-1}\prod_{j=0}^{i-3}(1-x^{n+j}) \\ &= 1 -x^{2n-1}-x^{3n-1} Q, \qquad \text{ for some series }Q\\ \therefore Q &= \sum_{i=0}^\infty x^{in}\prod_{j=0}^{i}(1-x^{n+j}) \\ &= 1 - x^n +\sum_{i=1}^\infty x^{in}(1-x^n)\prod_{j=1}^{i}(1-x^{n+j}) \\ &= 1 -x^n +\sum_{i=1}^\infty x^{in}\prod_{j=1}^{i}(1-x^{n+j}) - \sum_{i=1}^\infty x^{(i+1)n}\prod_{j=1}^{i}(1-x^{n+j}) \\ &= 1 -x^{2n+1} + \sum_{i=1}^\infty x^{(i+1)n}\prod_{j=1}^{i+1}(1-x^{n+j}) - \sum_{i=1}^\infty x^{(i+1)n}\prod_{j=1}^{i}(1-x^{n+j}) \\ &= 1 -x^{2(n+1)-1} - \sum_{i=3}^\infty x^{i(n+1)-1} \prod_{j=0}^{i-3}(1-x^{(n+1)+j}) \\ &= F_{n+1} \\ \ \therefore ~~ F_n &= 1 -x^{2n-1}-x^{3n-1}F_{n+1} \end{aligned} \] Given that \[ \begin{aligned} p(-n)+3n+2&=p(-n-1) \\ p(-n)+2n+1&=p(n+1) \end{aligned} \] we get the following recurrence \[ \begin{aligned} (-1)^n x^{p(-n)}F_{n+1} &=(-1)^n x^{p(-n)}\left(1 -x^{2n+1}-x^{3n+2}F_{n+2}\right) \\ &= (-1)^n(x^{p(-n)}-x^{p(n+1)})+(-1)^{n+1}x^{p(-n-1)}F_{n+2} \end{aligned} \] Let \(n=0\) and apply the recurrence inductively, \[ \begin{aligned} F_1 &= (x^{p(0)} - x^{p(1)}) - x^{p(-1)} F_2 \\ &= (x^{p(0)} - x^{p(1)}) - (x^{p(-1)}-x^{p(2)}) + (x^{p(-2)}-x^{p(3)}) - (x^{p(-3)}-x^{p(4)}) +\cdots \\ &= \sum_{i \in {\mathbb Z}}(-1)^i x^{p(i)} \end{aligned} \] To conclude the proof, \[ \prod_{i=1}^\infty (1-x^i) = (1 - x) -x^2(1-x) -x^3(1-x)(1-x^2) - \cdots = F_1 \]

Only Euler could spend a decade on a problem and make it seem so easy when he finally solved it. What follows is even more remarkable. He showed that there was a recurrence relation for the sum of \(n\)'s divisors. The divisors of \(n\) depend on the prime factorization of \(n\). Since there's no known order to the prime factorization of \(n\), one would expect no order in the sum of divisors. Nevertheless, Euler managed to find order in the least expected of places!

Definition 3. For any positive integer \(n\), \(\sigma(n)\) is the sum of positive divisors of \(n\).

Theorem 4. \[ \sigma(n) = \sum_{i \in {\mathbb Z}\setminus{0}} (-1)^{i+1} \sigma(n-p(i)) \] where \(\sigma(k) = 0\) for \(k<0\) and \(\sigma(n-n) = n\).

This proof is one of the earliest examples in which Euler uses analytic methods to study number-theoretic functions. It would be important to explain that Euler liked to manipulate infinite products/series (especially generating functions) as if they were continuous functions. For instance, in this proof, Euler expanded the logarithm of an infinite product and took the derivative of the results. These steps were not justified until the foundations of real analysis (or Formal Power Series) were established a century later; Euler was way ahead of his time.

Proof: Suppose \[ y = \prod_{i=1}^\infty (1-x^i) \] Then \[ \ln(y) = \sum_{i=1}^\infty \ln(1-x^i) \] After implicit differentiation \[ \begin{aligned} \frac{y'}{y} &= \sum_{i=1}^\infty \frac{-ix^{i-1}}{1-x^i} \\ \implies -\frac{x y'}{y} &= \sum_{i=1}^\infty \frac{ix^i}{1-x^i}= \sum_{i=1}^\infty(ix^i+ix^{2i}+ix^{3i}+\cdots) \\ &= \sum_{i=1}^\infty \sigma(i)x^i \end{aligned} \] By the Pentagonal Number Theorem, \[ -\frac{x y'}{y} = \dfrac{\sum\limits_{i \in {\mathbb Z}\setminus{0}} (-1)^{i+1} p(i)x^{p(i)}}{\sum\limits_{i \in {\mathbb Z}} (-1)^i x^{p(i)}} \] Equating the two forms of \(-\frac{x y'}{y}\), \[ \begin{aligned} \sum\limits_{i \in {\mathbb Z}\setminus{0}} (-1)^{i+1} p(i)x^{p(i)} &= \left(\sum\limits_{i \in {\mathbb Z}} (-1)^i x^{p(i)}\right) \left(\sum_{i=1}^\infty \sigma(i)x^i\right) \\ &= \sum_{j=1}^\infty \sum_{p(k)<j}(-1)^k\sigma(j-p(k))x^j \end{aligned} \] By comparing the coefficients of \(x^j\) and solving for \(\sigma(j)\) \[ \sigma(j) = \begin{cases} (-1)^{i+1} p(i) + \sum\limits_{0<p(k)<j}(-1)^{k+1}\sigma(j-p(k)), & \text{if } j = p(i) \text{ for some } i \\ \sum\limits_{0<p(k)<j}(-1)^{k+1}\sigma(j-p(k)), & \text{if } j\ne p(i) \text{ for any } i \end{cases} \]

Definition 5. For any positive integer \(n\), \(\rho(n)\) is the number of partitions of \(n\). We also define \(\rho(0)=1\) and \(\rho(-n)=0\).

Lastly, using another elegant generating function, \[ \prod_{i=1}^\infty \frac{1}{(1-x^i)} = \sum_{i=0}^\infty \rho(i)x^i \] Euler proved the recurrence formula for \(\rho(n)\).

Theorem 6. \[\rho(n) = \sum_{i \in {\mathbb Z}\setminus{0}} (-1)^{i+1} \rho(n-p(i))\]

This follows from the Pentagonal Number Theorem and the expansion of \[ 1 = \left(\prod_{i=1}^\infty(1-x^i)\right)\left(\sum_{i=0}^\infty \rho(i)x^i\right) \]