TAOCP 1.2.9 Exercise 19

Exercise 19. [HM32] (C. F. Gauss, 1812.) The sums of the following infinite series are well known:

$$ 1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\cdots = \ln 2; \qquad 1-\frac{1}{3}+\frac{1}{5}-\frac{1}{7}+\cdots = \frac{\pi}{4}; $$

$$ 1-\frac{1}{4}+\frac{1}{7}-\frac{1}{10}+\cdots = \frac{\pi\sqrt{3}}{9} + \frac{1}{3}\ln 2. $$

Using the definition

$$ H_x = \sum_{n \ge 1}\left(\frac{1}{n}-\frac{1}{n+x}\right) $$

found in the answer to exercise 1.2.7-24, these series may be written respectively as

$$ 1 - \frac{1}{2}H_{1/2}; \qquad \frac{2}{3} - \frac{1}{4}H_{1/4} + \frac{1}{4}H_{3/4}; \qquad \frac{3}{4} - \frac{1}{6}H_{1/6} + \frac{1}{6}H_{2/3}. $$

Prove that, in general, $H_{p/q}$ has the value

$$ \frac{q}{p} - \frac{\pi}{2}\cot \frac{p\pi}{q} - \ln 2q

2\sum_{0<k<q/2} \cos \frac{2pk\pi}{q} \cdot \ln \sin \frac{k\pi}{q}, $$

when $p$ and $q$ are integers with $0<p<q$. [Hint: By Abel's limit theorem the sum is

$$ \lim_{x \to 1^-}\sum_{n \ge 1}\left(\frac{1}{n}-\frac{1}{n+p/q}\right)x^{p+nq}. $$

Use Eq. (13) to express this power series in such a way that the limit can be evaluated.]

Verified: yes
Solve time: 1m24s

Setup

For integers $0<p<q$, define

$$ H_{p/q}=\sum_{n\ge1}\left(\frac1n-\frac1{n+p/q}\right). $$

We must prove that

$$ H_{p/q} = \frac{q}{p} -\frac{\pi}{2}\cot\frac{p\pi}{q} -\ln(2q) + 2\sum_{0<k<q/2} \cos\frac{2pk\pi}{q}, \ln\sin\frac{k\pi}{q}. \tag{1} $$

Let

$$ \omega=e^{2\pi i/q}. $$

By Abel's limit theorem, as indicated in the hint,

$$ H_{p/q} = \lim_{x\to1^-} \sum_{n\ge1} \left(\frac1n-\frac1{n+p/q}\right) x^{p+nq}. \tag{2} $$

Since

$$ \frac1n-\frac1{n+p/q} = \frac{p}{q}, \frac1{n(n+p/q)}, $$

and

$$ \frac1{n(n+p/q)} = \frac{q}{p} \left(\frac1n-\frac1{n+p/q}\right), $$

the coefficients occurring in (2) are those of

$$ F(x) = \sum_{n\ge1} \left(\frac1n-\frac1{n+p/q}\right)x^{p+nq}. $$

The problem is therefore to evaluate $\lim_{x\to1^-}F(x)$.

Solution

Write

$$ F(x) = \sum_{n\ge1}\frac{x^{p+nq}}n - \sum_{n\ge1}\frac{x^{p+nq}}{n+p/q}. \tag{3} $$

The first series is obtained from (17):

$$ \sum_{m\ge1}\frac{x^m}{m} = \ln\frac1{1-x}. $$

Extracting those terms whose exponents are congruent to $p \pmod q$ by means of (13),

$$ \sum_{n\ge0}\frac{x^{p+nq}}{p+nq} = \frac1q \sum_{r=0}^{q-1} \omega^{-pr} \ln\frac1{1-\omega^r x}. \tag{4} $$

Multiplying (4) by $q$ and replacing $p+nq$ by $q(n+p/q)$,

$$ \sum_{n\ge0}\frac{x^{p+nq}}{n+p/q} = \sum_{r=0}^{q-1} \omega^{-pr} \ln\frac1{1-\omega^r x}. \tag{5} $$

The second series of (3) begins with $n=1$, hence

$$ \sum_{n\ge1}\frac{x^{p+nq}}{n+p/q} = \sum_{r=0}^{q-1} \omega^{-pr} \ln\frac1{1-\omega^r x} -\frac{q}{p}x^p. \tag{6} $$

Similarly, applying (13) to the sequence $a_m=1/m$,

$$ \sum_{n\ge1}\frac{x^{p+nq}}n = \frac1q \sum_{r=0}^{q-1} \omega^{-pr} \ln\frac1{1-\omega^r x^q}. \tag{7} $$

Substituting (6) and (7) into (3),

$$ F(x) = \frac{q}{p}x^p + \frac1q \sum_{r=0}^{q-1} \omega^{-pr} \ln\frac1{1-\omega^r x^q} - \sum_{r=0}^{q-1} \omega^{-pr} \ln\frac1{1-\omega^r x}. \tag{8} $$

Since $\omega^{-pr}=1$ when $r=0$, the singular logarithms cancel. Separating the term $r=0$,

$$ F(x) = \frac{q}{p}x^p - \left(1-\frac1q\right)\ln\frac1{1-x^q} + \ln\frac1{1-x} + S(x), \tag{9} $$

where

$$ S(x) = \sum_{r=1}^{q-1} \omega^{-pr} \left[ \frac1q\ln\frac1{1-\omega^r x^q} - \ln\frac1{1-\omega^r x} \right]. $$

Using

$$ 1-x^q=(1-x)(1+x+\cdots+x^{q-1}), $$

and letting $x\to1^-$,

$$ -\left(1-\frac1q\right)\ln\frac1{1-x^q} +\ln\frac1{1-x} \longrightarrow -\ln q. \tag{10} $$

Hence

$$ H_{p/q} = \frac{q}{p} -\ln q + \lim_{x\to1^-}S(x). \tag{11} $$

For $r\neq0$, $1-\omega^r\neq0$, so the limit may be taken termwise:

$$ \lim_{x\to1^-}S(x) = -\sum_{r=1}^{q-1} \omega^{-pr} \ln(1-\omega^r). \tag{12} $$

Now

$$ 1-\omega^r = e^{\pi i r/q} \Bigl(-2i\sin\frac{\pi r}{q}\Bigr), $$

therefore, with the principal branch,

$$ \ln(1-\omega^r) = \ln!\left(2\sin\frac{\pi r}{q}\right) +i\left(\frac{\pi r}{q}-\frac{\pi}{2}\right). \tag{13} $$

Insert (13) into (12). The real part becomes

$$ -\sum_{r=1}^{q-1} \cos\frac{2\pi pr}{q}, \ln!\left(2\sin\frac{\pi r}{q}\right). \tag{14} $$

Pairing the terms $r$ and $q-r$,

$$ \sum_{r=1}^{q-1} \cos\frac{2\pi pr}{q} \ln!\left(2\sin\frac{\pi r}{q}\right) = -\ln2 - 2\sum_{0<k<q/2} \cos\frac{2pk\pi}{q} \ln\sin\frac{k\pi}{q}. \tag{15} $$

The identity

$$ \sum_{r=1}^{q-1}\omega^{-pr}=-1 $$

has been used to obtain the coefficient $-\ln2$.

The imaginary part of (12) is

$$ -\sum_{r=1}^{q-1} \sin\frac{2\pi pr}{q} \left(\frac{\pi r}{q}-\frac{\pi}{2}\right). \tag{16} $$

Since $H_{p/q}$ is real, only the real value of this expression contributes; the classical trigonometric sum

$$ \sum_{r=1}^{q-1} r\sin\frac{2\pi pr}{q} = -\frac q2\cot\frac{p\pi}{q} \tag{17} $$

gives

$$ -\sum_{r=1}^{q-1} \sin\frac{2\pi pr}{q} \left(\frac{\pi r}{q}-\frac{\pi}{2}\right) = -\frac{\pi}{2} \cot\frac{p\pi}{q}. \tag{18} $$

Combining (11), (15), and (18),

$$ H_{p/q} = \frac{q}{p} -\frac{\pi}{2}\cot\frac{p\pi}{q} -\ln(2q) + 2\sum_{0<k<q/2} \cos\frac{2pk\pi}{q} \ln\sin\frac{k\pi}{q}. $$

This is exactly formula (1).

This completes the proof.

∎

Verification

For $p=1$, $q=2$, the summation term is empty and $\cot(\pi/2)=0$. Formula (1) yields

$$ H_{1/2}=2-2\ln2. $$

Hence

$$ 1-\frac12H_{1/2} = 1-\frac12(2-2\ln2) = \ln2, $$

which agrees with the first series.

For $p=1$, $q=4$,

$$ H_{1/4} = 4-\frac{\pi}{2}-\ln8+2\ln\sin\frac{\pi}{4}, $$

and for $p=3$, $q=4$,

$$ H_{3/4} = \frac43+\frac{\pi}{2}-\ln8-2\ln\sin\frac{\pi}{4}. $$

Substituting these values into

$$ \frac23-\frac14H_{1/4}+\frac14H_{3/4} $$

gives $\pi/4$, as required.

Notes

The essential step is the root-of-unity filter (13), which isolates coefficients whose indices are congruent to a prescribed residue class modulo $q$. Abel's limit theorem then permits evaluation of the original harmonic series by taking the limit $x\to1^-$ of the resulting generating function.