My professor provided a solution to this problem, but it seemed very unmotivated. I am looking for a general way to approach recursively defined sequences and show their convergence. Here is the specific question. Let $x_0 = 1$. Let $x_{n+1} = \frac{x_n +2}{x_n +1}$ for $n \in \mathbb{N} \cup {0}$. Show that $x_n$ converges to $\sqrt{2}$. Edit: I should add that computing the limit as $\sqrt{2}$ wouldn't be hard if I could show that the limit in fact exists, but the only way I could think of to do that would be to show that this was a bounded increasing sequence, but the sequence isn't monotonically increasing as far as I can show.


Consider an iteration $x_{n+1} = f(x_n)$ where $f$ is some function. If $\lim_{n \to \infty} x_n = L$ and $f$ is continuous at $L$, then $L$ must be a fixed point of $f$, i.e. $f(L) = L$. Moreover, if $f$ is differentiable at $L$, $L$ is an attracting fixed point of $f$ if $|f'(L)|< 1$, while if $|f'(L)| > 1|$ it is a repelling fixed point. An attracting fixed point will be the limit of the sequence if the terms ever get close enough, while a repelling fixed point can't be the limit unless some $x_n$ happens to be exactly $L$.

One way to show that the fixed point $L$ is the limit of the sequence is to find an interval $[a,b]$ containing $L$ and such that $|f'(x)| < 1$ for all $x$ in $L$, and show that some $x_n$ is in the interval.

In your case, $f(x) = \frac{x+2}{x+1}$ has two fixed points, one attracting and one repelling.

EDIT: In this particular case, another approach is possible, since this function is a fractional linear transformation $f(x) = \frac{ax + b}{cx+d}$. For these, it turns out that $x_n = \frac{a_n x_0 + b_n}{c_n x_0 + d_n}$ where the matrix $$\pmatrix{a_n & b_n\cr c_n & d_n} = \pmatrix{a & b\cr c & d\cr}^n$$ We can then use a little linear algebra to get closed-form formulas for $x_n$. In your case, the matrix has eigenvalues $\lambda_1 = 1+\sqrt{2}$ and $\lambda_2 = 1 - \sqrt{2}$ corresponding to eigenvectors $\pmatrix{\pm \sqrt{2} \cr 1\cr}$, so that $$ \pmatrix{1 & 2\cr 1 & 1\cr}^n = \pmatrix{\sqrt{2} & -\sqrt{2}\cr 1 & 1} \pmatrix{\lambda_1^n & 0\cr 0 & \lambda_2^n} \pmatrix{ \sqrt{2} & -\sqrt{2} \cr 1 & 1\cr}^{-1} = \pmatrix{(\lambda_1^n+\lambda_2^n)/2 & \sqrt{2}(\lambda_1^n-\lambda_2^n)/2\cr \sqrt{2}(\lambda_1^n-\lambda_2^n)/4 & (\lambda_1^n + \lambda_2^n)/2} $$ Thus with $x_0 = 1$, $$ x_n = \frac{(\lambda_1^n+\lambda_2^n)/2 + \sqrt{2}(\lambda_1^n-\lambda_2^n)/2}{ \sqrt{2}(\lambda_1^n-\lambda_2^n)/4 + (\lambda_1^n + \lambda_2^n)/2} = \frac{(1+\sqrt{2})/2 + (1-\sqrt{2}) (\lambda_2/\lambda_1)^n/2}{(\sqrt{2}/4 + 1/2) + (-\sqrt{2}/4 + 1/2) (\lambda_2/\lambda_1)^n}$$ Since $|\lambda_2| < |\lambda_1|$, $(\lambda_2/\lambda_1)^n \to 0$ as $n \to \infty$, so that $$x_n \to \frac{(1+\sqrt{2})/2}{\sqrt{2}/4+1/2} = \sqrt{2}$$

  • $\begingroup$ Any way to do this without any machinery of continuity or derivation? $\endgroup$ – Nujra Nov 16 '17 at 6:46
  • $\begingroup$ @Nujra Professional mathematicians use professional tools. If you don't want to learn them, don't go looking for "a general way to approach recursively defined sequences". $\endgroup$ – Professor Vector Nov 16 '17 at 6:53

Based on the theoretical knowledge given by R.Israel for sequences $(x_n)_n$ defined by $x_{n+1}=f(x_n)$ you can also draw the graph of $y=x$ and $y=f(x)$ and notice that for $x_0=1$ the sequence $x_n$ converges to $\ell=\sqrt{2}$ in spiral.

Now, instead of going for calculating $f'$ you can try to justify these visual observations.

First note that $x\ge 1\implies f(x)\ge 1$, so since $x_0=1$ then $x_n\ge 1$ for any $n$.

Since it is a spiral convergence, we are interested in the behaviour of $x_{n+2}-x_n$.

So let's study

  • $f(f(x))-x=\dfrac{4-2x^2}{2x+3}=\underbrace{\dfrac{-2}{2x+3}}_{<0}(x^2-\ell^2)$

  • $f(x)-\ell=\underbrace{\dfrac{\sqrt{2}-1}{x+1}}_{>0}(x-\ell)$

Whose signs depends only whether $x>\ell$ or not considering we already have $x\ge 1$.

Let's define : $\begin{cases} u_n=x_{2n} & u_0=x_0=1<\ell\\v_n=x_{2n+1} & v_0=x_1=\frac 32>\ell\end{cases}\implies\begin{cases}(u_n)_n\nearrow & u_n<\ell\\(v_n)_n\searrow & v_n>\ell\end{cases}$

So both sequences are convergent and the equation $f(f(x))-x=0$ immediately confirms that this limit is common and actually $\ell$.

Yet, as you can notice, this is no easiest calculations than the $f'$ based approach, just another way to present it.


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.