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

Question

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.

Answer 1

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$.

Answer 2

$$(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$...

Answer 3

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$?

Answer 4

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 $$