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

\(\displaystyle 4y_{m+2}-2y_{m+1}=4y_{2}-2y_1+\sum_{n=1}^m\frac1{2^ n\cdot y_n}=2+\sum_{n=1}^m\frac1{2^ n\cdot y_n}. \)

\(\displaystyle (1) \)

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.