# $\sqrt{c+\sqrt{c+\sqrt{c+\cdots}}}$, or the limit of the sequence $x_{n+1} = \sqrt{c+x_n}$

(Fitzpatrick Advanced Calculus 2e, Sec. 2.4 #12)

For $c \gt 0$, consider the quadratic equation $x^2 - x - c = 0, x > 0$.

Define the sequence $\{x_n\}$ recursively by fixing $|x_1| \lt c$ and then, if $n$ is an index for which $x_n$ has been defined, defining

$$x_{n+1} = \sqrt{c+x_n}$$

Prove that the sequence $\{x_n\}$ converges monotonically to the solution of the above equation.

Note: The answers below might assume $x_1 \gt 0$, but they still work, as we have $x_3 \gt 0$.

This is being repurposed in an effort to cut down on duplicates, see here: Coping with abstract duplicate questions.

and here: List of abstract duplicates.

• I have noted that the recursive definition of $\{x_n\}$ is identical to the first equation if $x_{n+1} = x_n$, so is it sufficient to show that $\{x_n\}$ is monotonic and that $x_{n+1}$ converges to $x_n$? And how would I go about doing this? – cnuulhu Mar 2 '12 at 0:32
• Clearly a solution of that equation would be a fixed point of $x\mapsto \sqrt{c+x}$. So I'd look at criteria for when a fixed point is attractive. – Michael Hardy Mar 2 '12 at 0:39
• What do you mean by ‘$x_{n+1}$ converges to $x_n$’? – Brian M. Scott Mar 2 '12 at 0:49
• Sorry, that wasn't remotely clear. I mean, $\lim_{n \to \infty}|x_{n+1}-x_n| = 0$ – cnuulhu Mar 2 '12 at 0:59
• I guessed that that was what you meant, but I figured that it was best to be sure. You’ve the right feel for what’s going on, but the details take a bit of work: see my answer. (By the way, it would be better to edit your question to include the information in your first comment, so as to make it self-contained.) – Brian M. Scott Mar 2 '12 at 1:20

Assuming that you know that a monotone, bounded sequence converges, you want to do two things. First, show that $\langle x_n:n\in\mathbb{Z}^+\rangle$ is monotone and bounded, and then show that its limit is the positive root of $x^2-x-c=0$.

If $c=x_1=1$, $x_2=\sqrt2>x_1$, while if $c=1$ and $x_1=2$, $x_2=\sqrt3<x_1$, so if the sequence is monotonic, the direction in which it’s monotonic must depend on $c$ and $x_1$. A good first step would be to try to figure out how this dependence works.

The positive root of the quadratic is $\frac12(1+\sqrt{1+4c})$, which I’ll denote by $r$. If $x_n\to r$, as claimed, and does so monotonically, it must be the case that the sequence increases monotonically if $x_1<r$ and decreases monotonically if $x_1>r$. In the examples in the last paragraph, $r=\frac12(1+\sqrt5)\approx 1.618$, so they behave as predicted.

This suggests that your first step should be to show that if $x_n<r$, then $x_n<x_{n+1}<r$, while if $x_n>r$, $x_n>x_{n+1}>r$; that would be enough to show that $\langle x_n:n\in\mathbb{Z}^+\rangle$ is both monotone and bounded and hence that it has a limit.

Suppose that $0\le x_n<r$; you can easily check that $x_n^2-x_n-c<0$, i.e., that $x_n^2<x_n+c$. On the other hand, $x_{n+1}^2=c+x_n$, so $x_{n+1}^2>x_n^2$, and therefore $x_{n+1}>x_n$. Is it possible that $x_{n+1}\ge r$? That would require that $x_{n+1}^2-x_{n+1}-c\ge 0$ (why?) and hence that $$x_{n+1}^2\ge x_{n+1}+c>x_n+c=x_{n+1}^2\;,$$ which is clearly impossible. Thus, if $0\le x_n<r$, we must have $x_n<x_{n+1}<r$, as desired. I leave the case $x_n>r$ to you.

Once this is done, you still have to show that the limit of the sequence really is $r$. Let $f(x)=\sqrt{c+x}$; clearly $f$ is continuous, so if the sequence converges to $L$, we have $$L=\lim_{n\to\infty}x_n=\lim_{n\to\infty}x_{n+1}=\lim_{n\to\infty}f(x_n)=f(L)\;,$$ and from there it’s trivial to check that $L=r$.

Added: Note that although the problem gave us $x_1>0$, this isn’t actually necessary: all that’s needed is that $x_1\ge -c$, so that $x_2$ is defined, since $x_2=\sqrt{c+x_1}\ge 0$ automatically.

• If possible, can you also edit your answer to include the case $-c \le x_n \le 0$ (if not already sufficient)? – Aryabhata Mar 2 '12 at 1:48
• @Aryabhata: That case never arises: we’re given that $c$ and $x_1$ are positive. – Brian M. Scott Mar 2 '12 at 1:54
• I know. I just want the answer to cater to the case when $x_1 \lt 0$. I am trying to get this to be one of the abstract parents. See my edits to the question. So it would be great if you can do it (if not, I will edit your answer later). (It is a simple noting that $x_2 \gt 0$ and rest of the argument works, I suppose) – Aryabhata Mar 2 '12 at 1:56
• @Aryabhata: Now I understand. Done. – Brian M. Scott Mar 2 '12 at 2:18

Let $k$ be the positive root to your polynomial. Note that $y=x^2-x-c$ is an upward opening parabola with its vertex below the $x$-axis and an initial downward slope. This implies that positive $x$-values less than $k$ produce negative output, while $x$-values greater than $k$ produce positive output.

Note also that all $x_n$ are positive, so it will be acceptable to preserve equalities and inequalities involving $x_n^2$ after taking a square root.

If $x_0=k$, then $x_1^2=c+k=k^2$, so $x_1=k$. The sequence continues like this, and is constant.

If $x_n<k$, then $x_{n+1}^2=c+x_n<c+k=k^2$. So $x_{n+1}<k$. (Similarly if $x_n>k$, then $x_{n+1}>k$.) This establishes that the sequence is either bounded above or below, depending on where $x_0$ is in relation to $k$.

If $x_n<k$, then $x$ is a positive number to the left of the root of your polynomial. $x$-values in this region produce negative output, so $x_n^2-x_n-c<0$. That implies that $x_{n+1}^2=c+x_n>x_n^2$, and so $x_{n+1}>x_n$. (Similarly if $x_n>k$, then $x_{n+1}<x_n$.)

Thus if $x_0<k$ you will have an increasing sequence bounded above. And if $x_0>k$ you will have a decreasing sequence bounded below.

So the limit exists under all possible cases. It's value has to be a solution to $L=\sqrt{c+L}$. There is only one such solution: $L=k$.

Let $r=\frac {1+\sqrt {1+4c}}2$ be the positive root of the quadratic, so that $r^2=r+c$ and $r\gt 1$

Note that for $n\gt 1$ we have $x_n\gt 0$

Now suppose $r\gt x_n$ so with $x_{n+1}^2=c+x_n$ we have $$r^2-x_{n+1}^2=(r+c)-(c+x_n)=r-x_n\gt 0$$and $$r-x_{n+1}=\frac {r-x_n}{r+x_{n+1}}\lt r-x_n$$

Whence $x_n$ is monotonically increasing, and getting closer to $r$ - the difference reduces at least as fast as $r^{-n}$, so the limit is easy to prove.

On the other hand if $r\lt x_n$ we have $$x_{n+1}^2-r^2=(c+x_n)-(r+c)=x_n-r\gt 0$$and $$x_{n+1}-r=\frac {x_n-r}{x_{n+1}+r}\lt x_n-r$$and the sequence is decreasing and bounded below by $r$, and it is once again easy to prove that this is the limit.

I am going to do this Ramanujan-style: pick some real positive $$a$$. $$a=\sqrt{a^2}=\sqrt{a^2-a+a}=\sqrt{a^2-a+\sqrt{a^2-a+a}}=\sqrt{a^2-a+\sqrt{a^2-a+\sqrt{a^2-a+a}}}=\dots=\sqrt{a^2-a+\sqrt{a^2-a+\sqrt{a^2-a+\sqrt{a^2-a+\dots}}}}$$ What you do is keep replacing the last $$a$$ in the expression by $$\sqrt{a^2-a+a}$$.

Now let $$a^2-a=c$$ and we have the given expression. Solve that for $$a$$ and you have your answer.

• This is cute but not rigorous. The definition of the "infinite radical" is as the limit of a certain sequence described in the question. The equations you have written can probably be used to prove that such a limit is $a$ but that is not obvious and definitely takes some work. – Eric Wofsey Dec 12 '18 at 6:12
• Why it's not rigorous? If you have a sequence with all terms equal to $a$ what is the limit of the sequence? – plus1 Dec 13 '18 at 8:35
• Your sequence is not the same as the sequence defined in the question, unless $x_1=a$. – Eric Wofsey Dec 13 '18 at 16:22
• @EricWofsey just define it as $x = \sqrt{a^2-a+x}$. This is rigorous enough. – Mr Pie Feb 23 '20 at 23:55
• @MrPie: But that is not the definition used in this question. – Eric Wofsey Feb 24 '20 at 0:26

Hint on methodology:

Denoting $$f(x)=\sqrt{c+x}$$ the function that defines the recursive sequence, you can show the sequence is increasing (resp.decreasing) by showing that all its terms live in an interval $$I$$ such that $$f(x)>x \quad(\text{resp.}\;f(x) To show that all terms of the sequence live in $$I$$, you just have to show that $$f(I)\subseteq I$$.

Last point: all terms are obviously positive. On the other hand, as $$f$$ is continuous, if a limit $$\ell$$ exists, it satisfies the equation $$f(x)=\sqrt{c+x}=x\iff x^2-x-c=0,\quad x>0$$ This quadratic equation has a negative and a positive root: $$\;\dfrac{1\pm \sqrt{1+4c}}2$$. Therefore, if the sequence converges, its limit is the positive root $$\lambda$$, and you can try to show that $$f\bigl([0,\lambda]\bigr)\subseteq[0,\lambda]\quad\text{and}\quad f(x)>x\enspace\text{on }\; [0,\lambda].$$