uniolympiads Ελληνικά

IMC 2026, Day 2, Problem 9

Let a1,a2,…a_1, a_2, \dots be an infinite sequence of positive real numbers satisfying

a1+a2+⋯+a2n−1=an2a_1 + a_2 + \dots + a_{2n-1} = a_n^2

for all positive integers nn. Prove that an≥2n−1a_n \ge 2n - 1 for all positive integers nn.

Original from the official PDFLet a1, a2, ... be an infinite sequence of positive real numbers satisfying a1 + a2 + ··· + a2n−1 = a²n for all positive integers n. Prove that an ≥ 2n − 1 for all positive integers n.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(proposed by Ilya I. Bogdanov, MIPT, Moscow and Aleksandr Kuznetsov, SPbU, Saint Petersburg)

Solution 1. The condition applied to n=1n = 1 gives a1=1a_1 = 1, so the desired inequality holds for n=1n = 1.

Denote δn=an+1−an\delta_n = a_{n+1} - a_n. Say that an index ii is regular if ai+1≥2i+1a_{i+1} \ge 2i + 1; otherwise ii is irregular. Our aim is to prove that all indices are regular.

Say that our sequence is μ\mu-good if δi≥μ\delta_i \ge \mu for all irregular indices ii. We will show that our sequence is μ\mu-good for all μ<2\mu < 2. This yields the desired inequality; indeed, otherwise, choosing the minimum irregular index nn, we get an+1−an<(2n+1)−(2n−1)=2a_{n+1} - a_n < (2n+1) - (2n-1) = 2, so the sequence would not be μ\mu-good for some μ<2\mu < 2.

Notice that an+12−an2=a2n+a2n+1>0a_{n+1}^2 - a_n^2 = a_{2n} + a_{2n+1} > 0, so an+1>ana_{n+1} > a_n for all nn, and hence the sequence is 00-good. Now the desired statement follows from the Claim below.

Claim. If our sequence (an)(a_n) is μ\mu-good for some 0≤μ<20 \le \mu < 2, then it is also ν\nu-good for ν=μ2+1\nu = \frac{\mu}{2} + 1.

Proof. Consider any irregular index nn. Notice that ak−an+1≥(k−n−1)μa_k - a_{n+1} \ge (k - n - 1)\mu for every k>n+1k > n + 1; indeed, if all indices n+1,n+2,…,k−1n+1, n+2, \ldots, k-1 are irregular, then this follows from (an)(a_n) being μ\mu-good. Otherwise, let ii be the maximum regular index not exceeding k−1k - 1. Then

ak−an+1=(ak−ai+1)+(ai+1−an+1)≥μ(k−i−1)+((2i+1)−(2n+1))=μ(k−i−1)+2(i−n)>μ(k−n−1),a_k - a_{n+1} = (a_k - a_{i+1}) + (a_{i+1} - a_{n+1}) \ge \mu(k-i-1) + ((2i+1) - (2n+1)) = \mu(k-i-1) + 2(i-n) > \mu(k-n-1),
as desired.

Therefore,

δn(2an+1−δn)=an+12−an2=a2n+a2n+1≥2an+1+(2n−1)μ,\delta_n(2a_{n+1} - \delta_n) = a_{n+1}^2 - a_n^2 = a_{2n} + a_{2n+1} \ge 2a_{n+1} + (2n-1)\mu,
This inequality easily yields δn>1\delta_n > 1, so in particular an+1>2a_{n+1} > 2. Then the function f(x)=x(2an+1−x)f(x) = x(2a_{n+1} - x) increases on x∈[0,2]x \in [0, 2], and in order to prove δn≥ν\delta_n \ge \nu it suffices to show that f(ν)≤2an+1+(2n−1)μf(\nu) \le 2a_{n+1} + (2n-1)\mu. This inequality rewrites as
μan+1−(μ2+1)2≤(2n−1)μ  ⟺  μ(an+1−2n−1)≤(μ2−1)2.\mu a_{n+1} - \left(\frac{\mu}{2} + 1\right)^2 \le (2n-1)\mu \iff \mu(a_{n+1} - 2n - 1) \le \left(\frac{\mu}{2} - 1\right)^2.
This last inequality holds, since the left hand part is negative, while the right hand part is positive.

Solution 2. First, let us prove that the required inequality holds asymptotically, namely

Lemma. lim inf⁡n→∞an2n−1≥1\liminf\limits_{n\to\infty} \frac{a_n}{2n-1} \ge 1

Proof. Let AA denote this limit inferior. Clearly, the sequence is monotonically increasing. Then an2=a1+a2+⋯+a2n−1≥nana_n^2 = a_1 + a_2 + \cdots + a_{2n-1} \ge na_n, hence A≥12>0A \ge \frac{1}{2} > 0.

Let ε>0\varepsilon > 0. We know that an≥(A−ε)(2n−1)a_n \ge (A - \varepsilon)(2n-1) for all sufficiently large nn. Then, from the inequality

an2=a1+a2+⋯+a2n−1≥(A−ε)(1+3+…+4n−3)+O(1)=(A−ε)(2n−1)2+O(1)a_n^2 = a_1 + a_2 + \cdots + a_{2n-1} \ge (A - \varepsilon)(1 + 3 + \ldots + 4n - 3) + O(1) = (A - \varepsilon)(2n-1)^2 + O(1)
we obtain A2≥A−εA^2 \ge A - \varepsilon. Letting ε\varepsilon tend to zero, we get A≥1A \ge 1.

Let us make the substitution bn=an−(2n−1)b_n = a_n - (2n-1). The recurrence relation takes the form

bn(bn+2(2n−1))=b1+…+b2n−1,b_n(b_n + 2(2n-1)) = b_1 + \ldots + b_{2n-1},
and the lemma implies that lim inf⁡n→∞bn2n−1≥0\liminf\limits_{n\to\infty} \frac{b_n}{2n-1} \ge 0. Consider B=inf⁡nbn2n−1B = \inf\limits_{n} \frac{b_n}{2n-1}. If B<0B < 0, then the infimum is attained at some k∈Nk \in \mathbb{N}, i.e. bk=B(2k−1)b_k = B(2k-1) (otherwise we get a contradiction with the lemma). Then
B(B+2)(2k−1)2=bk(bk+2(2k−1))=b1+…+b2k−1>B(1+3+…+4k−3)=B(2k−1)2.B(B+2)(2k-1)^2 = b_k(b_k + 2(2k-1)) = b_1 + \ldots + b_{2k-1} > B(1 + 3 + \ldots + 4k - 3) = B(2k-1)^2.
This yields B<−1B < -1. On the other hand, an>0a_n > 0 implies B>−1B > -1 and we get a contradiction.

Solution 2 (by Dan Carmon). Begin with observing a1=a12a_1 = a_1^2, so a1=1a_1 = 1 from positivity. It follows that an2=∑i=12n−1ai≥a1=1a_n^2 = \sum_{i=1}^{2n-1} a_i \ge a_1 = 1 so an≥1=(2n−1)0a_n \ge 1 = (2n-1)^0 for every nn. Applying the same technique again gives an2=∑i=12n−1ai≥2n−1a_n^2 = \sum_{i=1}^{2n-1} a_i \ge 2n - 1 so an≥2n−1=(2n−1)1/2a_n \ge \sqrt{2n-1} = (2n-1)^{1/2}. Applying this technique again and again, we will prove the following claim by induction on mm:

Claim. Let m≥0m \ge 0, and set cm=1−2−mc_m = 1 - 2^{-m}. Then there is a constant Cm>0C_m > 0 such that an≥Cm(2n−1)cma_n \ge C_m(2n-1)^{c_m} for all n≥1n \ge 1.

Moreover, we will get a recurrence relation for CmC_m, and show that lim⁡m→∞Cm=1\lim_{m\to\infty} C_m = 1. It would follow that an≥lim⁡m→∞Cm(2n−1)cm=2n−1a_n \ge \lim_{m\to\infty} C_m(2n-1)^{c_m} = 2n - 1, as we are asked to show.

Proof. We have already established the m=0,1m = 0, 1 (c0=0c_0 = 0, c1=1/2c_1 = 1/2) with C0=C1=1C_0 = C_1 = 1. Let m≥1m \ge 1 and suppose an≥Cm(2n−1)cma_n \ge C_m(2n-1)^{c_m} for every nn. Write c=cmc = c_m and C=CmC = C_m for brevity. Since c<1c < 1, the function xcx^c is concave, and therefore have xc≥12∫x−1x+1tcdtx^c \ge \frac{1}{2}\int_{x-1}^{x+1} t^c dt. Thus

an2=∑k=12n−1ak≥C∑k=12n−1(2k−1)c≥C2∑k=12n−1∫2k−22ktcdt=C2∫04n−2tcdt=C2 (4n−2)c+1c+1=2cC1+c(2n−1)1+c.\begin{aligned} a_n^2 &= \sum_{k=1}^{2n-1} a_k \ge C\sum_{k=1}^{2n-1} (2k-1)^c \ge \frac{C}{2}\sum_{k=1}^{2n-1} \int_{2k-2}^{2k} t^c dt = \frac{C}{2}\int_0^{4n-2} t^c dt = \frac{C}{2}\,\frac{(4n-2)^{c+1}}{c+1} \\ &= \frac{2^c C}{1+c}(2n-1)^{1+c}. \end{aligned}
Recall c=cm=1−2−mc = c_m = 1 - 2^{-m} hence 1+c2=cm+1\frac{1+c}{2} = c_{m+1}. Taking the square root of the above inequality yields
an≥2−2−m1−2−m−1Cm⋅(2n−1)cm+1(1)a_n \ge \sqrt{\frac{2^{-2^{-m}}}{1 - 2^{-m-1}}C_m}\cdot(2n-1)^{c_{m+1}} \tag{1}
Which completes the inductions step for Cm+1=BmCmC_{m+1} = \sqrt{B_m C_m}, where Bm=2−2−m1−2−m−1B_m = \frac{2^{-2^{-m}}}{1 - 2^{-m-1}}.

Observe that Bm→1B_m \to 1 as m→∞m \to \infty (since 2−m→02^{-m} \to 0), and the sequence CmC_m is obtained by repeatedly averaging (geometrically) the previous term with the terms of BmB_m. It is well known (a standard exercise in calculus 1) that this implies CmC_m also converges and to the same limit as BmB_m, as we claimed. This can be shown directly by limits calculus; another method is to apply Cesaro’s theorem on geometric means to the sequence DkD_k defined by D1=C1D_1 = C_1, Dk=B⌈log⁡2(k)⌉D_k = B_{\lceil \log_2(k) \rceil} (i.e., the first elements are C1,B1,B2,B2,B3,B3,B3,B3,B4,…C_1, B_1, B_2, B_2, B_3, B_3, B_3, B_3, B_4, \ldots), which clearly has the same limit as BmB_m, and each CmC_m is just the geometric mean of the first 2m−12^{m-1} elements of DkD_k.

Transcribed from the official solutions, pages 5–7. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?