9
$\begingroup$

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

In advance, thank you for your interest/time.

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.

$\endgroup$
  • $\begingroup$ When $x\ge\sqrt{2}$ the sequence converges to $(x-\sqrt{x^2-2})/2$, $\endgroup$ – Henri Cohen Dec 7 '17 at 17:38
  • 4
    $\begingroup$ 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. . $\endgroup$ – fedja Dec 7 '17 at 18:11
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for your answer. What is $U-n$ in your proof ? Can you give an explicit definition please ? $\endgroup$ – elie520 Dec 7 '17 at 18:15
  • $\begingroup$ @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)$ $\endgroup$ – Coolwater Dec 7 '17 at 18:18
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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) :-) $\endgroup$ – fedja Dec 7 '17 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.