Showing $\sum_{k=1}^{nm} \frac{1}{k} \approx \sum_{k=1}^{n} \frac{1}{k} + \sum_{k=1}^{m} \frac{1}{k}$ Since $\log(nm) = \log(n) + \log(m)$, and $\sum_{k=1}^n \frac{1}{k} \approx \log n$ for large $n$, we would expect that $$\sum_{k=1}^{nm} \frac{1}{k} \approx \sum_{k=1}^{n} \frac{1}{k} + \sum_{k=1}^{m} \frac{1}{k}$$
when $n,m$ are large. 
I'm wondering if this approximation can be demonstrated through discrete means. That is to say, manipulations of rational fractions and/or elementary number-theoretical considerations, without using the $\log n$ approximation.  
 A: 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
$$
A: 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. $$
A: 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$.
A: Be the sucession $\{c_n\}_{n\in\mathbb{N}}$ as:
\begin{equation}
c_n = \sum_{k=1}^n \left(\frac{1}{k}\right) - \ln(n)
\end{equation}
We can notice that:
\begin{eqnarray*}
c_{n+1}-c_n &=& \left[\sum_{k=1}^{n+1} \left(\frac{1}{k}\right) - \ln(n+1)\right]
             -\left[\sum_{k=1}^{n} \left(\frac{1}{k}\right) - \ln(n)\right]  \\
c_{n+1}-c_n &=& \frac{1}{n+1} -       \ln(n+1) + \ln(n)  \\
c_{n+1}-c_n &=& \frac{1}{n+1} - \left[\ln(n+1) - \ln(n)\right]  \\
c_{n+1}-c_n &=& \frac{1}{n+1} - \int_{n}^{n+1} \frac{1}{x} dx  \\
\end{eqnarray*}
But if we graph $\displaystyle y = \frac{1}{x}$ and we draw rectangles as in the figure:

We notice that the area of the rectangle between $x=n$ and $x=n+1$ is $\displaystyle\frac{1}{n+1}$ and it is less than $\displaystyle\int_{n}^{n+1} \frac{1}{x} dx$. Then $\forall n\in \mathbb{N}$:
\begin{equation}
c_{n+1}-c_n = \frac{1}{n+1} - \int_{n}^{n+1} \frac{1}{x} dx < 0
\end{equation}
Thus, the sucession $\{c_n\}_{n\in\mathbb{N}}$ is monotonically decreasing and $c_{n+1} < c_n < \cdots < c_2 < c_1 = 1$, then $\lim_{n\to\infty}c_n=\gamma$ exists and it is less than 1, it should be noted that $\lim_{n\to\infty}c_n$ is the Euler-Mascheroni constant $\gamma$.
Be the sucession $\left\lbrace b_n \right\rbrace_{n\in\mathbb{N}}$ such that $b_n=nm$ with $m\in\mathbb{N}$, the sucession $c_n$ and its subsucession $c_{b_n}$ converge to the same number:
\begin{eqnarray}
\lim_{n\to\infty}c_{b_n} &=& \lim_{n\to\infty}c_n  \\
\lim_{n\to\infty}\sum_{k=1}^{nm} \left(\frac{1}{k}\right) - \ln(nm) &=& \lim_{n\to\infty}\sum_{k=1}^n \left(\frac{1}{k}\right) - \ln(n)  \\
\lim_{n\to\infty}\sum_{k=1}^{nm} \left(\frac{1}{k}\right) - \ln(n) - \ln(m) &=& \lim_{n\to\infty}\sum_{k=1}^n \left(\frac{1}{k}\right) - \ln(n)  \\
\lim_{n\to\infty}\sum_{k=1}^{nm} \left(\frac{1}{k}\right) -\sum_{k=1}^n \left(\frac{1}{k}\right) &=& \ln(m)  \\
\lim_{n\to\infty}\sum_{k=1}^{nm} \left(\frac{1}{k}\right) -\sum_{k=1}^n \left(\frac{1}{k}\right) -\sum_{k=1}^{m} \left(\frac{1}{k}\right) &=& \ln(m) -\sum_{k=1}^{m} \left(\frac{1}{k}\right) \\
\lim_{m\to\infty}\lim_{n\to\infty}\sum_{k=1}^{nm} \left(\frac{1}{k}\right) -\sum_{k=1}^n \left(\frac{1}{k}\right) -\sum_{k=1}^{m} \left(\frac{1}{k}\right)
&=&
\lim_{m\to\infty}\ln(m) -\sum_{k=1}^{m} \left(\frac{1}{k}\right)  \\
\lim_{m\to\infty}\lim_{n\to\infty}\sum_{k=1}^{nm} \left(\frac{1}{k}\right) -\sum_{k=1}^n \left(\frac{1}{k}\right) -\sum_{k=1}^{m} \left(\frac{1}{k}\right)
&=&
\gamma < 1
\end{eqnarray}
Then for $n,m$ very big:
\begin{eqnarray}
\sum_{k=1}^{nm} \left(\frac{1}{k}\right) -\sum_{k=1}^n \left(\frac{1}{k}\right) -\sum_{k=1}^{m} \left(\frac{1}{k}\right) &\approx& \gamma  \\
\sum_{k=1}^{nm} \left(\frac{1}{k}\right) &\approx& \gamma + \sum_{k=1}^n \left(\frac{1}{k}\right) + \sum_{k=1}^{m} \left(\frac{1}{k}\right) \\
\sum_{k=1}^{nm} \left(\frac{1}{k}\right) &\approx& \sum_{k=1}^n \left(\frac{1}{k}\right) + \sum_{k=1}^{m} \left(\frac{1}{k}\right)
\end{eqnarray}
Because $\displaystyle \gamma << \sum_{k=1}^n \left(\frac{1}{k}\right) + \sum_{k=1}^{m} \left(\frac{1}{k}\right)$.
Part of this demonstration is from the book "Euler: The master of us all" [1].

References:
Dunham, William, Euler: The master of us all, The Dolciani Mathematical Expositions. 22. Washington, DC: The Mathematical Association of America. xxviii, 185 p. (1999). ZBL0951.01012.
