Recursive sequence with square root

Question

I came across this (cool) question this weekend Find the limit of the following sequence as $n$ approaches infinity. $x_1 = 1$ and $x_{n+1} = \sqrt{x_n^2+\frac{1}{2}^n}$

I had two questions about it. I approximated it using excel to be about 1.224745. Does anyone know if there is an exact expression for what this converges to? Also, on problems like this, I normally use the fact that if a sequence converges all of its sub-sequences converge, and have the same limit. Plugging in $L$ for all of the $x_n$'s and solving didn't get me anywhere. Why does this "trick" not work here, and what other sort of recursive sequences does it fail for? What are some other methods for finding the limit in a situation like this? Thanks in advance.

Answer 1

For this particular sequence, it is easier to deal with $x_n^2$ as

$$x_{n+1}^2 = x_n^2 + \frac{1}{2^n}.$$

Thus

$$\lim_{n\to \infty} x_n^2 = \left(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} +\cdots \right)= 2$$

Thus

$$\lim_{n\to \infty} x_n = \sqrt{\lim_{n\to \infty} x_n^2}=\sqrt{2}$$

which is not the same as what you've got. Your number looks like $\sqrt{1.5}$ to me.

Answer 2

For the limit to converge to your mentioned values, the sequence should be $x_{n+1} = \sqrt{x_n^2+\dfrac1{2^{n+1}}}$. Consider the sequence $b_n = x_n^2$. We have $b_1 = 1$ and $b_{n+1} = b_n + \dfrac1{2^{n+1}}$. This means $$b_{n+1} = 1 + \dfrac14 + \dfrac18 + \cdots + \dfrac1{2^{n+1}} = \dfrac32-\dfrac1{2^{n+1}}$$ We hence have that $$\lim_{n \to \infty} b_n = \dfrac32 \implies \lim_{n \to \infty} x_n = \sqrt{\dfrac32}$$

Answer 3

One way to see that your (often useful) trick of substituting $L$ for all the $x_i$ must fail is that it loses the information about the starting condition. To have your trick work the limit has to be independent of the starting values. The sequence is monotonically increasing, so clearly if $x_1 \gt 1.224745$, the limit will be higher. Following John's logic, the limit of your equation will be $L = \sqrt{x_1^2+1}$ but I suspect your Excel sheet missed the $1/2$ term and you find $L=\sqrt{x_1^2+0.5}$

Answer 4

Let $h = \dfrac 1 2$. \begin{align} x_1 &= 1\cr x_2 &= \sqrt{1 + h}\cr x_3 &= \sqrt{1 + h + h^2}\cr x_4 &= \sqrt{1 + h + h^2 + h^3}\cr &\vdots\cr x_\infty &=\sqrt{1 + h + h^2 + h^3 + h^4 + \cdots}\cr x_\infty &=\sqrt{2}\cr \end{align}

Since $1 + h + h^2 + \cdots = \dfrac{1}{1-h} = 2$