## Task 5 - 271245

Let $\left(x_{n}\right)$ be the sequence defined by

$$
x_{1}=1, \quad x_{2}=1, \quad x_{n+1}=\frac{x_{n}+1}{x_{n-1}+4}
$$

$(n=2,3,4, \ldots)$.

Determine whether this sequence is convergent, and if so, find its limit.
If the sequence converges to a limit $a$, then

$$
a=\frac{a+1}{a+4}
$$

and thus $a=\frac{-3+\sqrt{13}}{2}$ must hold (the negative solution for $a$ can be excluded since all terms of the sequence are positive).

Now, proving the convergence of the sequence is not straightforward, as it is not monotonic but oscillates around $a$.

One could apply the Banach fixed-point theorem and show that the two-dimensional function corresponding to the sequence's formation rule is a contraction, which would be cumbersome and require a rather strong theorem.

Instead, we want to establish the plausible estimate $\left|x_{n}-a\right|<c \lambda^{n}$ for sufficiently large $n$ with $c>0$ and $0<\lambda<1$. We start from the inequality to be shown:

$$
\left|x_{n}-a\right|=\frac{x_{n-1}+1}{x_{n-2}+4}-a
$$

For $x_{n} > a$, we have:

$$
\frac{a+c \lambda^{n-1}+1}{a-c \lambda^{n-2}+4}-a \stackrel{?}{<} c \lambda^{n}
$$

This can be simplified to:

$$
\frac{1}{4}\left(\frac{1}{4}+4\right)-\frac{3}{2^{n}}-\frac{3}{8}-\frac{1}{2}>\frac{1}{16}+1-\frac{3}{16}-\frac{3}{8}-\frac{1}{2}=0
$$

for $n \geq 4$, which verifies the claimed inequality.

For $x_{n} \leq a$, similarly:

$$
a-\frac{a-c \lambda^{n-1}+1}{a+c \lambda^{n-2}+4} \stackrel{?}{<} c \lambda^{n}
$$

This can be simplified to:

$$
\frac{1}{4}\left(\frac{1}{4}+4\right)-\frac{3}{2^{n}}-\frac{3}{8}-\frac{1}{2}>\frac{1}{16}+1-\frac{3}{16}-\frac{3}{8}-\frac{1}{2}=0
$$

for $n \geq 4$, which verifies the claimed inequality.

Overall, we have for every $n \geq 2$ the estimate $\left|x_{n}-a\right|<c \lambda^{n}$ with $\lambda=\frac{1}{2}$ and $c=3$, which shows convergence because $c \lambda^{n} \rightarrow 0$ as $n \rightarrow \infty$. Thus, it is proven that $x_{n}$ converges to $a=\frac{-3+\sqrt{13}}{2}$.

Remark: Interestingly, one cannot easily show $\left|x_{n}-a\right|<\frac{1}{n}$ by induction, even though this is weaker than the error estimate shown in this proof (weaker because polynomials decrease more slowly than exponential functions). This is a known phenomenon that can be explained by the fact that while one wants to show something weaker, one can only assume something weaker in the induction hypothesis.