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

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

Solution 2:

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