TAOCP 1.2.7 Exercise 16

Let S_n = 1 + \frac{1}{3} + \cdots + \frac{1}{2n-1} = \sum_{k=1}^{n}\frac{1}{2k-1}.

taocpmathematicsalgorithmsvolume-1medium

Section 1.2.7: Harmonic Numbers

Exercise 16. [18] Express the sum $1 + \frac{1}{3} + \cdots + \frac{1}{2n-1}$ in terms of harmonic numbers.

Verified: no
Solve time: -

Solution

Let

$$ S_n = 1 + \frac{1}{3} + \cdots + \frac{1}{2n-1} = \sum_{k=1}^{n}\frac{1}{2k-1}. $$

The harmonic number $H_{2n}$ contains all reciprocals from $1$ to $2n$:

$$ H_{2n} = \sum_{k=1}^{2n}\frac{1}{k} = \sum_{k=1}^{n}\frac{1}{2k-1}

  • \sum_{k=1}^{n}\frac{1}{2k}. $$

The second sum is

$$ \sum_{k=1}^{n}\frac{1}{2k} = \frac12\sum_{k=1}^{n}\frac{1}{k} = \frac12 H_n. $$

Hence

$$ H_{2n} = S_n + \frac12 H_n. $$

Solving for $S_n$ gives

$$ S_n = H_{2n} - \frac12 H_n. $$

Therefore,

$$ 1 + \frac{1}{3} + \cdots + \frac{1}{2n-1} = H_{2n} - \frac12 H_n. $$

$$ \boxed{H_{2n}-\frac12 H_n} $$