Limit of a sequence in $\mathbb{R}^3$ given by $x_{n+1}=\sqrt{x_n(y_n+z_n-x_n)}$, etc.

sequences-and-series

Someone else asked me this, so unfortunately I do not know its context. Put $(x_0,y_0,z_0)=(1,2,\sqrt{7})$. Recursively define
\begin{align}
x_{n+1}&=\sqrt{x_n(y_n+z_n-x_n)}\,, \\
y_{n+1}&=\sqrt{y_n(z_n+x_n-y_n)}\,, \\
z_{n+1}&=\sqrt{z_n(x_n+y_n-z_n)}\,.
\end{align}
Prove that the sequences $(x_n)_{n\in\mathbb{N}}$, $(y_n)_{n\in\mathbb{N}}$ and $(z_n)_{n\in\mathbb{N}}$ converge, and find their limits.

My attempt:

Note that
\begin{align}
y_{n+1}z_{n+1}=\sqrt{y_nz_n(z_n+x_n-y_n)(x_n+y_n-z_n)}=\sqrt{y_nz_n[x_n^2-(y_n-z_n)^2]}\,.
\end{align}
Hence $(y_n-z_n)^2<x_n^2<(y_n+z_n)^2$ implies $(y_{n+1}-z_{n+1})^2<x_{n+1}^2<(y_{n+1}+z_{n+1})^2$. The same is true if $x,y,z$ are permuted. By induction, all $x_n,y_n,z_n$ are well-defined.

Put $u_n=(x_n,y_n,z_n)$ for each $n$. Then
\begin{align}
\|u_n\|^2-\|u_{n+1}\|^2=2[(x_n-y_n)^2+(y_n-z_n)^2+(z_n-x_n)^2]\geq 0\,,
\end{align}
as a decreasing sequence, $\|u_n\|\to\sqrt{3}\cdot\alpha$ as $n\to\infty$ for some $\alpha\geq 0$. The distance from $u_n$ to the line $\ell$ given by $x=y=z$ is
\begin{align}
d(u_n,\ell)=\sqrt{\frac{2}{3}[(x_n-y_n)^2+(y_n-z_n)^2+(z_n-x_n)^2]}\,,
\end{align}
which converges to $0$ as $n\to\infty$. Hence $u_n\to(\alpha,\alpha,\alpha)$ as $n\to\infty$.

What I cannot find analytically is the limit of $(u_n)_{n\in\mathbb{N}}$. Numerical computation shows that $\alpha$ should be $\sqrt{2}$. However, $\alpha$ is dependent on the choice of $u_0$, whereas the method above does not.

Best Answer

I suspected something deeper was going on. Indeed, if we just substitute $L$ into the recursions, we get trivial equations. So clearly we can't work our way out that easily!

I've often seen situations where invariants come in useful. Given a sequence $x_n$, a function $f$ such that $f(x_n) = f(x_{n+1})$ for all $n$ is called an invariant of the sequence.

The key thing, is that if $f$ is continuous then $f(x_0) = f(x_1)=\ldots = f(\lim_{n \to \infty} x_n)$, and therefore we may be able to use the nature of preimages of $f$ to calculate our answer.

The first thing I did was write Python code to simulate the situation. I just took some arbitrary $a,b,c$ here.

from math import *

def checkone() :

a = 3

b = 7

c = sqrt(61)

for i in range(100) :

    d = a

    e = b

    f = c

    a = sqrt(d*(f+e-d))

    b = sqrt(e*(f+d-e))

    c = sqrt(f*(d+e-f))

    print(str([a,b,c]) + ","+str(a**4+b**4+c**4))

checkone()

where I used the $a^4+b^4+c^4$ term to predict that something was going on with the fourth powers of the sequence. I noticed this fourth-power pattern when I saw that we would need to play with quadratics of $x_n^2$, which due to the nature of the RHS (the fact that $x_{n+1}^2 = sth. x^2 + sth. x_ny_n $ etc.) meant that I'd have to go a square further.

Call $(L(a,b,c),L(a,b,c),L(a,b,c))$ as the limit obtained from the above. Following some playing around, I first came to the conclusion that : $$ 3L^4(a,b,\sqrt{a^2+b^2}) = 4a^2b^2 $$ (note : I actually used the homogeniety of the relation and realized that it was enough to take $a=1$, so this simplified things) and then by perturbation to the conclusion: $$ 3L^4(a,b,\sqrt{a^2+b^2-c}) = 4a^2b^2-c^2 $$ This then tells me what the limit should be , following a change of subject: $$ 3L^4(a,b,x) = 2(a^2b^2+b^2x^2+x^2a^2) - a^4-b^4-x^4 \\ $$

Now comes the wonderful idea : That quantity, right there on the RHS, is actually invariant.

Suppose that $x_n,y_n,z_n$ are defined as given. Then : $$ 2(x_{n+1}^2y_{n+1}^2+x_{n+1}^2z_{n+1}^2+y_{n+1}^2z_{n+1}^2) - x_{n+1}^4-y_{n+1}^4-z_{n+1}^4\\ = 2(x_n^2y_n^2+y_n^2z_n^2+z_n^2x_n^2)-x_n^4-y_n^4-z_n^4 $$

This is a non-routine but fairly ok check to make. So you substitute the recursion where required and make sure things simplify.

Once we make this check, we note that we can, obviously by induction, obtain the statement :

$$ 2(x_{n}^2y_{n}^2+x_{n}^2z_{n}^2+y_{n}^2z_{n}^2) - x_{n}^4-y_{n}^4-z_{n}^4\\ = 2(x_0^2y_0^2+y_0^2z_0^2+z_0^2x_0^2)-x_0^4-y_0^4-z_0^4 $$

for all $n \geq 1$. Now, the splendid work of the OP has proved that the sequence converges to a limit $(\alpha,\alpha,\alpha)$.

But now, we may take the limit on both sides of the recursion. Indeed, note that if we do so then we get : $$ 3L(x_0,y_0,z_0)^4 = 2(x_0^2y_0^2+y_0^2z_0^2+z_0^2x_0^2)-x_0^4-y_0^4-z_0^4 $$ and therefore : $$ \boxed{ L(x_0,y_0,z_0) = \sqrt[4]{\frac{2(x_0^2y_0^2+y_0^2z_0^2+z_0^2x_0^2)-x_0^4-y_0^4-z_0^4}{3}} } $$

which gives the correct answer for the case above.

So find invariants, is the lesson. Don't ask me how I'd do this without computing power, though!

Related Question