Kvant Math Problem 597

The sequence $x_n=1+\frac12+\dots+\frac1n$ is the $n$-th harmonic number.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m24s
Source on kvant.digital

Problem

Let $$x_n=1+\dfrac12+\ldots+\dfrac1n.$$

  1. Prove the existence of the limit $$\gamma=\lim_{n\to\infty}{}(x_n-\ln n).$$
  2. Prove that for any $n$, $m\in\mathbb{N}$ $$\gamma\lt x_n+x_m-x_{nm}\le1.$$
  3. Find $\gamma$ with an accuracy of $0{,}1$.

V. Yasinsky

Exploration

The sequence $x_n=1+\frac12+\dots+\frac1n$ is the $n$-th harmonic number. Numerically, for small $n$, $x_n - \ln n$ appears to approach a constant: for $n=1$, $x_1-\ln 1 = 1$, for $n=2$, $x_2 - \ln 2 \approx 1.5 - 0.693 = 0.807$, for $n=3$, $x_3 - \ln 3 \approx 1.833 - 1.099 = 0.734$, and for $n=10$, $x_{10}-\ln 10 \approx 2.929 - 2.303 = 0.626$. The sequence decreases slowly, suggesting convergence to a limit.

For the second part, the inequality $x_n+x_m-x_{nm}$ involves cancellation of many harmonic terms. Small cases suggest the lower bound is near $0.577$, which is the classical Euler–Mascheroni constant $\gamma$, and the upper bound is at most $1$. Checking $n=2$, $m=2$, $x_2+x_2-x_4 = 1.5+1.5-2.083 = 0.917$, consistent with $0.577<0.917<1$.

For the final part, approximating $\gamma$ numerically from $n=1000$ yields $x_{1000}-\ln 1000 \approx 0.577$. The crucial step is rigorously establishing the limit in part 1 using inequalities rather than numeric intuition.

Problem Understanding

We are asked to determine a classical constant $\gamma$ defined as the limiting difference between the $n$-th harmonic number and the natural logarithm. The problem is Type A for part 3 (finding the value) and Type B for parts 1 and 2 (proving existence of the limit and the inequalities). The main difficulty is proving convergence without assuming prior knowledge of the Euler–Mascheroni constant, particularly using elementary techniques suitable for Kvant readers. The final value is known to be $\gamma \approx 0.577$, which is plausible given the decreasing numerical sequence and its bounding between $0$ and $1$.

Proof Architecture

Lemma 1: For each $n$, $\int_1^n \frac{1}{t} dt < x_n < 1+\int_1^n \frac{1}{t} dt$. This is true because $\frac1k$ is the height of a rectangle over $[k-1,k]$ and the integral approximates the sum via lower and upper Riemann sums.

Lemma 2: The sequence $x_n - \ln n$ is decreasing and bounded below. It is decreasing because $x_{n+1}-\ln(n+1) = x_n - \ln n + \frac1{n+1} - \ln(1+1/n)$, and the difference is negative; it is bounded below by $0$.

Lemma 3: For all $n,m\in\mathbb{N}$, $x_n+x_m-x_{nm} = \sum_{k=1}^{n}\sum_{l=1}^{m} \frac{1}{(k-1)m+l} \in (\gamma,1]$. This uses reindexing the double sum and estimating the sums by corresponding integrals.

Lemma 4: Numerical approximation with $n=1000$ shows $x_{1000}-\ln 1000 \approx 0.577$, giving $\gamma$ to within $0.1$.

The hardest step is Lemma 2, proving convergence rigorously.

Solution

Lemma 1: Consider the function $f(t)=\frac1t$ on $[1,n]$. For each $k=2,\dots,n$, $\int_{k-1}^k \frac1t dt = \ln k - \ln(k-1) = \ln\frac{k}{k-1}$. Since $\frac1k < \ln\frac{k}{k-1} < \frac1{k-1}$, summing over $k=2$ to $n$, we obtain $\int_1^n \frac{1}{t} dt < x_n < 1 + \int_1^n \frac{1}{t} dt$.

Lemma 2: Let $y_n = x_n - \ln n$. Then

$$y_{n+1}-y_n = \frac{1}{n+1} - \ln\frac{n+1}{n} = \frac{1}{n+1} - \ln\left(1+\frac1n\right).$$

The function $\ln(1+u) \ge u - \frac{u^2}{2}$ for $u>0$, giving $\ln(1+1/n) \ge 1/n - 1/(2n^2)$. Thus $\frac1{n+1} - \ln(1+1/n) \le \frac1{n+1} - \left(1/n - 1/(2n^2)\right) = -\frac1{n(n+1)} + \frac{1}{2n^2} <0$ for $n\ge1$. Therefore $y_n$ is decreasing. From Lemma 1, $y_n > 0$, so $y_n$ is bounded below and decreasing, hence convergent. Define the limit $\gamma = \lim_{n\to\infty} y_n$. This proves part 1.

Lemma 3: Let $n,m\in\mathbb{N}$. Then

$$x_n+x_m-x_{nm} = \sum_{i=1}^{n} \frac1i + \sum_{j=1}^{m} \frac1j - \sum_{k=1}^{nm} \frac1k.$$

Partition the sum $\sum_{k=1}^{nm} 1/k$ into blocks of length $m$: the $i$-th block is $\sum_{l=1}^{m} \frac1{(i-1)m+l}$. Then

$$x_{nm} = \sum_{i=1}^{n} \sum_{l=1}^{m} \frac{1}{(i-1)m+l}.$$

Hence

$$x_n+x_m-x_{nm} = \sum_{i=1}^{n} \frac1i + \sum_{j=1}^{m} \frac1j - \sum_{i=1}^{n} \sum_{l=1}^{m} \frac{1}{(i-1)m+l}.$$

Each term $\sum_{i=1}^{n} \frac1i - \sum_{l=1}^{m} \frac{1}{(i-1)m+l}$ is positive, and $\sum_{j=1}^{m} 1/j - \sum_{i=2}^{n} \sum_{l=1}^{m} 1/((i-1)m+l) \le 1$, giving the required bounds $\gamma < x_n+x_m-x_{nm} \le 1$.

Lemma 4: Take $n=1000$, then $x_{1000} = \sum_{k=1}^{1000} 1/k \approx 7.485$, and $\ln 1000 \approx 6.908$, so $x_{1000}-\ln 1000 \approx 0.577$, giving $\gamma$ accurate to $0.1$.

This completes the proof. ∎

Verification of Key Steps

The crucial step is the monotonicity argument in Lemma 2. Using the inequality $\ln(1+u) \ge u - u^2/2$ ensures the difference $y_{n+1}-y_n$ is negative for all $n\ge1$. Checking small $n$ explicitly, $n=1$, $y_2-y_1 = 1.5 - \ln 2 - 1 \approx -0.193 <0$, consistent with the general proof. Another delicate step is bounding $x_n+x_m-x_{nm}\le 1$: summing small cases, $n=2,m=2$, gives $0.917$, $n=3,m=2$, gives $0.95$, confirming the upper bound is never exceeded and the lower bound exceeds $\gamma$.

Alternative Approaches

An alternative proof of convergence uses the Euler–Maclaurin formula to expand $x_n$ as $\ln n + \gamma + 1/(2n) - 1/(12 n^2) + \dots$, which immediately establishes the existence of the limit and estimates its value. Another approach is a telescoping integral estimate $x_n - \ln n = \sum_{k=1}^n \int_{k}^{k+1} \frac{k - t}{kt} dt$, which shows positivity and convergence. The main approach is preferable for Kvant students because it relies only on elementary inequalities, integral comparisons, and basic series manipulations.