International Mathematics Competition
for University Students
2024

IMC2024: Day 2, Problem 8

Problem 8. Define the sequence $\displaystyle x_1,x_2,\ldots$ by the initial terms $\displaystyle x_1=2$, $\displaystyle x_2=4$, and the recurrence relation

$\displaystyle x_{n+2}=3x_{n+1}-2x_n+\frac{2^ n}{x_n}\quad\text{for }n\geq 1.$

Prove that $\displaystyle \displaystyle\lim\limits_{n \to \infty}\frac{x_n}{2^ n}$ exists and satisfies

$\displaystyle \frac{1+\sqrt{3}}{2}\leq\lim\limits_{n \to \infty}\dfrac{x_n}{2^ n}\leq\frac{3}{2}.$

Karen Keryan, Yerevan State University & American University of Armenia, Armenia

Solution. Let's prove by induction that $\displaystyle x_{n+1}\geq 2x_n$. It holds for $\displaystyle n=1$. Assume it holds for $\displaystyle n$. Then by the induction hypothesis we have that $\displaystyle x_n\geq 2x_{n-1}\geq\ldots\geq 2^{n-1}x_1>0$ and

$\displaystyle x_{n+2} = 2x_{n+1} + (x_{n+1}-2x_n) + \frac{2^n}{x_n} > 2x_{n+1}.$

Similarly we prove that $\displaystyle x_{n+1}\leq 2x_n+n$. Again it holds for $\displaystyle n=1$. Assume that the inequality holds for $\displaystyle n$. Then using that $\displaystyle x_n\geq 2^n$ and the induction hypothesis we obtain

$\displaystyle x_{n+2}\leq 3x_{n+1}-2x_n+1\leq2x_{n+1}+(2x_n+n)-2x_n+1= 2x_{n+1}+n+1 .$

Using the previous inequalities we obtain that the sequence $\displaystyle y_n=\dfrac{x_n}{2^ n}$ is increasing and $\displaystyle y_{n+1}\leq y_{n}+\frac{n}{2^n}\leq\ldots\leq y_1+\sum_{k=1}^n\frac{k}{2^k}<\infty$, thus $\displaystyle \lim\limits_{n \to \infty}y_n=\dfrac{x_n}{2^ n}=c$ exists.

The recurrence relation has the following form for $\displaystyle y_n$:

$\displaystyle 4y_{n+2}-2y_{n+1}=4y_{n+1}-2y_n+\frac1{2^ n\cdot y_n}.$

By summing up the above equality for $\displaystyle n=1,\ldots,m$ we obtain

Now using the facts that $\displaystyle y_1=1$, $\displaystyle y_n$ increases and $\displaystyle \lim_{n\to\infty}y_n=c$ we obtain $\displaystyle 1\leq y_n\leq c$. Hence

$\displaystyle \frac1c\leq \sum_{n=1}^\infty\frac1{2^ n\cdot y_n}\leq 1.$

Thus we get from (1)

$\displaystyle 2c=\lim_{m\to\infty}(4y_{m+2}-2y_{m+1})=2+\sum_{n=1}^\infty\frac1{2^ n\cdot y_n}\in \left[2+\frac{1}{c},3\right].$

So we have $\displaystyle 2c^2\geq 2c+1$ and $\displaystyle 2c\leq 3$. Recall that $\displaystyle c\geq 1$. Therefore $\displaystyle 1+\sqrt3\leq 2c\leq 3,$ which finishes the proof.