TAOCP 1.2.7 Exercise 7

Let T(m,n) = H_m + H_n - H_{mn}, where $m,n > 0$ and $H_k = \sum_{i=1}^{k} \frac{1}{i}$ is the $k$-th harmonic number.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.7: Harmonic Numbers

Exercise 7. [M21] Let $T(m,n)=H_m+H_n-H_{mn}$. Show that when $m$ or $n$ increases, $T(m,n)$ never increases (assuming that $m$ and $n$ are positive). Compute the minimum and maximum values of $T(m,n)$ for $m,n>0$.

Verified: no
Solve time: -

Solution

Let

$$ T(m,n) = H_m + H_n - H_{mn}, $$

where $m,n > 0$ and $H_k = \sum_{i=1}^{k} \frac{1}{i}$ is the $k$-th harmonic number. We first show that $T(m,n)$ is nonincreasing in each argument.

Suppose $m$ increases by 1. Then

$$ T(m+1,n) - T(m,n) = (H_{m+1}-H_m) - (H_{(m+1)n}-H_{mn}). $$

By the definition of $H_k$, we have $H_{m+1}-H_m = \frac{1}{m+1}$ and $H_{(m+1)n}-H_{mn} = \sum_{i=mn+1}^{(m+1)n} \frac{1}{i}$. Since each term in this sum satisfies

$$ \frac{1}{i} \le \frac{1}{mn+1} \le \frac{1}{m+1}, $$

and there are $n \ge 1$ terms, we have

$$ \sum_{i=mn+1}^{(m+1)n} \frac{1}{i} \ge \frac{n}{(m+1)n} = \frac{1}{m+1}. $$

Hence

$$ T(m+1,n) - T(m,n) = \frac{1}{m+1} - \sum_{i=mn+1}^{(m+1)n} \frac{1}{i} \le 0. $$

A symmetric argument applies when $n$ increases, so $T(m,n)$ is nonincreasing in each argument.

To compute the maximum of $T(m,n)$, observe that $T(m,n)$ decreases as $m$ or $n$ increases, so the maximum occurs at the smallest positive integers, $m=n=1$:

$$ T(1,1) = H_1 + H_1 - H_{1\cdot 1} = 1 + 1 - 1 = 1. $$

To compute the minimum, consider letting $m$ or $n$ grow without bound. Since $H_k$ diverges logarithmically, we have

$$ T(m,n) = H_m + H_n - H_{mn} \sim \ln m + \ln n - \ln(mn) = 0 $$

as $m$ or $n \to \infty$. To justify this rigorously, note that $H_k = \ln k + \gamma + \epsilon_k$ with $0 < \epsilon_k < 1/k$ by Theorem A (or by Section 1.2.7). Then

$$ T(m,n) = (\ln m + \gamma + \epsilon_m) + (\ln n + \gamma + \epsilon_n) - (\ln(mn) + \gamma + \epsilon_{mn}) = \gamma + (\epsilon_m + \epsilon_n - \epsilon_{mn}) \to 0 $$

as $m,n \to \infty$, because $\epsilon_m, \epsilon_n, \epsilon_{mn} \to 0$. Hence the minimum value of $T(m,n)$ is

$$ \boxed{0}. $$

In summary, $T(m,n)$ is nonincreasing in each argument, attains its maximum at $m=n=1$ with value

$$ \boxed{1}, $$

and its infimum (minimum in the limit) is

$$ \boxed{0}. $$

This completes the proof.

∎