TAOCP 5.2.3 Exercise 27

Exercise 27. [M25] (T. Clausen, 1828.) Prove that

$$\sum_{n \ge 1} \frac{x^n}{1 - x^n} = \sum_{n \ge 1} \frac{1 + x^n}{1 - x^n} x^{n^2}.$$

(Setting $x = \frac{1}{2}$ gives a very rapidly converging series for the evaluation of (19).)

Verified: no
Solve time: 57s

Solution

The identity is an equality of formal power series (or absolutely convergent series for (|x|<1)).
We prove it by comparing coefficients.

Left-hand side.
[ \sum_{n\ge 1}\frac{x^n}{1-x^n} = \sum_{n\ge 1}\sum_{k\ge 1} x^{nk} = \sum_{m\ge 1} \tau(m),x^m, ] where (\tau(m)) denotes the number of positive divisors of (m).

Right-hand side.
Expand the geometric series: [ \sum_{n\ge 1}\frac{1+x^n}{1-x^n},x^{n^2} = \sum_{n\ge 1} x^{n^2}\sum_{k\ge 0}(x^{nk}+x^{n(k+1)}) = \sum_{n\ge 1}\sum_{k\ge 0}\bigl(x^{n(n+k)}+x^{n(n+k+1)}\bigr). ] In the first inner term set (j=n+k); as (k) runs over (k\ge 0), (j) runs over (j\ge n).
In the second inner term set (j=n+k+1); then (j) runs over (j\ge n+1).
Thus the right-hand side becomes [ \sum_{n\ge 1}\sum_{j\ge n} x^{nj} ;+; \sum_{n\ge 1}\sum_{j\ge n+1} x^{nj}. ]

For a fixed integer (m\ge 1), the coefficient of (x^m) in the first double sum is the number of divisors (n) of (m) with (n\le m/n), i.e. (n\le\sqrt{m}).
The coefficient in the second double sum is the number of divisors (n) of (m) with (n<m/n), i.e. (n<\sqrt{m}).

If (m) is not a perfect square, (\tau(m)) is even and the divisors pair up as ((n,m/n)) with (n<\sqrt{m}). Both double sums contribute (\tau(m)/2); their sum is (\tau(m)).
If (m) is a perfect square, one divisor equals (\sqrt{m}). The first sum contributes ((\tau(m)+1)/2) (it includes (\sqrt{m})), the second contributes ((\tau(m)-1)/2) (it excludes (\sqrt{m})); again the total is (\tau(m)).

Hence both sides have the same coefficient (\tau(m)) for every (m\ge 1), so the identity holds as formal power series (and absolutely for (|x|<1)). ∎

Notes

Setting (x=\frac12) gives a rapidly converging series for the constant (19) in the text: [ \sum_{n\ge 1}\frac{1}{2^n-1} = \sum_{n\ge 1}\frac{1+2^{-n}}{1-2^{-n}},2^{-n^2}. ] The terms decrease roughly like (2^{-n^2}), making it extremely efficient for numerical evaluation.