Exercises from Section 1.2.7

2. [13] Show that the simple argument used in the text to prove that

H_{2^{m}} \geq 1 + m ∕ 2

can be slightly modiﬁed to prove that

H_{2^{m}} \leq 1 + m

We can show that the simple argument used in the text to prove that $H_{2^{m}} \geq 1 + m ∕ 2$ may be slightly modiﬁed to prove that $H_{2^{m}} \leq 1 + m$ , by noting that for each term, $1 ∕ (2^{m} + k) \leq 1 ∕ 2^{m}$ , as shown in the proof by induction below.

Proposition. $H_{2^{m}} \leq m + 1$ .

Proof. Let $m$ be an arbitrary integer such that $m \geq 0$ . We must show that $H_{2^{m}} \leq m + 1$ . In the case that $m = 0$ ,

H_{2^{0}} = H_{1} = 1 \leq 0 + 1 .

Then, assuming

H_{2^{m}} \leq m + 1

we must show that

H_{2^{m + 1}} \leq m + 2 .

But

\begin{array}{l} H_{2^{m + 1}} & = \sum_{1 \leq k \leq 2^{m + 1}} \frac{1}{k} \\ = \sum_{1 \leq k \leq 2^{m}} \frac{1}{k} + \sum_{2^{m} + 1 \leq k \leq 2^{m + 1}} \frac{1}{k} \\ = H_{2^{m}} + \sum_{2^{m} + 1 \leq k \leq 2^{m + 1}} \frac{1}{k} \\ = H_{2^{m}} + \sum_{1 \leq k \leq 2^{m}} \frac{1}{2^{m} + k} \\ \leq H_{2^{m}} + \sum_{1 \leq k \leq 2^{m}} \frac{1}{2^{m}} \\ = H_{2^{m}} + \frac{2^{m}}{2^{m}} \\ = H_{2^{m}} + 1 \\ \leq m + 1 + 1 \\ = m + 2 \end{array}

as we needed to show. □

3. [M21] Generalize the argument used in the previous exercise to show that, for

r > 1

, the sum

H_{n}^{(r)}

remains bounded for all

n

. Find an upper bound.

Proposition. $H_{n}^{(r)} \leq \frac{2^{r - 1}}{2^{r - 1} - 1}$ for $r > 1$ .

Proof. Let $n$ be an arbitrary nonnegative integer and $r$ an arbitrary real such that $r > 1$ . We must show that

H_{n}^{(r)} \leq \frac{2^{r - 1}}{2^{r - 1} - 1} .

First note that for arbitrary $m \geq 1$ , we may show that

\sum_{1 \leq k \leq 2^{m - 1}} \frac{1}{k^{r}} \leq \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} .

If $m = 1$ ,

\begin{array}{l} \sum_{1 \leq k \leq 2^{1 - 1}} \frac{1}{k^{r}} & = \sum_{1 \leq k \leq 0} \frac{1}{k^{r}} \\ = 0 \\ \leq 1 \\ = \frac{2^{0}}{2^{(0) r}} \\ = \sum_{0 \leq k < 1} \frac{2^{k}}{2^{k r}} . \end{array}

Then assuming

\sum_{1 \leq k \leq 2^{m - 1}} \frac{1}{k^{r}} \leq \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} .

we must show that

\sum_{1 \leq k \leq 2^{m}} \frac{1}{k^{r}} \leq \sum_{0 \leq k < m + 1} \frac{2^{k}}{2^{k r}} .

But

\begin{array}{l} \sum_{1 \leq k \leq 2^{m}} \frac{1}{k^{r}} & = \sum_{1 \leq k \leq 2^{m - 1}} \frac{1}{k^{r}} + \sum_{2^{m - 1} + 1 \leq k \leq 2^{m}} \frac{1}{k^{r}} \\ \leq \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} + \sum_{2^{m - 1} + 1 \leq k \leq 2^{m}} \frac{1}{k^{r}} \\ = \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} + \sum_{1 \leq k \leq 2^{m - 1}} \frac{1}{{(2^{m - 1} + k)}^{r}} \\ \leq \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} + \sum_{1 \leq k \leq 2^{m - 1}} \frac{1}{{(2^{m - 1})}^{r}} \\ = \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} + \frac{2^{m - 1}}{{(2^{m - 1})}^{r}} \\ = \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} + \frac{2^{m - 1}}{2^{(m - 1) r}} \\ \leq \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} + \frac{2^{m}}{2^{m r}} \\ = \sum_{0 \leq k < m + 1} \frac{2^{k}}{2^{k r}} \end{array}

and hence the noted inequality. We now continue with the main proof.

Since $2^{r - 1} > 1$ , we have both in the case that $n = 0$ that

H_{0}^{(r)} = \sum_{1 \leq k \leq 0} \frac{1}{k^{r}} = 0 \leq \frac{2^{r - 1}}{2^{r - 1} - 1}

and in the case that $n = 1 = 2^{m - 1}$ for $m = 1$ that

H_{1}^{(r)} = \sum_{1 \leq k \leq 1} \frac{1}{k^{r}} = 1 \leq \frac{2^{r - 1}}{2^{r - 1} - 1} .

Then, for arbitrary $m \geq 1$ , and since $2^{- m r + m + r - 1} = \frac{2^{r - 1}}{2^{(r - 1) m}} < 1 < 2^{r - 1}$ ,

\begin{array}{l} H_{2^{m - 1}}^{(r)} & = \sum_{1 \leq k \leq 2^{m - 1}} \frac{1}{k^{r}} \\ \leq \sum_{0 \leq k < m} \frac{2^{k}}{2^{k r}} \\ = \sum_{0 \leq k < m} \frac{1}{2^{(r - 1) k}} \\ = \sum_{0 \leq k \leq m - 1} 2^{(- r + 1) k} \\ = \frac{2^{(- r + 1) 0} - 2^{(- r + 1) m}}{1 - 2^{- r + 1}} \\ = \frac{1 - 2^{(- r + 1) m}}{1 - 2^{- r + 1}} \\ = \frac{(2^{m (r - 1)} - 1) ∕ 2^{m (r - 1)}}{(2^{r - 1} - 1) ∕ 2^{r - 1}} \\ = \frac{2^{r - 1} (2^{m (r - 1)} - 1)}{2^{m (r - 1)} (2^{r - 1} - 1)} \\ = \frac{2^{m (r - 1) + (r - 1)} - 2^{r - 1}}{2^{m (r - 1) + (r - 1)} - 2^{m (r - 1)}} \\ = \frac{2^{- m (r - 1)} (2^{m (r - 1) + (r - 1)} - 2^{r - 1})}{2^{r - 1} - 1} \\ = \frac{2^{- m (r - 1)} 2^{m (r - 1) + (r - 1)} - 2^{- m (r - 1)} 2^{r - 1}}{2^{r - 1} - 1} \\ = \frac{2^{r - 1} - 2^{- m (r - 1) + r - 1}}{2^{r - 1} - 1} \\ = \frac{2^{r - 1} - 2^{- m r + m + r - 1}}{2^{r - 1} - 1} \\ \leq \frac{2^{r - 1}}{2^{r - 1} - 1} \end{array}

as we needed to show. □

▸

4. [10] Decide which of the following statements are true for all positive integers

n

: (a)

H_{n} < \ln n

. (b)

H_{n} > \ln n

. (c)

H_{n} > \ln n + γ

In summary, (a) is false, while (b) and (c) are true, the justiﬁcation for each enumerated below.

a): $H_{n} < \ln n$ is not true for all positive integers $n$ , as may be seen by considering $n = 1$ , in which case, $H_{1} = 1 ≮ 0 = \ln 1$ .
b): $H_{n} > \ln n$ is true for all positive integers $n$ , as may be deduced from Eq. (3), since $γ + \frac{1}{2 n} - \frac{1}{12 n^{2}} + \frac{1}{120 n^{4}} - 𝜖 > 0$ .
c): $H_{n} > \ln n + γ$ is true for all positive integers $n$ , as may also be deduced from Eq. (3), since $\frac{1}{2 n} - \frac{1}{12 n^{2}} + \frac{1}{120 n^{4}} - 𝜖 > 0$ .

5. [15] Give the value of

H_{10000}

to 15 decimal places, using the tables in Appendix A.

From Eq. (3) we know

\begin{array}{l} H_{10000} & = \ln 10000 + γ + \frac{1}{2 (10000)} - \frac{1}{12 {(10000)}^{2}} + \frac{1}{120 {(10000)}^{4}} - 𝜖 \end{array}

for $0 < 𝜖 < \frac{1}{252 {(10000)}^{6}}$ . Letting $𝜖^{'} = \frac{1}{120 {(10000)}^{4}} - 𝜖 > 0$ , since

\begin{array}{l} 𝜖^{'} & < \frac{1}{120 {(10000)}^{4}} \\ = \frac{1}{1.2 \times 1 0^{18}} \\ < \frac{1}{1 0^{18}}, \end{array}

we may ignore $𝜖^{'}$ in order to approximate $H_{10000}$ to only 15 decimal places as

\begin{array}{l} H_{10000} & \approx \ln 10000 + γ + \frac{1}{2 (10, 000)} - \frac{1}{12 {(10, 000)}^{2}} \\ = 4 \ln 10 + γ + \frac{59999}{1200000000} . \end{array}

Given

\begin{array}{l} \ln 10 & = 2.30258 50929 94045 6 + \\ γ & = 0.57721 56649 01532 8 + \\ \frac{59999}{1200000000} & = 0.00004 99991 66666 6 + \end{array}

we may compute the sum as

	2.30258 50929 94045 6
	2.30258 50929 94045 6
	2.30258 50929 94045 6
	2.30258 50929 94045 6
	0.57721 56649 01532 8
$+$	0.00004 99991 66666 6

	9.78760 60360 44381 8

That is,

H_{10000} \approx 9.78760 60360 44382 \dots

6. [M15] Prove that the harmonic numbers are directly related to Stirling’s numbers, which were introduced in the previous section; in fact,

Proposition. $H_{n} = [\binom{n + 1}{2}] / n!$ .

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

H_{n} = [\binom{n + 1}{2}] / n! .

In the case that $n = 0$ ,

\begin{array}{l} H_{0} & = \sum_{1 \leq k \leq 0} \frac{1}{k} \\ = 0 \\ = [\binom{1}{2}] \\ = [\binom{0 + 1}{2}] / 0! . \end{array}

Then, assuming

H_{n} = [\binom{n + 1}{2}] / n!

we must show that

H_{n + 1} = [\binom{n + 2}{2}] / (n + 1)! .

But

\begin{array}{l} H_{n + 1} & = H_{n} + \frac{1}{n + 1} \\ = ([\binom{n + 1}{2}] / n!) + \frac{1}{n + 1} \\ = ((n + 1) [\binom{n + 1}{2}] + n!) / (n + 1)! \\ = ((n + 1) [\binom{n + 1}{2}] + [\binom{n + 1}{1}]) / (n + 1)! & from Eq. (50) \\ = ((n + 1) [\binom{n + 1}{2}] + [\binom{n + 1}{2 - 1}]) / (n + 1)! \\ = [\binom{n + 2}{2}] / (n + 1)! & from Eq. (46) \end{array}

as we needed to show. □

7. [M21] Let

T (m, n) = H_{m} + H_{n} - H_{m n}

. (a) Show that when

m

n

increases,

T (m, n)

never increases (assuming that

m

and

n

are positive). (b) Compute the minimum and maximum values of

T (m, n)

for

m, n > 0

We may provide a proof and determine bounds.

a)

We may show that

T (m, n)

never increases.

Proposition. $T (m + 1, n) \leq T (m, n)$ for $m, n$ positive integers.

Proof. Deﬁne $T (m, n)$ as

T (m, n) = H_{m} + H_{n} - H_{m n}

and let $m$ and $n$ be arbitrary positive integers. We must show that

T (m + 1, n) - T (m, n) \leq 0 .

But

\begin{array}{l} T (m + 1, n) - T (m, n) & = (H_{m + 1} + H_{n} - H_{(m + 1) n}) - (H_{m} + H_{n} - H_{m n}) \\ = H_{m + 1} + H_{n} - H_{(m + 1) n} - H_{m} - H_{n} + H_{m n} \\ = H_{m + 1} - H_{(m + 1) n} - H_{m} + H_{m n} \\ = \frac{1}{m + 1} - \sum_{m n + 1 \leq k \leq m n + n} \frac{1}{k} \\ \leq \frac{1}{m + 1} - \sum_{m n + 1 \leq k \leq m n + n} \frac{1}{m n + n} \\ = \frac{1}{m + 1} - \frac{n}{m n + n} \\ = \frac{1}{m + 1} - \frac{1}{m + 1} \\ = 0 \end{array}

as we needed to show. □

b)

We may determine both the lower and upper bounds of

T (m, n)

, for

m, n

positive integers. Since

T (m, n)

never increases, we know that the lower bound corresponds to the limit as

m \to \infty

, and from Eq. (3),

\lim_{m \to \infty} T (m, n) = \lim_{m \to \infty} (H_{m} + H_{n} - H_{m n}) = \lim_{m \to \infty} (H_{m} - \ln m) = γ .

Similarly, since $T (m, n)$ never increases, we know that the upper bound corresponds to $m = n = 1$ , and

T (1, 1) = H_{1} + H_{1} - H_{1} = H_{1} = 1 .

______________________________________________________________________________________________________________________________

[AMM 70 (1963), 575–577]

8. [HM18] Compare Eq. (8) with

\sum_{k = 1}^{n} \ln k

; estimate the diﬀerence as a function of

n

Given Eq. (8)

\sum_{1 \leq k \leq n} H_{k} = (n + 1) H_{n} - n

we may estimate the diﬀerence with $\sum_{1 \leq k \leq n} \ln k$ . First, we note from Eq. (3) that

\begin{array}{l} \sum_{1 \leq k \leq n} H_{k} & = (n + 1) H_{n} - n \\ \approx (n + 1) (\ln n + γ + 1 ∕ 2 n) - n \\ = (n + 1) \ln n + (n + 1) γ + (n + 1) ∕ 2 n - n \\ = (n + 1) \ln n - n + (n + 1) γ + (n + 1) ∕ 2 n \\ \approx (n + 1) \ln n - n + (n + 1) γ + 1 ∕ 2 \\ = (n + 1) \ln n - n + n γ + γ + 1 ∕ 2 \\ = (n + 1) \ln n - n (1 - γ) + (γ + 1 ∕ 2) . \end{array}

Second, we note from Stirling’s approximation that

\begin{array}{l} \sum_{1 \leq k \leq n} \ln k & = \ln n! \\ \approx \ln \sqrt{2 π n} {(\frac{n}{e})}^{n} \\ = \ln \sqrt{2 π} + \frac{1}{2} \ln n + n \ln n - n \ln e \\ = \ln \sqrt{2 π} + (n + \frac{1}{2}) \ln n - n \\ = (n + \frac{1}{2}) \ln n - n + \ln \sqrt{2 π} . \end{array}

And so,

\begin{array}{l} \sum_{1 \leq k \leq n} H_{k} - \sum_{1 \leq k \leq n} \ln k \\ \approx ((n + 1) \ln n - n (1 - γ) + (γ + \frac{1}{2})) - ((n + \frac{1}{2}) \ln n - n + \ln \sqrt{2 π}) \\ = (n + 1) \ln n + - n + γ n + γ + \frac{1}{2} - (n + \frac{1}{2}) \ln n + n - \ln \sqrt{2 π} \\ = γ n + (n + 1 - n - \frac{1}{2}) \ln n + γ + \frac{1}{2} - \ln \sqrt{2 π} \\ = γ n + \frac{1}{2} \ln n + γ + \frac{1}{2} - \ln \sqrt{2 π} \\ \approx γ n + \frac{1}{2} \ln n + . 158 . \end{array}

▸

9. [M18] Theorem A applies only when

x > 0

; what is the value of the sum considered when

x = - 1

We make a proposition and oﬀer proof in the case that $x = - 1$ .

Proposition. $\sum_{1 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{k} H_{k} = - \frac{1}{n}$ .

Proof. Let $n$ be an arbitrary positive integer. We must show that

\sum_{1 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{k} H_{k} = - \frac{1}{n} .

If $n = 1$ ,

\sum_{1 \leq k \leq 1} (\binom{1}{k}) {(- 1)}^{k} H_{k} = (\binom{1}{1}) {(- 1)}^{1} H_{1} = - \frac{1}{1} .

Then, assuming

\sum_{1 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{k} H_{k} = - \frac{1}{n},

we must show that

\sum_{1 \leq k \leq n + 1} (\binom{n + 1}{k}) {(- 1)}^{k} H_{k} = - \frac{1}{n + 1} .

But

\begin{array}{l} \sum_{1 \leq k \leq n + 1} (\binom{n + 1}{k}) {(- 1)}^{k} H_{k} \\ = \sum_{1 \leq k \leq n + 1} ((\binom{n}{k}) + (\binom{n}{k - 1})) {(- 1)}^{k} H_{k} \\ = \sum_{1 \leq k \leq n + 1} (\binom{n}{k}) {(- 1)}^{k} H_{k} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k} H_{k} \\ = \sum_{1 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{k} H_{k} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k} H_{k} \\ = - \frac{1}{n} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k} H_{k} \\ = - \frac{1}{n} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} H_{k} \\ = - \frac{1}{n} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} (H_{k - 1} + \frac{1}{k}) \\ = - \frac{1}{n} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} H_{k - 1} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} \frac{1}{k} \\ = - \frac{1}{n} - \sum_{0 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{k} H_{k} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} \frac{1}{k} \\ = - \frac{1}{n} - \sum_{1 \leq k \leq n} (\binom{n}{k}) {(- 1)}^{k} H_{k} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} \frac{1}{k} \\ = - \frac{1}{n} + \frac{1}{n} - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} \frac{1}{k} \\ = - \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) {(- 1)}^{k - 1} \frac{1}{k} \\ = - \sum_{1 \leq k \leq n + 1} \frac{1}{n + 1} (\binom{n + 1}{k}) {(- 1)}^{k - 1} & from Eq. 1.2.6-(7) \\ = \frac{1}{n + 1} \sum_{1 \leq k \leq n + 1} (\binom{n + 1}{k}) {(- 1)}^{k} \\ = \frac{1}{n + 1} (- (\binom{n + 1}{0}) {(- 1)}^{0} + \sum_{0 \leq k \leq n + 1} (\binom{n + 1}{k}) {(- 1)}^{k}) \\ = \frac{1}{n + 1} (- 1 + {(1 - 1)}^{n + 1}) \\ = - \frac{1}{n + 1} \end{array}

as we needed to show. □

10. [M20] (Summation by parts.) We have used special cases of the general method of summation by parts in exercise 1.2.4-42 and in the derivation of Eq. (9). Prove the general formula

Proposition. $\sum_{1 \leq k < n} (a_{k + 1} - a_{k}) b_{k} = a_{n} b_{n} - a_{1} b_{1} - \sum_{1 \leq k < n} a_{k + 1} (b_{k + 1} - b_{k})$ .

Proof. Let $n$ be an arbitrary positive integer. We must show that

\sum_{1 \leq k < n} (a_{k + 1} - a_{k}) b_{k} = a_{n} b_{n} - a_{1} b_{1} - \sum_{1 \leq k < n} a_{k + 1} (b_{k + 1} - b_{k}) .

But

\begin{array}{l} \sum_{1 \leq k < n} (a_{k + 1} - a_{k}) b_{k} \\ = \sum_{1 \leq k < n} a_{k + 1} b_{k} - \sum_{1 \leq k < n} a_{k} b_{k} \\ = \sum_{1 \leq k < n} a_{k + 1} b_{k} - \sum_{0 \leq k < n - 1} a_{k + 1} b_{k + 1} \\ = \sum_{1 \leq k < n} a_{k + 1} b_{k} - (a_{1} b_{1} + \sum_{1 \leq k < n} a_{k + 1} b_{k + 1} - a_{n} b_{n}) \\ = a_{n} b_{n} - a_{1} b_{1} + \sum_{1 \leq k < n} a_{k + 1} b_{k} - \sum_{1 \leq k < n} a_{k + 1} b_{k + 1} \\ = a_{n} b_{n} - a_{1} b_{1} - (\sum_{1 \leq k < n} a_{k + 1} b_{k + 1} - \sum_{1 \leq k < n} a_{k + 1} b_{k}) \\ = a_{n} b_{n} - a_{1} b_{1} - \sum_{1 \leq k < n} a_{k + 1} (b_{k + 1} - b_{k}) \end{array}

as we needed to show. □

The sum may be evaluated using summation by parts as

\begin{array}{l} \sum_{1 < k \leq n} \frac{1}{k (k - 1)} H_{k} \\ = \sum_{1 < k \leq n} \frac{k - (k - 1)}{k (k - 1)} H_{k} \\ = \sum_{1 < k \leq n} (\frac{1}{k - 1} - \frac{1}{k}) H_{k} \\ = \sum_{1 < k \leq n} (- \frac{1}{(k + 1) - 1} - - \frac{1}{k - 1}) H_{k} \\ = \sum_{1 \leq k < n} (- \frac{1}{k + 1} - - \frac{1}{k}) H_{k + 1} \\ = - \frac{1}{n} H_{n + 1} - - \frac{1}{1} H_{1 + 1} - \sum_{1 \leq k < n} - \frac{1}{k + 1} (H_{(k + 1) + 1} - H_{k + 1}) \\ = - \frac{1}{n} (H_{n} + \frac{1}{n + 1}) + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{1}{k + 1} (H_{(k + 1) + 1} - H_{k + 1}) \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{1}{k + 1} (H_{(k + 1) + 1} - H_{k + 1}) \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{1}{k + 1} \frac{1}{k + 2} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{1}{(k + 1) (k + 2)} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{(k + 2) - (k + 1)}{(k + 1) (k + 2)} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{1}{k + 1} - \frac{1}{k + 2} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k < n} \frac{1}{k + 1} - \sum_{1 \leq k < n} \frac{1}{k + 2} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{2 \leq k \leq n} \frac{1}{k} - \sum_{3 \leq k \leq n + 1} \frac{1}{k} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + \sum_{1 \leq k \leq n} \frac{1}{k} - 1 - (\sum_{1 \leq k \leq n} \frac{1}{k} - 1 - \frac{1}{2} + \frac{1}{n + 1}) \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + H_{n} - 1 - (H_{n} - 1 - \frac{1}{2} + \frac{1}{n + 1}) \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 1 + \frac{1}{2} + H_{n} - 1 - H_{n} + 1 + \frac{1}{2} - \frac{1}{n + 1} \\ = - \frac{1}{n} H_{n} - \frac{1}{n} \frac{1}{n + 1} + 2 - \frac{1}{n + 1} \\ = 2 - H_{n} ∕ n - (\frac{1}{n (n + 1)} + \frac{1}{n + 1}) \\ = 2 - H_{n} ∕ n - \frac{n + 1}{n (n + 1)} \\ = 2 - H_{n} ∕ n - 1 ∕ n . \end{array}

▸

12. [M10] Evaluate

H_{\infty}^{1000}

correct to at least 100 decimal places.

By deﬁnition

H_{\infty}^{1000} = \sum_{k \geq 1} \frac{1}{k^{1000}} = 1 + \sum_{k \geq 2} \frac{1}{k^{1000}} = 1 + 𝜖

where $𝜖 \leq \frac{2^{1000 - 1}}{2^{1000 - 1} - 1} - 1$ from exercise 3, and

\begin{array}{l} 𝜖 & \leq \frac{2^{1000 - 1}}{2^{1000 - 1} - 1} - 1 \\ = \frac{2^{999}}{2^{999} - 1} - 1 \\ = \frac{2^{999} - 1 + 1}{2^{999} - 1} - 1 \\ = \frac{1}{2^{999} - 1} + 1 - 1 \\ = \frac{1}{2^{999} - 1} \\ < \frac{1}{2^{998}} \\ = \frac{1}{1 0^{998 \ln 2 ∕ \ln 10}} & < \frac{1}{1 0^{300}} \end{array}

so that

H_{\infty}^{1000} = 1.000 \dots

to at least 100 decimal places.

(Note in particular the special case

x = 0

, which gives us an identity related to exercise 1.2.6-48.)

Proposition. $\sum_{1 \leq k \leq n} \frac{x^{k}}{k} = H_{n} + \sum_{1 \leq k \leq n} (\binom{n}{k}) \frac{{(x - 1)}^{k}}{k}$ .

Proof. Let $n$ be an arbitrary positive integer and $x$ an arbitrary real. We must show that

\sum_{1 \leq k \leq n} \frac{x^{k}}{k} = H_{n} + \sum_{1 \leq k \leq n} (\binom{n}{k}) \frac{{(x - 1)}^{k}}{k} .

In the case that $n = 1$

\sum_{1 \leq k \leq 1} \frac{x^{k}}{k} = x = 1 + (\binom{1}{1}) (x - 1) = H_{1} + \sum_{1 \leq k \leq 1} (\binom{1}{k}) \frac{{(x - 1)}^{k}}{k} .

Then, assuming

\sum_{1 \leq k \leq n} \frac{x^{k}}{k} = H_{n} + \sum_{1 \leq k \leq n} (\binom{n}{k}) \frac{{(x - 1)}^{k}}{k}

we must show that

\sum_{1 \leq k \leq n + 1} \frac{x^{k}}{k} = H_{n + 1} + \sum_{1 \leq k \leq n + 1} (\binom{n + 1}{k}) \frac{{(x - 1)}^{k}}{k} .

But

\begin{array}{l} \sum_{1 \leq k \leq n + 1} \frac{x^{k}}{k} \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{x^{n + 1}}{n + 1} \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \frac{x^{n + 1}}{n + 1} - \frac{1}{n + 1} \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \frac{1}{n + 1} ({(1 + (x - 1))}^{n + 1} - 1) \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \frac{1}{n + 1} (\sum_{0 \leq k \leq n + 1} (\binom{n + 1}{k}) {(x - 1)}^{k} - 1) \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \frac{1}{n + 1} (\sum_{0 \leq k \leq n + 1} (\binom{n + 1}{k}) {(x - 1)}^{k} - (\binom{n + 1}{0}) {(x - 1)}^{0}) \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \frac{1}{n + 1} \sum_{1 \leq k \leq n + 1} (\binom{n + 1}{k}) {(x - 1)}^{k} \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \frac{1}{n + 1} \sum_{1 \leq k \leq n + 1} \frac{n + 1}{k} (\binom{n}{k - 1}) {(x - 1)}^{k} & from Eq. 1.2.6-(7) \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \sum_{1 \leq k \leq n + 1} \frac{n + 1}{n + 1} \frac{1}{k} (\binom{n}{k - 1}) {(x - 1)}^{k} \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) \frac{{(x - 1)}^{k}}{k} \\ = \sum_{1 \leq k \leq n} \frac{x^{k}}{k} + \frac{1}{n + 1} + (\binom{n}{n + 1}) \frac{{(x - 1)}^{n + 1}}{n + 1} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) \frac{{(x - 1)}^{k}}{k} \\ = H_{n} + \sum_{1 \leq k \leq n} (\binom{n}{k}) \frac{{(x - 1)}^{k}}{k} + \frac{1}{n + 1} + (\binom{n}{n + 1}) \frac{{(x - 1)}^{n + 1}}{n + 1} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) \frac{{(x - 1)}^{k}}{k} \\ = H_{n + 1} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k}) \frac{{(x - 1)}^{k}}{k} + \sum_{1 \leq k \leq n + 1} (\binom{n}{k - 1}) \frac{{(x - 1)}^{k}}{k} \\ = H_{n + 1} + \sum_{1 \leq k \leq n + 1} ((\binom{n}{k}) + (\binom{n}{k - 1})) \frac{{(x - 1)}^{k}}{k} \\ = H_{n + 1} + \sum_{1 \leq k \leq n + 1} (\binom{n + 1}{k}) \frac{{(x - 1)}^{k}}{k} \end{array}

as we needed to show. □

14. [M22] Show that

\sum_{k = 1}^{n} H_{k} ∕ k = \frac{1}{2} (H_{n}^{2} + H_{n}^{(2)})

, and evaluate

\sum_{k = 1}^{n} H_{k} ∕ (k + 1)

We may prove the identity.

Proposition. $\sum_{1 \leq k \leq n} H_{k} ∕ k = \frac{1}{2} (H_{n}^{2} + H_{n}^{(2)})$ .

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

\sum_{1 \leq k \leq n} H_{k} ∕ k = \frac{1}{2} (H_{n}^{2} + H_{n}^{(2)}) .

But

\begin{array}{l} \sum_{1 \leq k \leq n} H_{k} ∕ k \\ \sum_{1 \leq k \leq n} \frac{1}{k} H_{k} \\ = \sum_{1 \leq k \leq n} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = \sum_{1 \leq k \leq n} \sum_{1 \leq j \leq k} \frac{1}{k} \frac{1}{j} \\ = \frac{1}{2} ({(\sum_{1 \leq k \leq n} \frac{1}{k})}^{2} + (\sum_{1 \leq k \leq n} \frac{1}{k^{2}})) & from Eq. 1.2.3-(13) \\ = \frac{1}{2} (H_{n}^{2} + H_{n}^{(2)}) \end{array}

as we needed to show. □

Thus, we may evaluate the sum as

\begin{array}{l} \sum_{1 \leq k \leq n} H_{k} ∕ (k + 1) \\ = \sum_{1 \leq k \leq n} \frac{1}{k + 1} H_{k} \\ = \sum_{1 \leq k \leq n} \frac{1}{k + 1} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = \sum_{1 \leq k \leq n} \sum_{1 \leq j \leq k} \frac{1}{k + 1} \frac{1}{j} \\ = \sum_{2 \leq k \leq n + 1} \sum_{1 \leq j \leq k - 1} \frac{1}{k} \frac{1}{j} \\ = \sum_{2 \leq k \leq n + 1} \frac{1}{k} (- \frac{1}{k} + \sum_{1 \leq j \leq k} \frac{1}{j}) \\ = - \sum_{2 \leq k \leq n + 1} \frac{1}{k} \frac{1}{k} + \sum_{2 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = - \sum_{2 \leq k \leq n + 1} \frac{1}{k^{2}} + \sum_{2 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = - (- 1 + \sum_{1 \leq k \leq n + 1} \frac{1}{k^{2}}) + \sum_{2 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = - (- 1 + H_{n + 1}^{(2)}) + \sum_{2 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = 1 - H_{n + 1}^{(2)} + \sum_{2 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = 1 - H_{n + 1}^{(2)} + \sum_{1 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} - \frac{1}{1} \sum_{1 \leq j \leq 1} \frac{1}{j} \\ = 1 - H_{n + 1}^{(2)} + \sum_{1 \leq k \leq n + 1} \frac{1}{k} \sum_{1 \leq j \leq k} \frac{1}{j} - 1 \\ = 1 - H_{n + 1}^{(2)} + \sum_{1 \leq k \leq n + 1} \frac{1}{k} H_{k} - 1 \\ = - H_{n + 1}^{(2)} + \frac{1}{2} (H_{n + 1}^{2} + H_{n + 1}^{(2)}) \\ = - H_{n + 1}^{(2)} + \frac{1}{2} H_{n + 1}^{2} + \frac{1}{2} H_{n + 1}^{(2)} \\ = - H_{n + 1}^{(2)} + \frac{1}{2} H_{n + 1}^{2} + \frac{1}{2} H_{n + 1}^{(2)} \\ = \frac{1}{2} H_{n + 1}^{2} - \frac{1}{2} H_{n + 1}^{(2)} \\ = \frac{1}{2} (H_{n + 1}^{2} - H_{n + 1}^{(2)}) . \end{array}

▸

15. [M23] Express

\sum_{k = 1}^{n} H_{k}^{2}

in terms of

n

and

H_{n}

The sum is

\begin{array}{l} \sum_{1 \leq k \leq n} H_{k}^{2} \\ = \sum_{1 \leq k \leq n} H_{k} H_{k} \\ = \sum_{1 \leq k \leq n} H_{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = \sum_{1 \leq k \leq n} \sum_{1 \leq j \leq k} H_{k} \frac{1}{j} \\ = \sum_{1 \leq j \leq n} \sum_{j \leq k \leq n} H_{k} \frac{1}{j} \\ = \sum_{1 \leq j \leq n} \frac{1}{j} \sum_{j \leq k \leq n} H_{k} \\ = \sum_{1 \leq j \leq n} \frac{1}{j} (\sum_{1 \leq k \leq n} H_{k} - \sum_{1 \leq k \leq j - 1} H_{k}) \\ = \sum_{1 \leq j \leq n} \frac{1}{j} (((n + 1) H_{n} - n) - ((j - 1 + 1) H_{j - 1} - (j - 1))) & from Eq. (8) \\ = \sum_{1 \leq j \leq n} \frac{1}{j} ((n + 1) H_{n} - n - j H_{j - 1} + j - 1) \\ = ((n + 1) H_{n} - n - 1) \sum_{1 \leq j \leq n} \frac{1}{j} - \sum_{1 \leq j \leq n} \frac{1}{j} j H_{j - 1} + \sum_{1 \leq j \leq n} \frac{1}{j} j \\ = ((n + 1) H_{n} - n - 1) H_{n} - \sum_{1 \leq j \leq n} H_{j - 1} + \sum_{1 \leq j \leq n} 1 \\ = (n + 1) H_{n}^{2} - n H_{n} - H_{n} - (\sum_{1 \leq j \leq n} H_{j} - H_{n}) + n \\ = (n + 1) H_{n}^{2} - n H_{n} - H_{n} - ((n + 1) H_{n} - n - H_{n}) + n \\ = (n + 1) H_{n}^{2} - n H_{n} - H_{n} - (n + 1) H_{n} + n + H_{n} + n \\ = (n + 1) H_{n}^{2} - n H_{n} - (n + 1) H_{n} + 2 n \\ = (n + 1) H_{n}^{2} - (2 n + 1) H_{n} + 2 n . \end{array}

16. [18] Express the sum

1 + \frac{1}{3} + \dots + \frac{1}{2 n - 1}

in terms of harmonic numbers.

The sum of all $n$ unit fractions with odd denominators through $2 n - 1$ may be expressed as

\begin{array}{l} \sum_{1 \leq k \leq n} \frac{1}{2 k - 1} & = \sum_{\begin{array}{c} 1 \leq k \leq 2 n - 1 \\ k odd \end{array}} \frac{1}{k} \\ = \sum_{1 \leq k \leq 2 n - 1} \frac{1}{k} - \sum_{\begin{array}{c} 1 \leq k \leq 2 n - 1 \\ k even \end{array}} \frac{1}{k} \\ = \sum_{1 \leq k \leq 2 n - 1} \frac{1}{k} - \sum_{1 \leq k \leq n - 1} \frac{1}{2 k} \\ = H_{2 n - 1} - \frac{1}{2} \sum_{1 \leq k \leq n - 1} \frac{1}{k} \\ = H_{2 n - 1} - \frac{1}{2} H_{n - 1} . \end{array}

17. [M24] (E. Waring, 1782.) Let

p

be an odd prime. Show that the numerator of

H_{p - 1}

is divisible by

p

Proposition. If $p$ is an odd prime, the numerator of $H_{p - 1}$ is divisible by $p$ .

Proof. Let $p$ be an arbitrary odd prime. We must show that the numerator of $H_{p - 1}$ is divisible by $p$ . That is, that

(p - 1)! H_{p - 1} = \sum_{1 \leq k \leq p - 1} \frac{(p - 1)!}{k} \equiv 0 (mod p) .

From exercise 1.2.4-19, the law of inverses, we may ﬁnd a $k^{'}$ such that

k k^{'} \equiv 1 (\mod p)

since $k ⊥ p$ . Note that $1 \leq k^{'} \leq p - 1$ and that each $k^{'}$ is unique such that ${k | 1 \leq k \leq p - 1} = {k^{'} | k k^{'} \equiv 1 (\mod p)}$ . Also note that since $p$ is an odd prime by hypothesis, $- \frac{(p - 1)}{2}$ is an integer. Then, from Wilson’s theorem

(p - 1)! \equiv - 1 (\mod p)

we have that

\begin{array}{l} \sum_{1 \leq k \leq p - 1} \frac{(p - 1)!}{k} & \equiv - \sum_{1 \leq k \leq p - 1} \frac{1}{k} \\ \equiv - \sum_{1 \leq k \leq p - 1} \frac{k k^{'}}{k} \\ \equiv - \sum_{1 \leq k \leq p - 1} k^{'} \\ \equiv - \sum_{1 \leq k \leq p - 1} k \\ \equiv - \frac{p (p - 1)}{2} \\ \equiv 0 (\mod p) \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

[Hardy and Wright, An Introduction to the Theory of Numbers, Section 7.8]

18. [M33] (J. Selfridge.) What is the highest power of 2 that divides the numerator of

1 + \frac{1}{3} + \dots + \frac{1}{2 n - 1}

We want to ﬁnd the highest power of 2 that divides the numerator of

\sum_{1 \leq k \leq n} \frac{1}{2 k - 1},

assuming $n$ positive.

Let $m$ be the integer such that $n = 2^{r} m$ for some integer $r$ . We know that $m$ exists and is odd, as it is the product of the odd primes from the prime factorization of $n$ .

We then have

\begin{array}{l} \sum_{1 \leq k \leq n} \frac{1}{2 k - 1} & = \sum_{1 \leq k \leq 2^{r} m} \frac{1}{2 k - 1} \\ = \sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1}, \end{array}

which we may prove by induction on $m$ .

If $m = 1$ ,

\sum_{1 \leq k \leq 2^{r}} \frac{1}{2 k - 1} = \sum_{1 \leq k \leq 2^{r}} \frac{1}{(0) 2^{r + 1} + 2 k - 1} = \sum_{0 \leq j \leq 0} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} .

Then, assuming

\sum_{1 \leq k \leq 2^{r} m} \frac{1}{2 k - 1} = \sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1},

we must show that

\sum_{1 \leq k \leq 2^{r} (m + 1)} \frac{1}{2 k - 1} = \sum_{0 \leq j \leq m} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} .

But

\begin{array}{l} \sum_{1 \leq k \leq 2^{r} (m + 1)} \frac{1}{2 k - 1} & = \sum_{1 \leq k \leq 2^{r} m} \frac{1}{2 k - 1} + \sum_{2^{r} m + 1 \leq k \leq 2^{r} (m + 1)} \frac{1}{2 k - 1} \\ = \sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} + \sum_{2^{r} m + 1 \leq k \leq 2^{r} (m + 1)} \frac{1}{2 k - 1} \\ = \sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} + \sum_{1 \leq k - 2^{r} m \leq 2^{r}} \frac{1}{2 k - 1} \\ = \sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} + \sum_{1 \leq k \leq 2^{r}} \frac{1}{2 (k + 2^{r} m) - 1} \\ = \sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} + \sum_{1 \leq k \leq 2^{r}} \frac{1}{m 2^{r + 1} m + 2 k - 1} \\ = \sum_{1 \leq k \leq 2^{r} m} \frac{1}{2 k - 1} \end{array}

and hence the identity.

Let

P_{j} = \prod_{1 \leq k \leq 2^{r}} j 2^{r + 1} + 2 k - 1

be the common denominator such that

\sum_{1 \leq k \leq 2^{r}} \frac{1}{j 2^{r + 1} + 2 k - 1} = \sum_{1 \leq k \leq 2^{r}} \frac{P_{j}}{P_{j} (j 2^{r + 1} + 2 k - 1)} = \sum_{1 \leq k \leq 2^{r}} \frac{P_{j} ∕ (j 2^{r + 1} + 2 k - 1)}{P_{j}} .

That is, such that the numerator of $\sum_{1 \leq k \leq n} \frac{1}{2 k - 1}$ is

\sum_{0 \leq j \leq m - 1} \sum_{1 \leq k \leq 2^{r}} \frac{P_{j}}{j 2^{r + 1} + 2 k - 1},

$m$ sets of $2^{r}$ terms, each of the form $P_{j}$ over a distinct odd residue of $2^{r + 1}$ . Each ratio itself is an integer and a distinct odd residue of $2^{r + 1}$ , and the sum of $2^{r}$ distinct odd residues is $2^{r^{2}} m_{j} = 2^{2 r} m_{j}$ for some integer $m_{j}$ by the odd number theorem, $m_{j}$ odd. That is, the numerator of $\sum_{1 \leq k \leq n} \frac{1}{2 k - 1}$ is

\sum_{0 \leq j \leq m - 1} 2^{2 r} m_{j} = 2^{2 r} \sum_{0 \leq j \leq m - 1} m_{j} .

Since $m$ is odd, we know the sum of $m$ odd terms $m_{j}$ is itself an odd number. Let this be $M$ , so that the numerator of $\sum_{1 \leq k \leq n} \frac{1}{2 k - 1}$ is

2^{2 r} M

for some odd integer $M$ . That is, $2^{2 r}$ is the highest power of 2 that divides the numerator of

\sum_{1 \leq k \leq n} \frac{1}{2 k - 1}

where $m$ is the odd integer such that $n = 2^{r} m$ for some integer $r$ .

________________________________________________________________________________

[AMM 67 (1960), 924–925]

▸

19. [M30] List all nonnegative integers

n

for which

H_{n}

is an integer. [Hint: If

H_{n}

has odd numerator and even denominator, it cannot be an integer.]

The nonnegative integers $n$ for which $H_{n}$ is an integer are $n = 0$ and $n = 1$ , since $H_{0} = 0$ and $H_{1} = 1$ . To see why these are the only $n$ , consider the following. Let $k = ⌊ \lg n ⌋$ with $n \geq 2$ , so that $2^{k} \leq n < 2^{k + 1}$ and $k \geq 1$ , and let

P = \prod_{1 \leq i \leq n} 2^{k} m

be the common denominator for each term of $H_{n}$ , $m$ odd but $P$ even. We know that $m$ exists and is odd, as it is the product of the odd primes from a prime factorization of the common denominator. Then

\begin{array}{l} H_{n} & = \sum_{1 \leq j \leq n} \frac{1}{j} \\ = \sum_{1 \leq j \leq n} \frac{P}{P j} \\ = \sum_{1 \leq j \leq n} \frac{P ∕ j}{P} \\ = \sum_{1 \leq j \leq n} P ∕ j / P . \end{array}

If $H_{n}$ is an integer, then so is $H_{n} - 1$ . But

H_{n} - 1 = \sum_{2 \leq j \leq n} P ∕ j / P = \frac{M}{P}

for $M = \sum_{2 \leq j \leq n} P ∕ j$ . Each term in $M$ is even except for the term with $j = 2^{k}$ , $P ∕ 2^{k} = m$ , which means $M$ is odd. But the divisor $P$ is even. This means their ratio cannot possibly be an integer, and hence the claim.

20. [HM22] There is an analytic way to approach summation problems such as the one leading to Theorem A in this section: If

f (x) = \sum_{k \geq 0} a_{k} x^{k}

, and this series converges for

x = x_{0}

, prove that

Proposition. If $f (x) = \sum_{k \geq 0} a_{k} x^{k}$ and $f (x)$ converges for $x = x_{0}$ then $\sum_{k \geq 0} a_{k} x_{0}^{k} H_{k} = \int_{0}^{1} \frac{f (x_{0}) - f (x_{0} y)}{1 - y} d y$ .

Proof. Let $f (x) = \sum_{k \geq 0} a_{k} x^{k}$ be a series with arbitrary coeﬃcients $a_{k}$ such that $f (x)$ converges for $x = x_{0}$ . We must show that

\sum_{k \geq 0} a_{k} x_{0}^{k} H_{k} = \int_{0}^{1} \frac{f (x_{0}) - f (x_{0} y)}{1 - y} d y .

But

\begin{array}{l} \sum_{k \geq 0} a_{k} x_{0}^{k} H_{k} & = \sum_{k \geq 0} a_{k} x_{0}^{k} \sum_{1 \leq j \leq k} \frac{1}{j} \\ = \sum_{k \geq 0} a_{k} x_{0}^{k} \sum_{1 \leq j \leq k} \int_{0}^{1} y^{j - 1} d y \\ = \sum_{k \geq 0} a_{k} x_{0}^{k} \int_{0}^{1} \sum_{1 \leq j \leq k} y^{j - 1} d y \\ = \sum_{k \geq 0} a_{k} x_{0}^{k} \int_{0}^{1} \sum_{0 \leq j \leq k - 1} y^{j} d y \\ = \sum_{k \geq 0} a_{k} x_{0}^{k} \int_{0}^{1} \frac{y^{0} - y^{k - 1 + 1}}{1 - y} d y \\ = \sum_{k \geq 0} a_{k} x_{0}^{k} \int_{0}^{1} \frac{1 - y^{k}}{1 - y} d y \\ = \int_{0}^{1} \frac{1}{1 - y} \sum_{k \geq 0} (a_{k} x_{0}^{k} - a_{k} x_{0}^{k} y^{k}) d y \\ = \int_{0}^{1} \frac{1}{1 - y} (\sum_{k \geq 0} a_{k} x_{0}^{k} - \sum_{k \geq 0} a_{k} {(x_{0} y)}^{k}) d y \\ = \int_{0}^{1} \frac{1}{1 - y} (f (x_{0}) - f (x_{0} y)) d y \\ = \int_{0}^{1} \frac{f (x_{0}) - f (x_{0} y)}{1 - y} d y \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

[AMM 69 (1962), 239; H. W. Gould, Mathematics Magazine 34 (1961), 317–321]

The diﬀerence between the sum for $n$ and $n + 1$ is given as

\begin{array}{l} \sum_{1 \leq k \leq n + 1} \frac{H_{k}}{n + 2 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = \frac{H_{n + 1}}{n + 2 - (n + 1)} + \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 2 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = H_{n + 1} + \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 2 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = H_{n + 1} + \sum_{1 \leq k \leq n} (\frac{H_{k}}{n + 2 - k} - \frac{H_{k}}{n + 1 - k}) \\ = H_{n + 1} + \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 2 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = H_{n + 1} + \sum_{0 \leq k \leq n - 1} \frac{H_{k + 1}}{n + 1 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = H_{n + 1} + \frac{H_{1}}{n + 1} - H_{n + 1} + \sum_{1 \leq k \leq n} \frac{H_{k + 1}}{n + 1 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = \frac{1}{n + 1} + \sum_{1 \leq k \leq n} \frac{H_{k + 1}}{n + 1 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = \frac{1}{n + 1} + \sum_{1 \leq k \leq n} \frac{H_{k} + \frac{1}{k + 1}}{n + 1 - k} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = \frac{1}{n + 1} + \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} + \sum_{1 \leq k \leq n} \frac{1}{(k + 1) (n + 1 - k)} - \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} \\ = \frac{1}{n + 1} + \sum_{1 \leq k \leq n} \frac{1}{(k + 1) (n + 1 - k)} \\ = \frac{1}{n + 1} + \sum_{1 \leq k \leq n} (\frac{1}{(n + 2) (k + 1)} + \frac{1}{(n + 2) (n + 1 - k)}) \\ = \frac{1}{n + 1} + \frac{1}{n + 2} \sum_{1 \leq k \leq n} (\frac{1}{k + 1} + \frac{1}{n + 1 - k}) \\ = \frac{1}{n + 1} + \frac{1}{n + 2} \sum_{1 \leq k \leq n} \frac{1}{k + 1} + \frac{1}{n + 2} \sum_{1 \leq k \leq n} \frac{1}{n + 1 - k} \\ = \frac{1}{n + 1} + \frac{1}{n + 2} \sum_{2 \leq k \leq n + 1} \frac{1}{k} + \frac{1}{n + 2} \sum_{1 \leq k \leq n} \frac{1}{k} \\ = \frac{1}{n + 1} + \frac{1}{n + 2} (- \frac{1}{1} + \frac{1}{n + 1} + \sum_{1 \leq k \leq n} \frac{1}{k}) + \frac{H_{n}}{n + 2} \\ = \frac{1}{n + 1} + \frac{1}{n + 2} (- \frac{1}{1} + \frac{1}{n + 1} + H_{n}) + \frac{H_{n}}{n + 2} \\ = \frac{1}{n + 1} + \frac{1}{(n + 1) (n + 2)} + \frac{H_{n} - 1}{n + 2} + \frac{H_{n}}{n + 2} \\ = \frac{1}{n + 1} + \frac{H_{n}}{n + 2} - \frac{1}{n + 2} + \frac{H_{n + 1}}{n + 2} \\ = \frac{1}{(n + 1) (n + 2)} + \frac{H_{n}}{n + 2} + \frac{H_{n + 1}}{n + 2} \\ = \frac{H_{n + 1}}{n + 2} + \frac{H_{n + 1}}{n + 2} \\ = 2 \frac{H_{n + 1}}{n + 2} . \end{array}

Then, in the case that $n = 1$

\sum_{1 \leq k \leq 1} \frac{H_{k}}{1 + 1 - k} = \frac{H_{k}}{1 + 1 - k} = H_{1} = 1 = \frac{9}{4} - \frac{5}{4} = {(1 + \frac{1}{2})}^{2} - (1 + \frac{1}{2^{2}}) = H_{2}^{2} - H_{2}^{(2)}

and assuming

\sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} = H_{n + 1}^{2} - H_{n + 1}^{(2)}

it may be shown that

\sum_{1 \leq k \leq n + 1} \frac{H_{k}}{n + 2 - k} = H_{n + 2}^{2} - H_{n + 2}^{(2)}

\begin{array}{l} \sum_{1 \leq k \leq n + 1} \frac{H_{k}}{n + 2 - k} \\ = \sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} + 2 \frac{H_{n + 1}}{n + 2} \\ = H_{n + 1}^{2} - H_{n + 1}^{(2)} + 2 \frac{H_{n + 1}}{n + 2} \\ = H_{n + 1}^{2} + 2 \frac{H_{n + 1}}{n + 2} + \frac{1}{{(n + 2)}^{2}} - H_{n + 1}^{(2)} - \frac{1}{{(n + 2)}^{2}} \\ = {(H_{n + 1} + \frac{1}{n + 2})}^{2} - (H_{n + 1}^{(2)} + \frac{1}{{(n + 2)}^{2}}) \\ = H_{n + 2}^{2} - H_{n + 2}^{(2)} . \end{array}

That is

\sum_{1 \leq k \leq n} \frac{H_{k}}{n + 1 - k} = H_{n + 1}^{2} - H_{n + 1}^{(2)} .

From summation by parts and exercise 21,

\begin{array}{l} \sum_{0 \leq k \leq n} H_{k} H_{n - k} \\ = \sum_{1 \leq k \leq n} H_{k} H_{n - k} \\ = (\sum_{1 \leq j \leq n} H_{j}) H_{n - n} - \sum_{1 \leq k \leq n} (\sum_{1 \leq j \leq k} H_{j}) (H_{n - (k + 1)} - H_{n - k}) \\ = ((n + 1) H_{n} - n) H_{0} + \sum_{1 \leq k \leq n - 1} ((k + 1) H_{k} - k) \frac{1}{n - k} \\ = \sum_{1 \leq k \leq n - 1} \frac{(k + 1) H_{k} - k}{n - k} \\ = \sum_{1 \leq k \leq n - 1} \frac{(n - k + 1) H_{n - k} - n + k}{k} \\ = \sum_{1 \leq k \leq n - 1} \frac{n H_{n - k} - k H_{n - k} + H_{n - k} - n + k}{k} \\ = \sum_{1 \leq k \leq n - 1} \frac{n H_{n - k}}{k} - \sum_{1 \leq k \leq n - 1} \frac{k H_{n - k}}{k} + \sum_{1 \leq k \leq n - 1} \frac{H_{n - k}}{k} - \sum_{1 \leq k \leq n - 1} \frac{n}{k} + \sum_{1 \leq k \leq n - 1} \frac{k}{k} \\ = n \sum_{1 \leq k \leq n - 1} \frac{H_{n - k}}{k} - \sum_{1 \leq k \leq n - 1} H_{n - k} + \sum_{1 \leq k \leq n - 1} \frac{H_{n - k}}{k} - n \sum_{1 \leq k \leq n - 1} \frac{1}{k} + \sum_{1 \leq k \leq n - 1} 1 \\ = n \sum_{1 \leq k \leq n - 1} \frac{H_{n - k}}{k} - \sum_{1 \leq k \leq n - 1} H_{n - k} + \sum_{1 \leq k \leq n - 1} \frac{H_{n - k}}{k} - n H_{n - 1} + n - 1 \\ = n \sum_{1 \leq k \leq n - 1} \frac{H_{k}}{n - k} - \sum_{1 \leq k \leq n - 1} H_{k} + \sum_{1 \leq k \leq n - 1} \frac{H_{k}}{n - k} - n (H_{n} - 1) \\ = (n + 1) \sum_{1 \leq k \leq n - 1} \frac{H_{k}}{n - k} - (((n - 1) + 1) H_{n - 1} - (n - 1)) - n (H_{n} - 1) \\ = (n + 1) \sum_{1 \leq k \leq n - 1} \frac{H_{k}}{n - k} - n H_{n - 1} + n - 1 - n (H_{n} - 1) \\ = (n + 1) \sum_{1 \leq k \leq n - 1} \frac{H_{k}}{n - k} - n (H_{n} - 1) - n (H_{n} - 1) \\ = (n + 1) \sum_{1 \leq k \leq n - 1} \frac{H_{k}}{n - k} - 2 n (H_{n} - 1) \\ = (n + 1) (H_{n}^{2} - H_{n}^{(2)}) - 2 n (H_{n} - 1) . \end{array}

▸

23. [HM20] By considering the function

Γ^{'} (x) ∕ Γ (x)

, show how we can get a natural generalization of

H_{n}

to noninteger values of

n

. You may use the fact that

Γ^{'} (1) = - γ

, anticipating the next exercise.

We can get a natural generalization of $H_{n}$ to noninteger values of $n$ by considering the function $Γ^{'} (x) ∕ Γ (x)$ , using the fact that $Γ^{'} (1) = - γ$ .

By deﬁnition,

Γ (x + 1) = x Γ (x),

and so

\begin{array}{l} Γ^{'} (x + 1) & = {(x Γ (x))}^{'} \\ = x^{'} Γ (x) + x Γ^{'} (x) \\ = Γ (x) + x Γ^{'} (x) \end{array}

if and only if

\begin{array}{l} \frac{Γ^{'} (x + 1)}{Γ (x + 1)} & = \frac{Γ (x) + x Γ^{'} (x)}{Γ (x + 1)} \\ = \frac{Γ (x) + x Γ^{'} (x)}{x Γ (x)} \\ = \frac{Γ (x)}{x Γ (x)} + \frac{x Γ^{'} (x)}{x Γ (x)} \\ = \frac{1}{x} + \frac{Γ^{'} (x)}{Γ (x)}, \end{array}

giving us a natural generalization of $H_{n}$ to noninteger values of $n$ as

H_{x} = \frac{Γ^{'} (x + 1)}{Γ (x + 1)} + γ .

Note that in the case that $x = 0$

H_{0} = \frac{Γ^{'} (1)}{Γ (1)} + γ = \frac{- γ}{1} + γ = 0,

and assuming

H_{x} = \frac{Γ^{'} (x + 1)}{Γ (x + 1)} + γ

we have that

\begin{array}{l} H_{x + 1} & = H_{x} + \frac{1}{x + 1} \\ = \frac{Γ^{'} (x + 1)}{Γ (x + 1)} + γ + \frac{1}{x + 1} \\ = \frac{Γ^{'} (x + 1)}{Γ (x + 1)} + \frac{1}{x + 1} γ \\ = \frac{Γ^{'} (x + 2)}{Γ (x + 2)} + γ, \end{array}

proving the identity holds for all nonnegative integers $x$ .

Proposition. $x e^{γ x} \prod_{k \geq 1} ((1 + \frac{x}{k}) e^{- x ∕ k}) = \frac{1}{Γ (x)}$ .

Proof. Let $x$ be an arbitrary real. We must show that

x e^{γ x} \prod_{k \geq 1} ((1 + \frac{x}{k}) e^{- x ∕ k}) = \frac{1}{Γ (x)} .

But since

γ = \lim_{n \to \infty} (H_{n} - \ln n)

we have that

\begin{array}{l} x e^{γ x} \prod_{k \geq 1} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = x e^{γ x} \lim_{n \to \infty} \prod_{1 \leq k \leq n} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = \lim_{n \to \infty} x e^{γ x} \prod_{1 \leq k \leq n} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = \lim_{n \to \infty} x e^{(H_{n} - \ln n) x} \prod_{1 \leq k \leq n} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = \lim_{n \to \infty} x \frac{e^{x H_{n}}}{e^{x \ln n}} \prod_{1 \leq k \leq n} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = \lim_{n \to \infty} x \frac{e^{x H_{n}}}{n^{x}} \prod_{1 \leq k \leq n} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = \lim_{n \to \infty} \frac{x}{n^{x}} e^{x H_{n}} \prod_{1 \leq k \leq n} ((1 + \frac{x}{k}) e^{- x ∕ k}) \\ = \lim_{n \to \infty} \frac{x}{n^{x}} e^{x H_{n}} (\prod_{1 \leq k \leq n} (1 + \frac{x}{k})) (\prod_{1 \leq k \leq n} e^{- x ∕ k}) \\ = \lim_{n \to \infty} \frac{x}{n^{x}} e^{x H_{n}} (\prod_{1 \leq k \leq n} (1 + \frac{x}{k})) e^{- x \sum_{1 \leq k \leq n} 1 ∕ k} \\ = \lim_{n \to \infty} \frac{x}{n^{x}} e^{x H_{n}} (\prod_{1 \leq k \leq n} (1 + \frac{x}{k})) e^{- x H_{n}} \\ = \lim_{n \to \infty} \frac{x}{n^{x}} \prod_{1 \leq k \leq n} (1 + \frac{x}{k}) \\ = \lim_{n \to \infty} \frac{x}{n^{x}} \prod_{1 \leq k \leq n} \frac{x + k}{k} \\ = \lim_{n \to \infty} \frac{x}{n^{x}} \frac{\prod_{1 \leq k \leq n} (x + k)}{\prod_{1 \leq k \leq n} k} \\ = \lim_{n \to \infty} \frac{x}{n^{x}} \frac{\prod_{1 \leq k \leq n} (x + k)}{n!} \\ = \lim_{n \to \infty} \frac{x \prod_{1 \leq k \leq n} (x + k)}{n^{x} n!} \\ = \frac{1}{Γ (x)} \end{array}

as we needed to show. □