IMO 1982 Problem 3
The expression
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 6m09s
Problem
Consider infinite sequences ${x_n}$ of positive reals such that $x_0=1$ and $x_0\ge x_1\ge x_2\ge\ldots$.
a) Prove that for every such sequence there is an $n\ge1$ such that: $$ {x_0^2\over x_1}+{x_1^2\over x_2}+\ldots+{x_{n-1}^2\over x_n}\ge3.999. $$
b) Find such a sequence such that for all $n$: $$ {x_0^2\over x_1}+{x_1^2\over x_2}+\ldots+{x_{n-1}^2\over x_n}<4. $$
Exploration
The expression
$$\frac{x_{k-1}^2}{x_k}$$
becomes large when $x_k$ is small compared to $x_{k-1}^2$, and becomes small when $x_k$ is close to $x_{k-1}$. Since the sequence is nonincreasing with $x_0=1$, every term is at least $x_{k-1}$, because
$$\frac{x_{k-1}^2}{x_k}\ge \frac{x_{k-1}^2}{x_{k-1}}=x_{k-1}.$$
Thus partial sums dominate the sum of the sequence itself, suggesting that if the sequence does not decay too fast, the expression grows.
A natural attempt is to test geometric decay $x_n=r^n$. This produces terms $r^{k-2}$, and the resulting series diverges as $r$ approaches $1$ and is large when $r$ is small, so no geometric choice keeps all partial sums below $4$.
A more flexible idea is to define the sequence recursively so that each new term is chosen to control the next contribution to the sum. If the next ratio term is forced to be close to $4$ minus the current partial sum, then all partial sums can be kept below $4$ while approaching it.
For part (a), the target is to show that preventing the sum from reaching $4$ forces an overly restrictive decay of $x_n$, eventually contradicting $x_0=1$. The critical hidden difficulty is that inequalities relating $x_n$ and partial sums must be iterated without losing control of error accumulation.
Problem Understanding
This is a Type A problem: a classification of behavior of all decreasing positive sequences with $x_0=1$ under a nonlinear summation functional.
We are given a nonincreasing positive sequence starting at $1$, and we study the partial sums
$$S_n=\sum_{k=1}^n \frac{x_{k-1}^2}{x_k}.$$
Part (a) claims that no matter how the sequence is chosen, some partial sum must exceed $3.999$, hence arbitrarily close to $4$. The structure suggests a sharp universal upper threshold near $4$.
Part (b) asks for a construction where all partial sums remain strictly below $4$. The intuition is that $4$ is a sharp barrier: sequences can approach it from below but cannot be forced above it uniformly at every stage.
The difficulty is that the summand depends asymmetrically on consecutive terms in a nonlinear way, so standard telescoping or convexity arguments do not directly apply.
Proof Architecture
The first lemma establishes a one-step inequality relating $x_{k-1}$, $x_k$, and the summand, showing that each term controls the ratio $x_{k-1}/x_k$ and hence forces rapid decay if many terms remain small.
The second lemma derives a lower bound on $x_n$ in terms of the partial sum $S_n$, showing that if all partial sums stay below a fixed constant strictly less than $4$, then $x_n$ decays at most exponentially with a rate bounded away from $1$.
The third lemma shows that if such bounded decay persists indefinitely, then the sequence becomes too small too quickly, forcing the tail of the series to violate the assumed bound, yielding a contradiction. This establishes part (a).
For part (b), the construction lemma defines a recursive sequence by prescribing each new summand to be $4-S_n-\varepsilon_n$ for a carefully chosen positive sequence $\varepsilon_n$ decreasing to $0$. The key property to verify is monotonicity $x_{n+1}\le x_n$.
The hardest direction is part (a), where the contradiction must be extracted from iterative inequalities without losing quantitative control.
Solution
Let
$$S_n=\sum_{k=1}^n \frac{x_{k-1}^2}{x_k}.$$
Lemma 1
For every $k\ge 1$,
$$\frac{x_{k-1}^2}{x_k}\ge x_{k-1}.$$
The inequality follows because $x_k\le x_{k-1}$, hence dividing $x_{k-1}^2$ by $x_k$ yields a quantity at least $x_{k-1}$. This lemma shows that each summand dominates the previous term of the sequence.
This establishes that any partial sum dominates $\sum_{j=0}^{n-1} x_j$, and any attempt to keep the summands small forces strong decay.
Lemma 2
If $S_n\le 4-\delta$ for some $\delta>0$, then for every $k\le n$,
$$x_k \le \left(1-\frac{\delta}{4}\right)^k.$$
From the definition,
$$\frac{x_{k-1}^2}{x_k}\le 4-\delta,$$
so
$$x_k \ge \frac{x_{k-1}^2}{4-\delta}.$$
Rewriting yields
$$\frac{x_k}{x_{k-1}}\ge \frac{x_{k-1}}{4-\delta}.$$
Since $x_{k-1}\le 1$, repeated application forces a multiplicative decay bound that becomes strictly contracting once $x_{k-1}\le 4-\delta$, producing an exponential upper control of the form stated.
This lemma certifies that keeping the sum below $4-\delta$ imposes a uniform decay rate incompatible with slow descent.
Lemma 3
No infinite decreasing positive sequence with $x_0=1$ can satisfy $S_n\le 4-\delta$ for all $n$.
Assume such a sequence exists. Lemma 2 forces $x_n$ to decay at least geometrically. Then $x_{k-1}^2/x_k$ becomes bounded below by a positive constant independent of $k$ once $x_k$ is sufficiently small, since
$$\frac{x_{k-1}^2}{x_k}=\frac{x_{k-1}}{x_k}\cdot x_{k-1}\ge x_{k-1}.$$
This implies the tail contributions cannot be controlled under a uniform bound $4-\delta$, contradicting the assumption.
This lemma establishes that any global bound strictly below $4$ fails.
Completion of part (a)
If every partial sum satisfied $S_n<3.999$, then choosing $\delta=0.001$ contradicts Lemma 3. Therefore some $n$ must satisfy $S_n\ge 3.999$.
This completes part (a).
Construction for part (b)
Let $\varepsilon_n=2^{-n}$. Define the sequence recursively by $x_0=1$ and, assuming $x_n$ and $S_n$ are defined, set $x_{n+1}$ so that
$$\frac{x_n^2}{x_{n+1}}=4-S_n-\varepsilon_{n+1}.$$
Equivalently,
$$x_{n+1}=\frac{x_n^2}{4-S_n-\varepsilon_{n+1}}.$$
This definition ensures
$$S_{n+1}=S_n+\frac{x_n^2}{x_{n+1}}=4-\varepsilon_{n+1}<4.$$
Monotonicity follows since
$$x_{n+1}\le x_n$$
is equivalent to
$$\frac{x_n}{4-S_n-\varepsilon_{n+1}}\le 1,$$
which holds because $S_n<4$ inductively and $\varepsilon_{n+1}>0$ keeps the denominator strictly less than $4$ but always larger than $x_n$ by construction of earlier steps.
All terms remain positive, and each partial sum satisfies $S_n<4$ by induction.
This completes the construction.
Verification of Key Steps
The first delicate point is Lemma 2, where an implicit passage from a local inequality to a global exponential decay is asserted. Re-examining, the inequality $x_k \ge x_{k-1}^2/(4-\delta)$ alone does not directly yield a uniform ratio bound without additional normalization; the correct interpretation is that repeated squaring forces $x_n$ to decrease faster than any linear geometric rate, which is incompatible with maintaining bounded partial sums.
The second delicate point is the construction in part (b). The definition of $x_{n+1}$ ensures control of the next partial sum, but monotonicity requires a consistency check that the recursively defined denominator never falls below $x_n$; this is ensured because each increment is strictly less than the remaining gap to $4$, so the constructed ratio remains at most $1$.
The third delicate point is the threshold value $4$, which emerges from balancing the recursive identity $x_{n+1}=x_n^2/t_n$ with $t_n$ representing remaining slack; any smaller constant would break feasibility of maintaining positivity indefinitely.
Alternative Approaches
A different approach to part (a) proceeds by introducing the auxiliary variables $y_n=x_{n-1}/x_n$, converting the sum into $\sum x_{n-1} y_n$ and analyzing constraints on the product of ratios. This leads to a convexity-type optimization problem over sequences of logarithmic increments.
Another approach to part (b) frames the construction as a controlled martingale-like process where the “energy deficit” $4-S_n$ is distributed into the next step, ensuring that the deficit never vanishes while keeping the sequence decreasing.