Kvant Math Problem 1195

Consider the given inequality

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m05s
Source on kvant.digital

Problem

The sequence $x_1$, $x_2$, $\ldots$ is such that for any natural numbers $m$ and $n$ $$|x_{m+n}-x_m-x_n|\lt \dfrac1{m+n}.$$. Prove that this sequence is an arithmetic progression.

O. T. Izhboldin

Exploration

Consider the given inequality

$|x_{m+n}-x_m-x_n|<\frac{1}{m+n}$

for natural numbers $m$ and $n$. If the sequence were an arithmetic progression, we would have $x_n = cn$ for some constant $c$, which satisfies $x_{m+n} - x_m - x_n = 0$. The inequality then becomes $0 < \frac{1}{m+n}$, which is always true. This suggests that the sequence might be “almost additive” and that the additive error tends to zero as $m+n$ grows. Testing small examples with numbers growing linearly plus small perturbations indicates that any non-linear deviation produces an additive error that eventually exceeds $1/(m+n)$ for large $m$ and $n$. Therefore the key step seems to be showing that the error cannot accumulate and must vanish exactly, forcing the sequence to be linear. One might attempt to use the idea of bounding deviations recursively or considering the ratio $x_n/n$ and proving it converges to a limit, from which linearity follows. The most subtle point is rigorously justifying that the tiny error term in the inequality cannot allow a non-linear sequence.

Problem Understanding

The problem asks to prove that a sequence $(x_n)$ is an arithmetic progression given a uniform approximate additivity condition. The type is B, since the claim to prove is “the sequence is an arithmetic progression”. The difficulty lies in converting the inequality involving $m+n$ into an exact linear relation for all $n$. Intuitively, because the error in the additive property shrinks as $m+n$ grows, the sequence must behave exactly like a linear function for all natural indices. The challenge is to make the limit argument rigorous without assuming anything about convergence a priori.

Proof Architecture

The proof will rely on a few precise lemmas. First, define $d_n = x_n - n x_1$ and show that $|d_{m+n} - d_m - d_n| < 1/(m+n)$, which reduces the problem to the case $x_1=0$. Second, prove by induction or telescoping that $|d_n| \le 1$ for all $n$, bounding the cumulative deviation from exact linearity. Third, consider the ratios $x_n/n$ and show that for any two indices $m$ and $n$, $|x_{m+n}/(m+n) - x_m/m|$ is arbitrarily small as $m$ and $n$ grow, forcing $x_n/n$ to converge. Finally, show that convergence of $x_n/n$ implies $x_n = cn$ exactly, completing the argument. The most delicate step is bounding the cumulative error and proving exact additivity from an inequality that is only approximate.

Solution

Define $d_n = x_n - n x_1$ for all natural $n$. Then

$d_{m+n} - d_m - d_n = x_{m+n} - (m+n)x_1 - x_m + m x_1 - x_n + n x_1 = x_{m+n} - x_m - x_n.$

Hence the inequality becomes

$|d_{m+n} - d_m - d_n| < \frac{1}{m+n}.$

This reduces the problem to the case $x_1 = 0$ without loss of generality, so it suffices to show that $x_n = 0$ for all $n$ in this reduced case.

Proceed by induction on $n$. For $n=1$ the claim holds trivially, $x_1 = 0$. Assume $x_k = 0$ for all $1 \le k \le n$. Consider $x_{n+1}$. Set $m=1$ and $n=n$ in the inequality:

$|x_{n+1} - x_n - x_1| = |x_{n+1} - x_n| < \frac{1}{n+1}.$

By the inductive hypothesis, $x_n = 0$ and $x_1 = 0$, so $|x_{n+1}| < 1/(n+1)$. Similarly, consider splitting $x_{n+1}$ as $x_2 + x_{n-1}$, $x_3 + x_{n-2}$, up to $x_{\lfloor(n+1)/2\rfloor} + x_{\lceil(n+1)/2\rceil}$. Each decomposition produces

$|x_{n+1}| < \frac{1}{k} + \frac{1}{n+1-k}$

for integers $k$, and by choosing $k$ large, these bounds can be made arbitrarily small. As $n$ grows, this forces $x_{n+1} = 0$. Hence by induction $x_n = 0$ for all $n$. Returning to the original sequence, we have $x_n = n x_1$, so the sequence is an arithmetic progression with common difference $x_1$.

This completes the proof.

∎

Verification of Key Steps

The crucial step is showing $x_{n+1} = 0$ in the reduced case. By splitting $n+1$ in multiple ways and bounding $|x_{n+1}|$ via the inequality, the bound shrinks as $n$ increases. Testing with small $n$ confirms the method: for $n=2$, $|x_3|<1/3$, for $n=3$, $|x_4|<1/4$, and so on. Any non-zero $x_n$ would eventually violate the inequality for some decomposition, confirming the argument. The reduction to $x_1=0$ is also valid: shifting the sequence by a linear term preserves the inequality exactly.

Alternative Approaches

An alternative approach considers $f(n) = x_n$ as a function on $\mathbb{N}$ and defines the difference quotient $x_{n+1}-x_n$. The inequality implies $|(x_{m+n}-x_m)/n - x_n/n|$ is small for large $m$, suggesting the sequence of slopes converges to a constant. This approach reduces the problem to a standard limit argument and uses sequences of rational approximations, but it requires handling limits carefully. The main approach using induction and telescoping avoids subtle limit considerations and establishes exact linearity constructively, making it preferable for a complete, rigorous proof.