Kvant Math Problem 945

Let

kvantmathematicsolympiad

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

Problem

Given a strictly increasing unbounded sequence of positive numbers $a_1$, $a_2$, $\ldots$, prove that for all sufficiently large $k$ the inequality holds

  1. $\dfrac{a_1}{a_2}+\dfrac{a_2}{a_3}+\ldots+\dfrac{a_k}{a_{k+1}} \lt k-1$;
  2. $\dfrac{a_1}{a_2}+\dfrac{a_2}{a_3}+\ldots+\dfrac{a_k}{a_{k+1}} \lt k-1985$.

L. D. Kurlyandchik

All-Union Mathematical Olympiad (1985)

Exploration

Let

$S_k=\sum_{i=1}^k \frac{a_i}{a_{i+1}}, \qquad d_i = 1-\frac{a_i}{a_{i+1}}=\frac{a_{i+1}-a_i}{a_{i+1}}.$

Then

$S_k = k - \sum_{i=1}^k d_i.$

So the problem becomes understanding whether the deficit

$D_k=\sum_{i=1}^k d_i$

must eventually exceed any fixed constant.

The sequence $(a_n)$ is strictly increasing and unbounded, so ratios $a_{i+1}/a_i>1$ but may approach $1$ extremely fast. The key question is whether this still forces divergence of $D_k$.

Try the borderline example $a_n=n$: then $d_i=\frac{1}{i+1}$ and $D_k\sim \log k$, which diverges.

Try a slower growth such as $a_n=\log n$ is not valid (not increasing from start and not unbounded positive ratios well-defined), but exponential-type constructions still give positive deficits.

The critical insight is to rewrite $d_i$ using logarithms:

$\log\frac{a_{i+1}}{a_i}.$

Since $a_n$ is unbounded, $\log a_n \to \infty$, hence

$\sum_{i=1}^k \log\frac{a_{i+1}}{a_i} \to \infty.$

We need to compare $\log t$ with $1-\frac{1}{t}$ for $t\ge 1$.

Thus the problem reduces to proving a uniform inequality linking these expressions, which forces divergence of $D_k$.

Problem Understanding

This is a Type C problem: it is about eventual bounds on a partial sum.

We must prove that for any strictly increasing unbounded sequence of positive numbers, the sum

$\sum_{i=1}^k \frac{a_i}{a_{i+1}}$

is eventually strictly smaller than $k-1$ and even $k-1985$.

Since each term is less than $1$, the sum is always less than $k$, but the task is to show a uniform deficit that grows beyond any fixed constant. The core difficulty is that the ratios $a_i/a_{i+1}$ can be arbitrarily close to $1$, so no local estimate suffices; the argument must use global divergence of $a_n$.

The expected mechanism is that unboundedness forces the product $\prod (a_{i+1}/a_i)$ to diverge, which translates into divergence of a sum of small deficits.

The conclusion to establish is:

$\boxed{\text{For all sufficiently large } k,; S_k<k-1 \text{ and } S_k<k-1985.}$

Proof Architecture

First lemma states that for all $t\ge 1$,

$\log t \ge 1-\frac{1}{t},$

with equality only at $t=1$, proved via monotonicity of the difference function.

Second lemma expresses the telescoping identity

$\sum_{i=1}^k \log\frac{a_{i+1}}{a_i}=\log a_{k+1}-\log a_1.$

Third lemma uses unboundedness of $(a_n)$ to deduce divergence of the right-hand side.

Fourth lemma converts the logarithmic sum bound into a bound for $\sum (1-a_i/a_{i+1})$.

The hardest step is the inequality connecting $\log t$ and $1-\frac{1}{t}$, since it reverses direction compared to the standard $\log t\le t-1$.

Solution

For $t\ge 1$, define

$\varphi(t)=\log t - 1 + \frac{1}{t}.$

We compute

$\varphi'(t)=\frac{1}{t}-\frac{1}{t^2}=\frac{t-1}{t^2}\ge 0 \quad \text{for } t\ge 1.$

Hence $\varphi$ is nondecreasing on $[1,\infty)$. Since $\varphi(1)=0$, we obtain

$\log t \ge 1-\frac{1}{t} \quad \text{for all } t\ge 1.$

Apply this to $t_i=\frac{a_{i+1}}{a_i}>1$. Then

$\log\frac{a_{i+1}}{a_i} \ge 1-\frac{a_i}{a_{i+1}} = d_i.$

Summing from $i=1$ to $k$ gives

$\sum_{i=1}^k \log\frac{a_{i+1}}{a_i} \ge \sum_{i=1}^k d_i.$

The left-hand side telescopes:

$\sum_{i=1}^k \log\frac{a_{i+1}}{a_i} = \log a_{k+1}-\log a_1.$

Since $(a_n)$ is unbounded, $\log a_{k+1}\to\infty$, hence

$\sum_{i=1}^k d_i \to \infty.$

Therefore

$S_k = k - \sum_{i=1}^k d_i \to -\infty \text{ relative to } k,$

meaning the deficit $k-S_k$ tends to infinity.

Thus for every constant $C>0$ there exists $k_0$ such that for all $k\ge k_0$,

$\sum_{i=1}^k d_i > C.$

Taking $C=1$ yields

$S_k < k-1$

for all sufficiently large $k, and taking $C=1985$ yields

$S_k < k-1985$

for all sufficiently large $k.

This completes the proof. ∎

Verification of Key Steps

The crucial inequality is

$\log t \ge 1-\frac{1}{t} \quad (t\ge 1).$

Its validity depends on checking that the derivative of $\log t - 1 + 1/t$ is nonnegative for all $t\ge 1$, which gives monotonicity from the base point $t=1$.

The second delicate step is the implication from divergence of $\log a_{k+1}$ to divergence of the deficit sum. This uses only that $\log a_{k+1}\to\infty$ for any unbounded positive sequence, since logarithm is strictly increasing and unbounded on $(0,\infty)$.

The final step is translating divergence of $\sum d_i$ into eventual inequalities for $S_k$. This is justified because if a nonnegative sequence has diverging partial sums, then it eventually exceeds any fixed constant, which directly produces the two required bounds.

Alternative Approaches

A different approach replaces logarithms with convexity of the function $x\mapsto -\log x$ applied to the ratios $a_{i+1}/a_i$, leading to Jensen-type bounds on products and sums. Another method constructs a comparison with the harmonic sequence by partitioning indices where $a_{i+1}/a_i$ exceeds a fixed threshold, showing that infinitely many such deviations force divergence of the deficit. The logarithmic approach is preferable because it converts multiplicative growth directly into an additive telescoping quantity with minimal case analysis.