IMC 2024 · Day 2 · P8

Hint: Prove that $2 x_n \le x_{n+1} \le 2 x_n + n$.

Let's prove by induction that $x_{n+1} \ge 2 x_n$. It holds for $n = 1$. Assume it holds for $n$. Then by the induction hypothesis we have that $x_n \ge 2 x_{n-1} \ge \dots \ge 2^{n-1} x_1 > 0$ and $$x_{n+2} = 2 x_{n+1} + (x_{n+1} - 2 x_n) + \frac{2^n}{x_n} > 2 x_{n+1}.$$ Similarly we prove that $x_{n+1} \le 2 x_n + n$. Again it holds for $n = 1$. Assume that the inequality holds for $n$. Then using that $x_n \ge 2^n$ and the induction hypothesis we obtain $$x_{n+2} \le 3 x_{n+1} - 2 x_n + 1 \le 2 x_{n+1} + (2 x_n + n) - 2 x_n + 1 = 2 x_{n+1} + n + 1.$$ Using the previous inequalities we obtain that the sequence $y_n = \dfrac{x_n}{2^n}$ is increasing and $y_{n+1} \le y_n + \dfrac{n}{2^n} \le \dots \le y_1 + \sum\limits_{k=1}^{n} \dfrac{k}{2^k} < \infty$, thus $\lim\limits_{n \to \infty} y_n = c$ exists.

The recurrence relation has the following form for $y_n$: $$4 y_{n+2} - 2 y_{n+1} = 4 y_{n+1} - 2 y_n + \frac{1}{2^n \cdot y_n}.$$ By summing up the above equality for $n = 1, \dots, m$ we obtain $$\tag{1} 4 y_{m+2} - 2 y_{m+1} = 4 y_2 - 2 y_1 + \sum_{n=1}^{m} \frac{1}{2^n \cdot y_n} = 2 + \sum_{n=1}^{m} \frac{1}{2^n \cdot y_n}.$$ Now using the facts that $y_1 = 1$, $y_n$ increases and $\lim\limits_{n \to \infty} y_n = c$ we obtain $1 \le y_n \le c$. Hence $$\frac1c \le \sum_{n=1}^{\infty} \frac{1}{2^n \cdot y_n} \le 1.$$ Thus we get from (1) $$2c = \lim_{m \to \infty} (4 y_{m+2} - 2 y_{m+1}) = 2 + \sum_{n=1}^{\infty} \frac{1}{2^n \cdot y_n} \in \left[ 2 + \frac1c, 3 \right].$$ So we have $2c^2 \ge 2c + 1$ and $2c \le 3$. Recall that $c \ge 1$. Therefore $1 + \sqrt{3} \le 2c \le 3$, which finishes the proof.