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

Question

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.

Answer 1

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 $$

Answer 2

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. $$

Answer 3

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.

Answer 4

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$.