Kvant Math Problem 865

For consecutive pairs $a_{i-1}<a_i$, the expression

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 12m45s
Source on kvant.digital

Problem

Let $[a,b]$ denote the least common multiple of the integers $a$ and $b$. Prove that for any $n+1$ numbers $a_0\lt a_1\lt\ldots\lt a_n$ the inequality $$\dfrac1{[a_0,a_1]}+\dfrac1{[a_1,a_2]}+\ldots+\dfrac1{[a_{n-1},a_n]}\le1-\dfrac1{2^n},$$ holds if

  1. $n=2$;
  2. $n=3$;
  3. $n$ is an arbitrary natural number

B. M. Ivlev

Exploration

For consecutive pairs $a_{i-1}<a_i$, the expression

$$\frac{1}{[a_{i-1},a_i]}=\frac{\gcd(a_{i-1},a_i)}{a_{i-1}a_i}$$

suggests comparing $\gcd(a_{i-1},a_i)$ with $a_i-a_{i-1}$, since the target inequality on the right-hand side telescopes into a difference of reciprocals.

A key observation is that $\gcd(a_{i-1},a_i)$ divides every integer linear combination of $a_{i-1}$ and $a_i$, in particular their difference $a_i-a_{i-1}$. This forces $\gcd(a_{i-1},a_i)\le a_i-a_{i-1}$. This converts each term involving an LCM into a difference of reciprocals.

After summation, a telescoping expression appears, reducing the problem to bounding $1/a_0 - 1/a_n$. The worst case should occur when $a_0$ is minimal and $a_n$ is as small as possible given strict monotonicity, namely $a_0=1$ and $a_n\ge n+1$. The remaining task is to compare $1/(n+1)$ with $1/2^n$, which reduces to verifying $n+1\le 2^n$.

The main delicate point is ensuring that replacing each LCM term by a difference of reciprocals does not lose direction and that the final bound is tight enough for all $n$.

Problem Understanding

This is a Type B problem, a proof of an inequality involving least common multiples of consecutive elements of an increasing integer sequence.

The core difficulty is to control $\frac{1}{[a_{i-1},a_i]}$ uniformly without knowing any structure of the sequence beyond monotonicity. The key idea is to convert LCMs into gcd expressions and then exploit divisibility properties to obtain a telescoping sum.

The goal is to prove

$$\sum_{i=1}^{n} \frac{1}{[a_{i-1},a_i]} \le 1 - \frac{1}{2^n}.$$

Proof Architecture

The proof relies on the identity $[x,y]=\frac{xy}{\gcd(x,y)}$, which yields

$$\frac{1}{[x,y]}=\frac{\gcd(x,y)}{xy}.$$

The main lemma states that for integers $x<y$, one has $\gcd(x,y)\le y-x$, because $\gcd(x,y)$ divides $y-x$.

This implies the inequality

$$\frac{1}{[x,y]} \le \frac{y-x}{xy} = \frac{1}{x}-\frac{1}{y}.$$

Summing over all consecutive pairs produces a telescoping sum bounded by $1/a_0 - 1/a_n$.

A final lemma bounds $a_n\ge a_0+n\ge n+1$, and uses $n+1\le 2^n$ to finish the estimate.

The most delicate point is the transition from LCM terms to the telescoping expression, since it determines the sharpness of the final bound.

Solution

For integers $x,y$, the least common multiple satisfies

$$[x,y]=\frac{xy}{\gcd(x,y)}.$$

Hence

$$\frac{1}{[x,y]}=\frac{\gcd(x,y)}{xy}.$$

Let $x<y$. The number $\gcd(x,y)$ divides both $x$ and $y$, hence it divides any integer linear combination of them. In particular, it divides $y-x$, so $\gcd(x,y)\le y-x$. Therefore

$$\frac{1}{[x,y]}=\frac{\gcd(x,y)}{xy}\le \frac{y-x}{xy}.$$

The right-hand side simplifies as

$$\frac{y-x}{xy}=\frac{1}{x}-\frac{1}{y}.$$

Apply this to each adjacent pair $a_{i-1}<a_i$:

$$\frac{1}{[a_{i-1},a_i]} \le \frac{1}{a_{i-1}}-\frac{1}{a_i}.$$

Summing over $i=1,\dots,n$ yields

$$\sum_{i=1}^n \frac{1}{[a_{i-1},a_i]} \le \sum_{i=1}^n \left(\frac{1}{a_{i-1}}-\frac{1}{a_i}\right).$$

The right-hand side telescopes, since all intermediate terms cancel, leaving

$$\sum_{i=1}^n \left(\frac{1}{a_{i-1}}-\frac{1}{a_i}\right)=\frac{1}{a_0}-\frac{1}{a_n}.$$

Because $a_0\ge 1$, one has $\frac{1}{a_0}\le 1$. Since the sequence is strictly increasing in integers, each step increases by at least $1$, so

$$a_n \ge a_0+n \ge 1+n,$$

hence

$$\frac{1}{a_n}\le \frac{1}{n+1}.$$

Combining these inequalities gives

$$\sum_{i=1}^n \frac{1}{[a_{i-1},a_i]} \le 1-\frac{1}{n+1}.$$

It remains to compare $\frac{1}{n+1}$ and $\frac{1}{2^n}$. The inequality $n+1\le 2^n$ holds for all $n\in\mathbb{N}$, since for $n=1$ equality holds and for $n\ge 2$,

$$2^n = 2\cdot 2^{n-1} \ge 2(n) \ge n+1.$$

Thus $\frac{1}{n+1}\ge \frac{1}{2^n}$, and consequently

$$1-\frac{1}{n+1}\le 1-\frac{1}{2^n}.$$

Therefore,

$$\sum_{i=1}^n \frac{1}{[a_{i-1},a_i]} \le 1-\frac{1}{2^n}.$$

For $n=2$ and $n=3$, the same argument applies directly, and the general estimate specializes to the required cases.

This completes the proof. ∎

Verification of Key Steps

The critical inequality $\gcd(x,y)\le y-x$ follows from the fact that $\gcd(x,y)\mid x$ and $\gcd(x,y)\mid y$, hence it divides any integer linear combination $y-x$. A divisor of a positive integer cannot exceed that integer, establishing the bound.

The telescoping step is exact because each term $\frac{1}{a_i}$ appears once with positive sign from index $i$ and once with negative sign from index $i+1$, leaving only endpoints.

The comparison $n+1\le 2^n$ is sharp at $n=1$ and grows increasingly strict thereafter, ensuring the final bound is always stronger than $1-\frac{1}{n+1}$.

Alternative Approaches

One alternative direction replaces the gcd estimate with $\gcd(x,y)\le \sqrt{xy}$, which yields a weaker but structurally similar bound and leads to a non-telescoping inequality that still collapses via AM-GM arguments. Another approach constructs an induction on $n$, inserting one additional term and controlling its contribution via the same LCM-to-difference transformation; however, this requires re-establishing the telescoping structure at each step, making it less transparent than the direct global summation argument used above.