Showing $\sum_{k=1}^{nm} \frac{1}{k} \approx \sum_{k=1}^{n} \frac{1}{k} + \sum_{k=1}^{m} \frac{1}{k}$

This is a nice little problem, and thankfully it has a simple solution.

Assume that $m$ and $n$ are large natural numbers. Consider the following inequalities:

$$ \sum_{k=cn+1}^{(c+1)n}\frac{1}{(c+1)n}\leq\sum_{k=cn+1}^{(c+1)n}\frac{1}{k} \leq\sum_{k=cn+1}^{(c+1)n}\frac{1}{cn+1} $$ This means that we may estimate the middle sum with the lower sum with an error no greater than the following (using the fact that $n$ is large): $$ \sum_{k=cn+1}^{(c+1)n}\frac{n-1}{(c+1)n(nc+1)} \approx \sum_{k=cn+1}^{(c+1)n}\frac{1}{c(c+1)n} = \frac{1}{c(c+1)} $$ Thus we have the following approximate upper bound (using the fact that $m$ is large): $$ \sum_{k=1}^{nm}\frac{1}{k} = \sum_{k=1}^{n}\frac{1}{k} + \sum_{c=1}^{m-1}\sum_{k=cn+1}^{(c+1)n}\frac{1}{k} \lesssim\sum_{k=1}^n\frac{1}{k}+ \sum_{c=1}^{m-1}\left[\frac{1}{c+1}+\frac{1}{c(c+1)}\right]\approx\sum_{k=1}^n\frac{1}{k}+\sum_{k=1}^m\frac{1}{k} $$ And we have the following lower bound: $$ \sum_{k=1}^{nm}\frac{1}{k} = \sum_{k=1}^{n}\frac{1}{k} + \sum_{c=1}^{m-1}\sum_{k=cn+1}^{(c+1)n}\frac{1}{k} \geq\sum_{k=1}^n\frac{1}{k}+ \sum_{c=1}^{m-1}\frac{1}{c+1} =\left[\sum_{k=1}^n\frac{1}{k}+\sum_{k=1}^m\frac{1}{k}\right]-1 $$

Let $$S = \sum_{k=1}^n \frac{1}k + \sum_{k=1}^m \frac{1}k.$$ Note that we can write $\sum_{k=1}^{nm} \frac{1}k$ as $$\begin{align*} 1 + \cdots + \frac{1}n \\ \frac1{n+1} + \cdots + \frac{1}{2n} \\ \cdots \\ \frac{1}{n(m-1)} + \cdots + \frac{1}{nm} \end{align*} $$ Label the rows of the above table from $1$ upto $m$. Note that all the numbers in the $j$th row are $\ge \frac{1}{jn}$ so the sum of the numbers in the $j$th row is at least $n \cdot \frac{1}{jn} = \frac{1}j$. Summing this from $j=2$ to $m$ gives us $$ \sum_{k=1}^{nm} \frac{1}k \ge \left(\sum_{k=1}^n \frac{1}k + \sum_{j=1}^m \frac{1}j \right) - 1 = S-1.$$ Similarly, each entry in the $j$th row is at most $\frac{1}{(j-1)n}$ so summing from $j=2$ to $m$ gives $$ \sum_{k=1}^{nm} \frac{1}k \le \left(\sum_{k=1}^n \frac{1}k + \sum_{j=1}^m \frac{1}j \right) - \frac{1}m = S-\frac{1}m.$$ Therefore, $$ \frac{1}m \le \sum_{k=1}^n \frac{1}k + \sum_{k=1}^m \frac{1}k - \sum_{k=1}^{nm} \frac{1}k \le 1. $$

Avoiding $\log$s we still have $H_N=\sum_{k=1}^{N}\frac{1}{k}=\int_{0}^{1}\frac{x^N-1}{x-1}$ and

$$ H_{NM}-H_{N}-H_{M} = \int_{0}^{1}\frac{(x^N-1)(x^M-1)}{x-1}\,dx\leq 0, $$ whose absolute value can be bounded (due to the Cauchy-Schwarz inequality) by $$ \sqrt{\int_{0}^{1}\frac{(1-x^N)^2}{1-x}\,dx \int_{0}^{1}\frac{(1-x^M)^2}{1-x}\,dx}=\sqrt{(2H_N-H_{2N})(2H_M-H_{2M})}. $$ On the other hand $$ H_{2N}-H_N = \sum_{k=1}^{2N}\frac{(-1)^{k+1}}{k} $$ is a partial sum for a convergent (to $\log 2$) series, hence $$ H_N+H_M-\sqrt{H_N H_M}\leq H_{NM} \leq H_N+H_M $$ holds for any large $N,M$.