IMC 2002 · Day 1 · P6

Lemma 1. Let $(a_n)_{n \ge 0}$ be a sequence of non-negative numbers such that $a_{2k} - a_{2k+1} \le a_k^2$, $a_{2k+1} - a_{2k+2} \le a_k a_{k+1}$ for any $k \ge 0$ and $\limsup n a_n < 1/4$. Then $\limsup \sqrt[n]{a_n} < 1$.

Proof. Let $c_l = \sup_{n \ge 2^l} (n+1) a_n$ for $l \ge 0$. We will show that $c_{l+1} \le 4 c_l^2$. Indeed, for any integer $n \ge 2^{l+1}$ there exists an integer $k \ge 2^l$ such that $n = 2k$ or $n = 2k+1$. In the first case there is $a_{2k} - a_{2k+1} \le a_k^2 \le \frac{c_l^2}{(k+1)^2} \le \frac{4 c_l^2}{(2k+1)(2k+2)}$, whereas in the second case there is $a_{2k+1} - a_{2k+2} \le a_k a_{k+1} \le \frac{c_l^2}{(k+1)(k+2)} \le \frac{4 c_l^2}{(2k+2)(2k+3)}$.

Hence a sequence $\left( a_n - \frac{4 c_l^2}{n+1} \right)_{n \ge 2^{l+1}}$ is non-decreasing and its terms are non-positive since it converges to zero. Therefore $a_n \le \frac{4 c_l^2}{n+1}$ for $n \ge 2^{l+1}$, meaning that $c_{l+1} \le 4 c_l^2$. This implies that a sequence $((4 c_l)^{2^{-l}})_{l \ge 0}$ is non-increasing and therefore bounded from above by some number $q \in (0,1)$ since all its terms except finitely many are less than 1. Hence $c_l \le q^{2^l}$ for $l$ large enough. For any $n$ between $2^l$ and $2^{l+1}$ there is $a_n \le \frac{c_l}{n+1} \le q^{2^l} \le (\sqrt{q})^n$ yielding $\limsup \sqrt[n]{a_n} \le \sqrt{q} < 1$, yielding $\limsup \sqrt[n]{a_n} \le \sqrt{q} < 1$,

which ends the proof.

Lemma 2. Let $T$ be a linear map from $\mathbb{R}^n$ into itself. Assume that $\limsup n \|T^{n+1} - T^n\| < 1/4$. Then $\limsup \|T^{n+1} - T^n\|^{1/n} < 1$. In particular $T^n$ converges in the operator norm and $T$ is power bounded.

Proof. Put $a_n = \|T^{n+1} - T^n\|$. Observe that $$T^{k+m+1} - T^{k+m} = (T^{k+m+2} - T^{k+m+1}) - (T^{k+1} - T^k)(T^{m+1} - T^m)$$ implying that $a_{k+m} \le a_{k+m+1} + a_k a_m$. Therefore the sequence $(a_m)_{m \ge 0}$ satisfies assumptions of Lemma 1 and the assertion of Proposition 1 follows.

Remarks. 1. The theorem proved above holds in the case of an operator $T$ which maps a normed space $X$ into itself, $X$ does not have to be finite dimensional.

2. The constant $1/4$ in Lemma 1 cannot be replaced by any greater number since a sequence $a_n = \frac{1}{4n}$ satisfies the inequality $a_{k+m} - a_{k+m+1} \le a_k a_m$ for any positive integers $k$ and $m$ whereas it does not have exponential decay.

3. The constant $1/4$ in Lemma 2 cannot be replaced by any number greater that $1/e$. Consider an operator $(Tf)(x) = x f(x)$ on $L_2([0,1])$. One can easily check that $\limsup \|T^{n+1} - T^n\| = 1/e$, whereas $T^n$ does not converge in the operator norm. The question whether in general $\limsup n \|T^{n+1} - T^n\| < \infty$ implies that $T$ is power bounded remains open.

Remark The problem was incorrectly stated during the competition: instead of the inequality $\|A^k - A^{k-1}\| \le \frac{1}{2002 k}$, the inequality $\|A^k - A^{k-1}\| \le \frac{1}{2002 n}$ was assumed. If $A = \begin{pmatrix} 1 & \varepsilon \\ 0 & 1 \end{pmatrix}$ then $A^k = \begin{pmatrix} 1 & k\varepsilon \\ 0 & 1 \end{pmatrix}$. Therefore $A^k - A^{k-1} = \begin{pmatrix} 0 & \varepsilon \\ 0 & 0 \end{pmatrix}$, so for sufficiently small $\varepsilon$ the condition is satisfied although the sequence $\bigl( \|A^k\| \bigr)$ is clearly unbounded.