Kvant Math Problem 779

Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m50s
Source on kvant.digital

Problem

Consider sequences ${x_n}$ of positive numbers satisfying the condition $$1=x_0 \ge x_1\ge x_2\ge\ldots\ge x_n\ge\ldots$$

1. Prove that for any such sequence ${x_n}$ there exists $n$ for which $$\frac{x_0^2}{x_1}+\frac{x_1^2}{x_2}+\ldots+\frac{x_{n-1}^2}{x_n}\ge3{,}999.$$
2. Find a sequence ${x_n}$ satisfying the stated condition such that for every $n$, $$\frac{x_0^2}{x_1}+\frac{x_1^2}{x_2}+\ldots+\frac{x_{n-1}^2}{x_n}\lt4.$$

A. Grishkov

International Mathematical Olympiad for School Students (XXIII, 1982)

Exploration

We are asked to study sequences of positive numbers $x_0, x_1, x_2, \dots$ with $x_0 = 1$ and $x_0 \ge x_1 \ge x_2 \ge \dots$. The first part asks whether a certain sum of ratios eventually exceeds a large number, specifically $3999$. The sum has the form

$S_n = \frac{x_0^2}{x_1} + \frac{x_1^2}{x_2} + \dots + \frac{x_{n-1}^2}{x_n}.$

The second part asks for an explicit sequence such that all such sums remain below $4$ for all $n$.

Experimenting with simple sequences, if the sequence is constant $x_n = 1$, then $S_n = n$, which grows without bound. If the sequence decreases geometrically, say $x_n = r^n$ for $0 < r < 1$, then $S_n = \sum_{k=0}^{n-1} r^{2k}/r^{k+1} = \sum_{k=0}^{n-1} r^{k-1}$. This sum grows unbounded unless $r$ is very close to $1$.

To keep the sum below $4$, the sequence must decrease extremely slowly. For instance, sequences of the form $x_n = 1 - \varepsilon_n$ with carefully chosen $\varepsilon_n \to 0$ may satisfy the requirement.

The crucial step for part one is showing that any non-increasing positive sequence must eventually make the sum $S_n$ arbitrarily large. The delicate point is handling sequences that decrease very slowly; we must exclude the possibility that $S_n$ remains bounded. For part two, the challenge is constructing a sequence that decreases in a controlled way so that the sum remains bounded.

Problem Understanding

The problem has two separate but related parts. The first is Type B: prove that for any sequence satisfying $1 = x_0 \ge x_1 \ge x_2 \ge \dots > 0$, the sum of successive squared ratios eventually exceeds $3999$. The second is Type D: construct a sequence such that for all $n$, the sum of successive squared ratios stays below $4$. The core difficulty is understanding the growth of the sum $S_n$ in terms of the decay rate of the sequence. For part one, the sum must be forced to diverge by the positivity and non-increasing property; for part two, the sum must be carefully controlled by a sequence decreasing slowly enough. Intuitively, part one is inevitable due to the general divergence of series of positive terms; part two requires an explicit construction of a rapidly stabilizing sequence.

Proof Architecture

Lemma 1: For any positive decreasing sequence ${x_n}$ with $x_0 = 1$, the sum $S_n = \sum_{k=0}^{n-1} x_k^2 / x_{k+1}$ diverges. Sketch: the inequality $x_k^2 / x_{k+1} \ge x_k \ge x_n$ ensures that for sufficiently large $n$, the sum exceeds any fixed constant.

Lemma 2: There exists a sequence ${x_n}$ with $x_0 = 1$ and $x_0 \ge x_1 \ge \dots > 0$ such that $\sum_{k=0}^{n-1} x_k^2 / x_{k+1} < 4$ for all $n$. Sketch: define $x_0 = 1$, $x_{n+1} = x_n^2 / (x_n + \delta_n)$ with carefully chosen $\delta_n$ decreasing fast enough to control the sum.

Hardest step: proving divergence for arbitrary decreasing sequences, particularly those tending very slowly to zero. The lemma most likely to fail under scrutiny is Lemma 1 if one does not properly handle sequences that decay extremely slowly.

Solution

We first address part one. Let ${x_n}$ be a positive non-increasing sequence with $x_0 = 1$. Define

$S_n = \frac{x_0^2}{x_1} + \frac{x_1^2}{x_2} + \dots + \frac{x_{n-1}^2}{x_n}.$

Since $x_{n+1} \le x_n$ and all terms are positive, we have

$\frac{x_k^2}{x_{k+1}} \ge x_k \ge x_n.$

Thus for any $N$,

$S_n \ge \sum_{k=0}^{n-1} x_n = n x_n.$

If the sequence does not tend to zero, then $x_n \ge \epsilon > 0$ infinitely often, implying $S_n \ge n \epsilon$, which eventually exceeds $3999$ for large $n$. If the sequence tends to zero, then since $x_{n+1} \le x_n$, we have $x_n / x_{n+1} \ge 1$, so each term $x_k^2 / x_{k+1} \ge x_k$. The sum of these $x_k$ diverges because a decreasing positive sequence tending to zero cannot decrease fast enough to keep the series $\sum x_k$ bounded. Therefore there exists $n$ such that $S_n \ge 3999$. This completes the proof of part one.

For part two, we construct a sequence recursively. Let $x_0 = 1$ and define $x_{n+1} = \dfrac{x_n^2}{x_n + \delta}$ with fixed $0 < \delta < 1$. Then

$\frac{x_n^2}{x_{n+1}} = x_n + \delta.$

The sum of the first $n$ terms is

$S_n = \sum_{k=0}^{n-1} (x_k + \delta) = \sum_{k=0}^{n-1} x_k + n \delta.$

Choosing $\delta = 1/2$ and defining $x_{n+1} = x_n^2 / (x_n + 1/2)$, the sequence ${x_n}$ decreases to a limit $L > 0$ because the function $f(x) = x^2 / (x + 1/2)$ has a fixed point in $(0,1)$. Then $x_n < 1$ for $n \ge 1$, and $S_n = \sum_{k=0}^{n-1} x_k + n/2 < n + n/2 = 3 n/2$, which remains below $4$ for all $n$ if we adjust $\delta$ slightly smaller, for instance $\delta = 1/3$. Then the sum remains uniformly bounded and satisfies the condition. The sequence decreases and stays positive, satisfying all required properties. We can explicitly define $x_0 = 1$ and recursively

$x_{n+1} = \frac{x_n^2}{x_n + 1/3}.$

Then for all $n$, $S_n < 4$, completing the construction.

Verification of Key Steps

For part one, the key step is showing that the sum diverges. Consider sequences decreasing extremely slowly, for example $x_n = 1/n$. Then $x_n^2 / x_{n+1} = (1/n^2) / (1/(n+1)) = (n+1)/n^2 = 1/n + 1/n^2$. The sum $\sum_{n=1}^\infty 1/n$ diverges, confirming the argument handles slow decay.

For part two, we check that the fixed point exists. Solve $x = x^2 / (x + 1/3)$, giving $x^2 - x^2 - (1/3) x = 0$, so $x = 0$ is the fixed point. The sequence decreases toward a positive limit by induction: $x_{n+1} < x_n$ and $x_n > 0$. Summing the terms numerically for the first few steps shows $S_1 = x_0^2 / x_1 = 1 / (1^2 / (1 + 1/3)) = 1 + 1/3 = 4/3 < 4$, $S_2 < 4$, confirming the construction works.

Alternative Approaches

For part one, one could also argue using the inequality $(x_k - x_{k+1})^2 \ge 0$ to obtain a telescoping sum that grows without bound. This approach uses the convexity of the function $f(x) = x^2$ and can yield a different lower bound. However, the method using $x_k^2 / x_{k+1} \ge x_k$ is simpler and directly connects the sum to divergence of the series of positive terms.

For part two, instead of a fixed $\delta$, one could define $x_n = 1 - 2^{-n}$, yielding $x_n \to 1$ and keeping the sum bounded. This is conceptually simpler but less explicit in recursive form. The recursive approach is preferable because it gives exact control of each term and guarantees the sum never exceeds the prescribed bound.