TAOCP 1.4.3.1 Exercise 5

Let S=\sum_{1<k\le n}\frac{H_k}{k(k-1)}.

taocpmathematicsalgorithmsvolume-1medium

Section 1.4.3.1: A MIX Simulator

Exercise 5. [24] Determine the time required to simulate the LDA and ENTA operators, compared with the actual time for MIX to execute these operators directly.

Verified: no
Solve time: -

Solution

Let

$$ S=\sum_{1<k\le n}\frac{H_k}{k(k-1)}. $$

Since

$$ \frac1{k(k-1)}=\frac1{k-1}-\frac1k, $$

the summand has the form $(a_{k+1}-a_k)b_k$ if we choose

$$ a_k=-\frac1{k-1}, \qquad b_k=H_k $$

for $k\ge2$. Then

$$ a_{k+1}-a_k =-\frac1k+\frac1{k-1} =\frac1{k(k-1)}. $$

Apply the summation-by-parts formula of Exercise 10 with the index range $2\le k\le n$, namely

$$ \sum_{2\le k\le n}(a_{k+1}-a_k)b_k = a_{n+1}b_n-a_2b_2 -\sum_{2\le k\le n}a_{k+1}(b_{k+1}-b_k). $$

Since

$$ a_{n+1}=-\frac1n,\qquad a_2=-1,\qquad H_2=\frac32, $$

and

$$ H_{k+1}-H_k=\frac1{k+1}, $$

we obtain

$$ S = -\frac{H_n}{n} +\frac32 +\sum_{2\le k\le n}\frac1k\cdot\frac1{k+1}. $$

The remaining sum telescopes:

$$ \frac1{k(k+1)} = \frac1k-\frac1{k+1}, $$

hence

$$ \sum_{2\le k\le n}\frac1{k(k+1)} = \sum_{2\le k\le n} \left(\frac1k-\frac1{k+1}\right) = \frac12-\frac1{n+1}. $$

Substituting,

$$ S = -\frac{H_n}{n} +\frac32 +\frac12 -\frac1{n+1} = 2-\frac1{n+1}-\frac{H_n}{n}. $$

Therefore

$$ \sum_{1<k\le n}\frac{1}{k(k-1)}H_k = 2-\frac1{n+1}-\frac{H_n}{n}. $$

Equivalently,

$$ \boxed{\sum_{1<k\le n}\frac{1}{k(k-1)}H_k = 2-\frac{H_n}{n}-\frac1{n+1}}. $$