# Proving $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$ by induction

How can I prove by induction that $\sqrt{1+\sqrt{2+\cdots+\sqrt{n}}} < 3$ for $n\geq 1$? My guess is that there must be another form to express the sum of nested square roots, but I don't know how to find it.

We can actually prove a more general version of what you hope to prove (set $a=0$ for your problem, specifically):

Claim: For every $n\in\mathbb{Z^+}$ and every non-negative real number $a$ $$\sqrt{a+1+\sqrt{a+2+\cdots+\sqrt{a+n}}}< a+3.$$ Proof. For $n\geq 1$, let $S(n)$ denote the statement that for any non-negative real $a$, $$S(n) : \sqrt{a+1+\sqrt{a+2+\cdots+\sqrt{a+n}}}< a+3.$$ Base step: $S(1)$ says that $\sqrt{a+1}<a+3$, and this is verifiable since $$a+1<(a+3)^2\Leftrightarrow 0<a^2+5a+8,$$ which is true for $a\geq 0$.

Inductive step: Fix some $k\geq 0$, and suppose that $S(k)$ is true for any non-negative $a$ where $$S(k) : \sqrt{a+1+\sqrt{a+2+\cdots+\sqrt{a+k}}}< a+3.$$ To be shown is that $S(k+1)$ follows for any non-negative $b$ where $$S(k+1) : \underbrace{\sqrt{b+1+\sqrt{b+2+\cdots+\sqrt{b+k+\sqrt{b+k+1}}}}}_{\text{LHS}}<\underbrace{b+3}_{\text{RHS}}.$$ Using $a=b+1$, \begin{align} \text{LHS} &= \sqrt{b+1+\sqrt{b+2+\cdots+\sqrt{b+k+\sqrt{b+k+1}}}}\\[1em] &= \sqrt{b+1+\sqrt{a+1+\cdots+\sqrt{a+k-1+\sqrt{a+k}}}}\\[1em] &< \sqrt{b+1+a+3}\tag{by $S(k)$}\\[0.5em] &= \sqrt{2b+5}\\[0.5em] &< b+3\\[0.5em] &= \text{RHS}, \end{align} where the last inequality follows since $$2b+5<(b+3)^2=b^2+6b+9$$ and $b^2\geq 0$. This proves $S(k+1)$, completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

Your particular problem holds for $S(n)$ where $a=0$.

You can also try going at it from the other direction: by squaring both sides, the given inequality can be written as $1+\sqrt{2+\sqrt{3+\ldots}}\lt 3^2$. Subtract $1$ and square: $2+\sqrt{3+\ldots}\lt (3^2-1)^2$. Subtract 2 and square: $3+\sqrt{\ldots}\lt\left((3^2-1)^2-2\right)^2$. So define $a_0=3$, $a_i=a_{i-1}^2-i$. Can you show by induction that $a_n^2\gt n+1$ for all $n$?

• Would the downvoters care to explain themselves? – Steven Stadnicki Apr 23 '15 at 21:53
• +1 there is no explanation, just a gut reaction for (generally) illogical reasons. – Zach466920 Apr 23 '15 at 22:08
• @Zach466920 I'm used to the occasional drive-by downvote, but seeing two on an answer so benign and seemingly straightforward makes me wonder if I missed something. – Steven Stadnicki Apr 23 '15 at 22:19
• @Zach466920 Although I see that your answer has 4(!) downvotes, so maybe something is going on here... – Steven Stadnicki Apr 23 '15 at 22:19
• 4! I didn't even know that! I thought it was 2. Hmmm...well on the bright side 4 people liked my answer. I think I'll state that my answer is only a partial in the future. In this case I did to little to late. – Zach466920 Apr 23 '15 at 22:28

$$(1) \quad x=k+\sqrt x$$ $$x=\sqrt {k+\sqrt x}$$ continuing the recursion... $$x=\sqrt {k+\sqrt {k+\sqrt {k+...}}}$$ Thus (1) is the equivalent expression. Solve for x with $k=1$ $$x=\phi$$ Thus, x equals the golden ratio. Multiply the expression by c... $$c \cdot x=c \cdot \sqrt {k+\sqrt {k+\sqrt {k+...}}}$$ $$c \cdot x=\sqrt {c^2 \cdot k+\sqrt {c^4 \cdot k+\sqrt {c^8 \cdot k+...}}}$$

Choose c to equal $2^{1/4}$ (This is where you use induction to prove this works)

Prove $$2^{2^n/4} \ge n$$ For $n=1 \$, $\ \sqrt 2 \gt 1$ so we have a base case Inductive step, assume the above holds for $n=k$ Let, $n=k+1$ $$2^{2^k/4} \ge k$$ $$2 \cdot 2^{2^k/4} \ge 2 \cdot k$$ $$2^{2 \cdot 2^{k}/4} \ge 2 \cdot k$$ $$2^{2^{k+1}/4} \ge k+1$$ assuming k is greater than 1, thus the above holds for all n.

$$2^{1/4} \cdot \phi=\sqrt {\sqrt 2+\sqrt {2+\sqrt { 4+\sqrt {16+...}}}}$$ Thus the inequality for the radical is given by $$\phi \le S \le 2^{1/4} \cdot \phi$$ $$1.618... \le S \le 1.924...$$

I personally guess the radical to be approximately equal to $1.771$...

• But this doesn't use induction as requested by the OP. – Prasun Biswas Apr 23 '15 at 21:03
• How is this even relevant? You're not considering the same sequence as in the question. The sequences $\sqrt{k+\sqrt{k+\cdots}}$ and $\sqrt{1+\sqrt{2+\cdots}}$ are not the same. – Patrick Da Silva Apr 23 '15 at 21:04
• He gets there in the end. (although $c^6$ should be $c^8$). – Empy2 Apr 23 '15 at 21:06
• @PatrickDaSilva you need to read the proof closer, I multiply after that... – Zach466920 Apr 23 '15 at 21:07
• This is clever, but you still need to show (a) that the interior terms are all greater than the corresponding integers (not hard, but needs proof all the same) and (b) that $a\lt a', b\lt b', c\lt c', \ldots\implies\sqrt{a+\sqrt{b+\sqrt{c+\ldots}}}\lt\sqrt{a'+\sqrt{b'+\sqrt{c'+...}}}$ - also not hard, and 'intuitively obvious', but it does need proof! – Steven Stadnicki Apr 23 '15 at 21:10

HINT

Take $U_n=\sqrt{1+\sqrt{2+ ... + \sqrt{n}}}, n\in \mathbb N.$

Then show that $\forall n \in \mathbb{N}, U_{n+1}^2 < 1+\sqrt{2} U_n$

After that, consider $Q(x)=x^2-\sqrt{2}x-1$ find the solutions then consider $Q(U_n)$ if it works you will find that

$$\lim_{n \to \infty} U_n \le \frac{\sqrt{2}+\sqrt{6}}{2} <3$$