TAOCP 7.2.1.4 Exercise 22

Let $E(q)=\prod_{m\ge 1}(1-q^m).$ Euler’s pentagonal number theorem gives $E(q)=\sum_{k\in \mathbb{Z}} (-1)^k q^{k(3k-1)/2}.$ Let $S(q)=\sum_{n\ge 1} \sigma(n) q^n.$

taocpmathematicsalgorithmsvolume-4hm-medium

Section 7.2.1.4: Generating All Partitions

Exercise 22. [HM21] [HM21] (L. Euler.) Let σ(n) be the sum of all positive divisors of the positive integer n. Thus, σ(n) = n + 1 when n is prime, and σ(n) can be significantly larger than n when n is highly composite. Prove that, in spite of this rather chaotic behavior, σ(n) satisfies almost the same recurrence (20) as the partition numbers: σ(n) = σ(n−1) + σ(n−2) −σ(n−5) −σ(n−7) + σ(n−12) + σ(n−15) −· · · for n ≥1, except that when a term on the right is ‘σ(0)’ the value ‘n’ is used instead. For example, σ(11) = 1 + 11 = σ(10) + σ(9) −σ(6) −σ(4) = 18 + 13 −12 −7; σ(12) = 1 + 2 + 3 + 4 + 6+ 12 = σ(11) +σ(10)−σ(7)−σ(5) + 12 = 12 + 18 −8 −6 + 12.

410 COMBINATORIAL SEARCHING 7.2.1.4

Verified: no
Solve time: 6m30s

Solution

Let

$E(q)=\prod_{m\ge 1}(1-q^m).$

Euler’s pentagonal number theorem gives

$E(q)=\sum_{k\in \mathbb{Z}} (-1)^k q^{k(3k-1)/2}.$

Let

$S(q)=\sum_{n\ge 1} \sigma(n) q^n.$

Step 1: Express $S(q)$ in terms of $E(q)$

For each $m\ge 1$ and $r\ge 1$, the integer $n=mr$ has a contribution $m$ from the divisor $m$. Hence

$S(q)=\sum_{m\ge 1}\sum_{r\ge 1} m q^{mr}=\sum_{m\ge 1}\frac{m q^m}{1-q^m}.$

Differentiate $\log E(q)$:

$\frac{E'(q)}{E(q)}=\sum_{m\ge 1}\frac{d}{dq}\log(1-q^m)=\sum_{m\ge 1}\frac{-m q^{m-1}}{1-q^m}.$

Multiplying by $q$ gives

$q\frac{E'(q)}{E(q)}=-\sum_{m\ge 1}\frac{m q^m}{1-q^m}=-S(q).$

Hence

$S(q)=-q\frac{E'(q)}{E(q)}, \qquad S(q)E(q)=-qE'(q).$

Step 2: Expand $-qE'(q)$

Write

$E(q)=\sum_{n\ge 0} \varepsilon(n) q^n,$

where $\varepsilon(0)=1$ and for $n>0$, $\varepsilon(n)$ equals $(-1)^k$ if $n=k(3k-1)/2$ for some integer $k$, and $0$ otherwise.

Then

$E'(q)=\sum_{n\ge 1} n,\varepsilon(n),q^{n-1},$

so

$-qE'(q)=-\sum_{n\ge 1} n,\varepsilon(n),q^n=-\sum_{n\ge 0} n,\varepsilon(n),q^n,$

since the $n=0$ term vanishes.

Thus

=-\sum_{n\ge 0} n,\varepsilon(n),q^n.$$ Equating coefficients of $q^n$ yields, for every $n\ge 0$, $$\sum_{k=0}^n \varepsilon(k)\sigma(n-k)=-n,\varepsilon(n).$$

Step 3: Extract the recurrence Split off the term $k=0$, using $\varepsilon(0)=1$:

$$\sigma(n)+\sum_{k=1}^n \varepsilon(k)\sigma(n-k)=-n,\varepsilon(n).$$ For $k>0$, the nonzero $\varepsilon(k)$ occur exactly at generalized pentagonal numbers $$k=\frac{j(3j\pm 1)}{2}, \quad j\ge 1,$$ with signs $(-1)^{j-1}$ in the standard alternating pattern. Rewriting the convolution gives $$\sigma(n)= -\sum_{k\ge 1} \varepsilon(k)\sigma(n-k) - n,\varepsilon(n).$$ The first sum reproduces Euler’s partition recurrence coefficients. The extra term $-n,\varepsilon(n)$ appears only when $n$ itself is a generalized pentagonal number, since otherwise $\varepsilon(n)=0$. The term involving $n$ corresponds exactly to the contribution of $\sigma(0)$ in the convolution. In the partition recurrence, the corresponding term would be $\varepsilon(n),p(0)$ with $p(0)=1$. Here the analogous term is $\varepsilon(n),\sigma(0)$, but the identity above shows that $\sigma(0)$ must be replaced by $n$. Thus the recurrence can be written in Euler’s pentagonal form: $$\sigma(n)=\sigma(n-1)+\sigma(n-2)-\sigma(n-5)-\sigma(n-7)+\sigma(n-12)+\sigma(n-15)-\cdots,$$ where the indices are generalized pentagonal numbers, and whenever a term $\sigma(0)$ arises, it is replaced by $n$. This completes the proof. ∎