# Show that the sequence ${a_n}$ converges where $a_n = \sqrt{1+\sqrt{2+\sqrt{3+\cdots+\sqrt{n}}}}$ for $n\geq 1$.

The original question was to determine whether the sequence converges, but I have checked for extremely high values of $n$ and it seems as though it does converge. This lead me to wonder if there was an "easy" method of showing that the sequence is bounded (since it is monotone, it then follows that it converges). Thanks.

By repeatedly rationalizing the numerators and using that $a_n\geq1$ for all $n$, $$a_{n+1}-a_n=\frac{\sqrt{2+\sqrt{3+\cdots\sqrt{n+1}}}-\sqrt{2+\sqrt{3+\cdots\sqrt{n}}}}{a_{n+1}+a_n}\\ \leq\frac{\sqrt{2+\sqrt{3+\cdots\sqrt{n+1}}}-\sqrt{2+\sqrt{3+\cdots\sqrt{n}}}}{2}\\ =\frac12\,\frac{\sqrt{3+\sqrt{4+\cdots\sqrt{n+1}}}-\sqrt{3+\sqrt{4+\cdots\sqrt{n}}}}{\sqrt{2+\sqrt{3+\cdots\sqrt{n+1}}}+\sqrt{2+\sqrt{3+\cdots\sqrt{n}}}}\\ \leq\frac12\,\frac{\sqrt{3+\sqrt{4+\cdots\sqrt{n+1}}}-\sqrt{3+\sqrt{4+\cdots\sqrt{n}}}}{2\sqrt2}\\ \leq\cdots\\ \leq\frac{\sqrt{n+1}}{2^{n+1}}\leq\frac{n+1}{2^n}$$ By telescoping, we see that the sequence is Cauchy, i.e. $$a_{n+k}-a_n=\sum_{j=1}^ka_{n+j}-a_{n+j-1}\leq\sum_{j=1}^k\frac{n+j+1}{2^{n+j}}\leq\frac3{2^n}.$$ So the limit $L$ exists.

• Okay, so I follow your reasoning throughout the proof. My only issue is with your repeated rationalization result. I seem to be getting that $a_{n+1}-a_n\leq\frac{\sqrt{n+1}}{2^n}$ when I do it. How did you get from this to your $\frac{1}{2^n+1}$? I have also noted that this inequality does not hold for $n=1$: $a_2-a_1=\sqrt{1+\sqrt{2}}-\sqrt{1}\approx 0.55377>\frac{1}{4}$. – PitheMathemagician Oct 7 '13 at 3:31
• For your first question, you are right; it doesn't affect the proof in an essential way, though, as $\sum_n\,n/2^n=2$ (I'll edit in a few minuts). In your second question you are using my (off by $\sqrt{2}$) estimate instead of the right one you mention in your first question. – Martin Argerami Oct 7 '13 at 4:14

The quantity $n^{2^{-n}}$ tends to $1$ as $n \to \infty$, so we can find a constant $C$ such that

$$n^{2^{-n}} \leq C$$

for all $n$, and hence that

$$n \leq C^{2^n}$$

for all $n$. Thus

\begin{align} a_n &= \sqrt{1+\sqrt{2+\sqrt{3+\cdots+\sqrt{n}}}} \\ &\leq \sqrt{C^2+\sqrt{C^{2^2}+\sqrt{C^{2^3}+\cdots+\sqrt{C^{2^n}}}}} \\ &= C \sqrt{1+\sqrt{1+\sqrt{1+\cdots+\sqrt{1}}}} \\ &< C \sqrt{1+\sqrt{1+\sqrt{1+\cdots}}} \\ &= C\varphi, \end{align}

where $\varphi$ is the golden ratio. The sequence $a_n$ is bounded and increasing and therefore has a limit.

This essentially mimics the proof of Herschfeld's theorem, the statement of which can be found in my answer here.

• I knew it had something to do with $\varphi$! I saw this proof some time ago and I couldn't remember it. (+1) – chubakueno Oct 6 '13 at 2:54

I fire up the burners and create a numerical experiment. I created this Python program.

import math
def foo(n):
out = math.sqrt(n)
for k in range(n - 1,0, -1):
out = math.sqrt(k + out)
return out
for k in range(1,50):
print ("f(%s) = %.6f"%(k, foo(k)))


Here is what is put out.

   f(1) = 1.000000
f(2) = 1.553774
f(3) = 1.712265
f(4) = 1.748763
f(5) = 1.756238
f(6) = 1.757641
f(7) = 1.757886
f(8) = 1.757926
f(9) = 1.757932
f(10) = 1.757933
f(11) = 1.757933
f(12) = 1.757933
f(13) = 1.757933
f(14) = 1.757933
f(15) = 1.757933
f(16) = 1.757933
f(17) = 1.757933
f(18) = 1.757933
f(19) = 1.757933
f(20) = 1.757933
f(21) = 1.757933
f(22) = 1.757933
f(23) = 1.757933
f(24) = 1.757933
f(25) = 1.757933
f(26) = 1.757933
f(27) = 1.757933
f(28) = 1.757933
f(29) = 1.757933
f(30) = 1.757933
f(31) = 1.757933
f(32) = 1.757933
f(33) = 1.757933
f(34) = 1.757933
f(35) = 1.757933
f(36) = 1.757933
f(37) = 1.757933
f(38) = 1.757933
f(39) = 1.757933
f(40) = 1.757933
f(41) = 1.757933
f(42) = 1.757933
f(43) = 1.757933
f(44) = 1.757933
f(45) = 1.757933
f(46) = 1.757933
f(47) = 1.757933
f(48) = 1.757933

f(49) = 1.757933


It looks like there is a limit less than 2, but I don't recognize the number. It seems to be quite flat after $n\ge 10$.

• Your program computes $\sqrt{n + \sqrt{n-1 + \sqrt{n-2 + \sqrt{\cdots + \sqrt{1}}}}}$. – 6005 Oct 6 '13 at 1:34
• Yerright, I will take a second cut. – ncmathsadist Oct 6 '13 at 1:35
• Thanks for the catch, @Goos – ncmathsadist Oct 6 '13 at 1:46
• oeis.org/A072449 – Fred Kline Oct 10 '13 at 22:03

Term by term, is less than $$\sqrt{1+\sqrt{2^1+\sqrt{2^2+\sqrt{2^3...}}}}=\sqrt{1+\sqrt{2}\sqrt{1+2^{-1}\sqrt{2^2+\sqrt{2^3...}}}}$$ $$<\sqrt{1+\sqrt{2}\sqrt{1+2^{-0.5}\sqrt{2^2+\sqrt{2^3+...}}}}$$ $$=\sqrt{1+\sqrt{2}\sqrt{1+\sqrt{2+2^{-1}\sqrt{2^3...}}}}$$ $$\cdots$$ $$<\sqrt{1+\sqrt{2}\sqrt{1+\sqrt{2+\sqrt{2^2...}}}}$$ So we now have to show that $a_0=1$,$a_{n+1}=\sqrt{1+\sqrt{2}a_{n}}$ converges(this series is strictly greater than the last equation).We proceed by induction.

Assume $a_n\le\frac{1+\sqrt3}{\sqrt2}$, then $$a_{n+1}\le\sqrt{2+\sqrt{3}}=\frac{1+\sqrt3}{\sqrt2}$$ And since our sequence is monotone increasing and $1\le\frac{1+\sqrt3}{\sqrt2}$ the result follows.

Note: The number $1.757933$ of ncmathsadist is fairly close to this limit, $\approx 1.931851$

I wanted to add the continued fraction format of the problem. This post is not really intended to be an answer

• How do you know that this continued fraction corresponds to the problem? – chubakueno Oct 6 '13 at 2:40
• Any symbolic computation software will do the job. I did it with Mathematica – Logarithm Oct 7 '13 at 23:30
• I know that if I approximate it well enough, I can procedurally do this. But I was more about asking about the pattern (i see nothing). However, if you are interested in programming, this is always a good exercise.(Ask GNU MP if you have precision issues :)) – chubakueno Oct 8 '13 at 1:27