IMC 2026 · Day 2 · P9

The condition applied to $n = 1$ gives $a_{1} = 1$, so the desired inequality holds for $n = 1$.

Denote $\delta_{n} = a_{n+1} - a_{n}$. Say that an index $i$ is regular if $a_{i+1} \geq 2 i + 1$; otherwise $i$ is irregular. Our aim is to prove that all indices are regular.

Say that our sequence is $\mu$-good if $\delta_{i} \geq \mu$ for all irregular indices $i$. We will show that our sequence is $\mu$-good for all $\mu < 2$. This yields the desired inequality; indeed, otherwise, choosing the minimum irregular index $n$, we get $a_{n+1} - a_{n} < (2n+1) - (2n-1) = 2$, so the sequence would not be $\mu$-good for some $\mu < 2$.

Notice that $a_{n+1}^{2} - a_{n}^{2} = a_{2n} + a_{2n+1} > 0$, so $a_{n+1} > a_{n}$ for all $n$, and hence the sequence is 0-good. Now the desired statement follows from the Claim below.

Claim. If our sequence $\left( a_{n} \right)$ is $\mu$-good for some $0 \leq \mu < 2$, then it is also $\nu$-good for $\nu = \frac{\mu}{2} + 1$.

Proof. Consider any irregular index $n$. Notice that $a_{k} - a_{n+1} \geq (k - n - 1) \mu$ for every $k > n + 1$; indeed, if all indices $n+1, n+2, \ldots, k-1$ are irregular, then this follows from $\left( a_{n} \right)$ being $\mu$-good. Otherwise, let $i$ be the maximum regular index not exceeding $k-1$. Then $$a_{k} - a_{n+1} = \left( a_{k} - a_{i+1} \right) + \left( a_{i+1} - a_{n+1} \right) \geq \mu (k - i - 1) + \bigl( (2i+1) - (2n+1) \bigr) = \mu (k - i - 1) + 2 (i - n) > \mu (k - n - 1),$$ as desired.

Therefore, $$\delta_{n} \left( 2 a_{n+1} - \delta_{n} \right) = a_{n+1}^{2} - a_{n}^{2} = a_{2n} + a_{2n+1} \geq 2 a_{n+1} + (2n-1) \mu,$$ This inequality easily yields $\delta_{n} > 1$, so in particular $a_{n+1} > 2$. Then the function $f(x) = x \left( 2 a_{n+1} - x \right)$ increases on $x \in [0, 2]$, and in order to prove $\delta_{n} \geq \nu$ it suffices to show that $f(\nu) \leq 2 a_{n+1} + (2n-1) \mu$. This inequality rewrites as $$\mu a_{n+1} - \left( \frac{\mu}{2} + 1 \right)^{2} \leq (2n-1) \mu \iff \mu \left( a_{n+1} - 2n - 1 \right) \leq \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.

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

Lemma. $\liminf\limits_{n \rightarrow \infty} \frac{a_{n}}{2n-1} \geq 1$

Proof. Let $A$ denote this limit inferior. Clearly, the sequence is monotonically increasing. Then $a_{n}^{2} = a_{1} + a_{2} + \cdots + a_{2n-1} \geq n a_{n}$, hence $A \geq \frac{1}{2} > 0$.

Let $\varepsilon > 0$. We know that $a_{n} \geq (A - \varepsilon)(2n-1)$ for all sufficiently large $n$. Then, from the inequality $$a_{n}^{2} = a_{1} + a_{2} + \cdots + a_{2n-1} \geq (A - \varepsilon)(1 + 3 + \ldots + 4n - 3) + O(1) = (A - \varepsilon)(2n-1)^{2} + O(1)$$ we obtain $A^{2} \geq A - \varepsilon$. Letting $\varepsilon$ tend to zero, we get $A \geq 1$.

Let us make the substitution $b_{n} = a_{n} - (2n-1)$. The recurrence relation takes the form $$b_{n} \left( b_{n} + 2 (2n-1) \right) = b_{1} + \ldots + b_{2n-1},$$ and the lemma implies that $\liminf\limits_{n \rightarrow \infty} \frac{b_{n}}{2n-1} \geq 0$. Consider $B = \inf\limits_{n} \frac{b_{n}}{2n-1}$. If $B < 0$, then the infimum is attained at some $k \in \mathbb{N}$, i.e. $b_{k} = B (2k-1)$ (otherwise we get a contradiction with the lemma). Then $$B (B+2)(2k-1)^{2} = b_{k} \left( b_{k} + 2 (2k-1) \right) = b_{1} + \ldots + b_{2k-1} > B (1 + 3 + \ldots + 4k - 3) = B (2k-1)^{2}.$$ This yields $B < -1$. On the other hand, $a_{n} > 0$ implies $B > -1$ and we get a contradiction.

(by Dan Carmon) Begin with observing $a_{1} = a_{1}^{2}$, so $a_{1} = 1$ from positivity. It follows that $a_{n}^{2} = \sum_{i=1}^{2n-1} a_{i} \geq a_{1} = 1$ so $a_{n} \geq 1 = (2n-1)^{0}$ for every $n$. Applying the same technique again gives $a_{n}^{2} = \sum_{i=1}^{2n-1} a_{i} \geq 2n-1$ so $a_{n} \geq \sqrt{2n-1} = (2n-1)^{1/2}$. Applying this technique again and again, we will prove the following claim by induction on $m$:

Claim. Let $m \geq 0$, and set $c_{m} = 1 - 2^{-m}$. Then there is a constant $C_{m} > 0$ such that $a_{n} \geq C_{m} (2n-1)^{c_{m}}$ for all $n \geq 1$.

Moreover, we will get a recurrence relation for $C_{m}$, and show that $\lim_{m \rightarrow \infty} C_{m} = 1$. It would follow that $a_{n} \geq \lim_{m \rightarrow \infty} C_{m} (2n-1)^{c_{m}} = 2n-1$, as we are asked to show.

Proof. We have already established the $m = 0, 1$ $\left( c_{0} = 0, c_{1} = 1/2 \right)$ with $C_{0} = C_{1} = 1$. Let $m \geq 1$ and suppose $a_{n} \geq C_{m} (2n-1)^{c_{m}}$ for every $n$. Write $c = c_{m}$ and $C = C_{m}$ for brevity. Since $c < 1$, the function $x^{c}$ is concave, and therefore have

$x^{c} \geq \frac{1}{2} \int_{x-1}^{x+1} t^{c} \, d t$. Thus $$\begin{aligned} a_{n}^{2} & = \sum_{k=1}^{2n-1} a_{k} \geq C \sum_{k=1}^{2n-1} (2k-1)^{c} \geq \frac{C}{2} \sum_{k=1}^{2n-1} \int_{2k-2}^{2k} t^{c} \, d t = \frac{C}{2} \int_{0}^{4n-2} t^{c} \, d t = \frac{C}{2} \frac{(4n-2)^{c+1}}{c+1} \\ & = \frac{2^{c} C}{1+c} (2n-1)^{1+c}. \end{aligned}$$ Recall $c = c_{m} = 1 - 2^{-m}$ hence $\frac{1+c}{2} = c_{m+1}$. Taking the square root of the above inequality yields $$\begin{equation} a_{n} \geq \sqrt{\frac{2^{-2^{-m}}}{1 - 2^{-m-1}} C_{m}} \cdot (2n-1)^{c_{m+1}} \tag{1} \end{equation}$$ Which completes the inductions step for $C_{m+1} = \sqrt{B_{m} C_{m}}$, where $B_{m} = \frac{2^{-2^{-m}}}{1 - 2^{-m-1}}$.

Observe that $B_{m} \rightarrow 1$ as $m \rightarrow \infty$ (since $2^{-m} \rightarrow 0$), and the sequence $C_{m}$ is obtained by repeatedly averaging (geometrically) the previous term with the terms of $B_{m}$. It is well known (a standard exercise in calculus 1) that this implies $C_{m}$ also converges and to the same limit as $B_{m}$, as we claimed. This can be shown directly by limits calculus; another method is to apply Cesáro's theorem on

geometric means to the sequence $D_{k}$ defined by $D_{1} = C_{1}$, $D_{k} = B_{\left\lceil \log_{2}(k) \right\rceil}$ (i.e. the first elements are $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 $B_{m}$, and each $C_{m}$ is just the geometric mean of the first $2^{m-1}$ elements of $D_{k}$.