# Maximum zero converges to $\sqrt{2}$

In my research I came upon a recursively defined sequence, and I'm pretty sure it converges to $\sqrt{2}$ though I can't prove it easily. I don't think it is a difficult question but I'm not sure.

Consider the following sequence of functions over $\mathbb{R}$, where it makes sense:

$f_0(x)=0$,

$\displaystyle f_{n+1}(x)=\frac{1}{2(x-f_n(x))}\hspace{1cm}$ ($n\geq 0)$.

Now let us define the sequence $(x_n)$ by $\displaystyle x_n:=\max\left\{y\in[0,\sqrt{2}[\,:\quad y=\frac{1}{2y}+f_n(y)\right\}$.

Question: is is true that $x_n\rightarrow\sqrt{2}$ when $n\rightarrow +\infty$?

Numerical evidence strongly suggest that, and it completely makes sense with the problem it originated from. The issue is that the functions $f_n$ have more and more poles as $n$ grows, and there is no function it converges to. It looks like the set of the poles of $f_n$ tends to be dense in $[-\sqrt{2},\sqrt{2}]$ when $n\rightarrow +\infty$, and $f_n$ is always decreasing outside of the poles. The poles seem to accumulate more around $\pm\sqrt{2}$ than around $0$.

For visual reference, one can see a graph of $f_{10}$ here

Edit: I added the fact that I'm only interested in the $y\in[0,\sqrt{2}[$. I don't care what happens outside the interval since then it's trivial.

• When $x\ge\sqrt{2}$ the sequence converges to $(x-\sqrt{x^2-2})/2$, – Henri Cohen Dec 7 '17 at 17:38
• All you need to know is that $f_n$ are continuous above $\sqrt 2$ and stay above $0$ and below $1/\sqrt 2$ there (so there is no chance to get $y>\sqrt 2$) and that the rightmost pole of $f_n$ tends to $\sqrt 2$, which follows from the inequality $f_{n+1}(x)\ge \frac 2{x^2}f_n(x)$ valid any time when $0<f_n(x)<x$ (so the IVT gives you $y$ somewhere between that last pole and $\sqrt 2$). It is a little bit more interesting to find the asymptotics of $\sqrt 2-x_n$ as $n\to\infty$, but since you didn't ask for that, I'll stop here. . – fedja Dec 7 '17 at 18:11

Modify the function so the equation becomes $f_n(x)=0$. That is

$$f_0(x)=\frac{1}{2 x}-x \quad\quad\quad f_n(x)=\frac{1}{2 \left(\frac{1}{2 x}-f_{n-1}(x)\right)}-x+\frac{1}{2 x}$$

Multiply both side of the equation by $-U_n(\sqrt{1/2}x)x$

$$f_0(x)=-U_0(\sqrt{1/2}x)x\left(\frac{1}{2 x}-x\right) \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{ } \\ f_n(x)=-U_n(\sqrt{1/2}x)x\left(\frac{1}{2 \left(\frac{1}{2 x}-\frac{f_{n-1}(x)}{-U_{n-1}(\sqrt{1/2}x)x}\right)}-x+\frac{1}{2 x}\right)$$

Substitute $x\to\sqrt{2}x$ and make common denominator

$$f_0(x)=U_2(x) \quad\quad\quad f_n(x)=\frac{U_n(x) \left(\left(1-4 x^2\right) f_{n-1}(x)+U_{n-1}(x)\right)}{f_{n-1}(x)+U_{n-1}(x)}$$

Replace $f_{n-1}$ by $U_{n+1}(x)$ which is valid for $n=1$ and hopefully more. Also replace $U_{n-1}(x)$ using the recurrence relation for $U_{n+1}(x)$, and expand

$$f_0(x)=U_2(x) \quad\quad\quad f_n(x)=\frac{U_n(x) \left(\left(1-4 x^2\right) U_{n+1}(x)+2 x U_n(x)-U_{n+1}(x)\right)}{U_{n+1}(x)+2 x U_n(x)-U_{n+1}(x)} \\f_0(x)=U_2(x) \quad\quad\quad f_n(x)=U_n(x)-2 x U_{n+1}(x)= U_{n+2}(x)\hspace{3.8cm}\text{ }$$

Now it's obvious that the maximal root approaches 1 which correspond to $\sqrt{2}$ because of the substitution.

The multiplication just cancel out singularities, but even if it did introduce additional roots, these would be in the range $(0,1)$ which doesn't affect the limit of the maximal root.

• Thank you for your answer. What is $U-n$ in your proof ? Can you give an explicit definition please ? – elie520 Dec 7 '17 at 18:15
• @elie520 U is the second kind chebyshev polynomial defined by $U_0(x)=1,U_1(x)=2x,U_{n+1}(x)=2xU_n(x)-U_{n-1}(x)$ – Coolwater Dec 7 '17 at 18:18

No need for any analysis: the roots are roots of shifted Tchebyshev polynomials, all of the form $\sqrt{2}\cos(\pi/(2k))$ for suitable $k$ in arithmetic progression.

You have $f_n(x)=g_x^n(0)$, where $g_x(y)=1/(2(x-y))$. The fixed points of $g_x$ are $\alpha_x=(x+\sqrt{x^2-2})/2$ and $\beta_x=(x-\sqrt{x^2-2})/2$. If we put $m_x(y)=(y-\alpha_x)/(y-\beta_x)$ and $$\gamma_x=\frac{\alpha_x}{\beta_x}=x^2-1+x\sqrt{x^2-2}$$ we find that $g_x(y)=m_x^{-1}(\gamma_x\,m_x(y))$. This gives $$f_n(x) = m_x^{-1}(\gamma_x^n\,m_x(0)) = m_x^{-1}(\gamma_x^{n+1}).$$ You want $f_n(y)=y-1/(2y)$ or equivalently $\gamma_y^{n+1}=m_y(y-1/(2y))$. However, one can check that $m_y(1-1/(2y))=\gamma_y^{-2}$, so you want $\gamma_y^{n+3}=1$. For $y>\sqrt{2}$ one can check that $\gamma_y$ is real and strictly greater than $1$, so there are no solutions, as required.

• This proves only that $x_n<\sqrt 2$. The OP asked for a little bit more than that. However, don't waste your time on corrections: the problem is trivial anyway (see my remark) :-) – fedja Dec 7 '17 at 18:18