Study the convergence of a sequence $ \left( x_n\right)_{n\ge 0} $ for which $ x_0\in\mathbb{R}\setminus\mathbb{Q} , $ and $ x_{n+1}\in \left\{ \frac{x_n+1}{x_n} , \frac{x_n+2}{2x_n-1}\right\} , $ for all $ n\ge 1. $
Problem
Source: Romanian National Olympiad 2000, Grade XI, Problem 2
Tags: Sequences, real analysis
19.03.2023 22:10
BUMP!!!
24.12.2024 17:42
Let $f(x)= \frac{x+1}{x}$ and $g(x)=\frac{x+2}{2x-1}.$ Notice that $x_n= h_n \circ h_{n-1} \circ \ldots \circ h_1(x_0),$ where each $h_i$ is either $f$ or $g$. Let's denote by $k(n)$ the number of functions $h_i$ that are equal to $f$ for $i \le n.$ By direct computation, we have $f \circ g = g \circ f$ (on the domain where the compositions make sense) and $g \circ g = \mathrm{Id}$. Since $f$ and $g$ commute, we have $h_n \circ h_{n-1} \circ \ldots \circ h_1= \underbrace{f \circ f \circ \ldots \circ f}_{k(n)} \circ \underbrace{g \circ g \circ \ldots \circ g}_{n-k(n)}.$
Since $g \circ g = \mathrm{Id},$ we have $\underbrace{g \circ g \circ \ldots \circ g}_{m}= \begin{cases} g,~\text{if}~m~ \text{is odd} \\ \mathrm{Id},~\text{if}~m~ \text{is even} \end{cases}.$ Therefore $x_n = \frac{F_{k(n)+1} g(x_0) + F_{k(n)}}{F_{k(n)} g(x_0) + F_{k(n)-1}}$ if $n-k(n)$ is odd and $x_n=\frac{F_{k(n)+1}x_0+F_{k(n)}}{F_{k(n)} x_0+F_{k(n)-1}}$ otherwise. If $k(n)$ is unbounded, then both $\frac{F_{k(n)+1} g(x_0) + F_{k(n)}}{F_{k(n)} g(x_0) + F_{k(n)-1}}$ and $\frac{F_{k(n)+1}x_0+F_{k(n)}}{F_{k(n)} x_0+F_{k(n)-1}}$ converge to $\varphi$ (the golden ration), so in this case $(x_n)$ is convergent. If $k(n)$ is bounded, then it is eventually constant (because it is also increasing), say to some value $k,$ so $x_n$ will eventually alternate between $\frac{F_{k+1} g(x_0) + F_{k}}{F_{k} g(x_0) + F_{k-1}}$ and $\frac{F_{k+1}x_0+F_{k}}{F_{k} x_0+F_{k-1}}.$ In this case $(x_n)$ is convergent if and only if the last two numbers are equal, that is, if and only if $\underbrace{f \circ \ldots \circ f}_k (g(x_0)) = \underbrace{f \circ \ldots \circ f}_k (x_0),$ which, by virtue of $f$ being injective, is equivalent to $g(x_0)=x_0,$ so to $x_0 \in \left\{ \varphi, -\frac{1}{\varphi} \right\}.$ In conclusion, if $k(n)$ is unbounded, then $(x_n)$ is convergent regardless of the value of $x_0,$ and if $k(n)$ is bounded, then $(x_n)$ is convergent if and only if $x_0 \in\left\{ \varphi, -\frac{1}{\varphi} \right\}.$