# How to prove $n = \sqrt{1+(n-1)\sqrt{1+n\sqrt{1+(n+1)\sqrt{...}}}}$

This problem is brought in Introduction to Algorithms: A Creative Approach to show common errors in mathematical induction.

Problem: For all natural values of $n$, prove that:

$$n=\sqrt{1+(n-1)\sqrt{1+n\sqrt{1+(n+1)\sqrt{...}}}}\quad\mathcal{\color{navy}{(I)}}$$

Wrong Solution: for $n=1$ we have $1 = \sqrt{1+ 0(...)}$ which is true. By induction hypothesis: $$n=\sqrt{1+(n-1)\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{...}}}}}$$ $$n^2=1+(n-1)\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{...}}}}$$ $$n^2-1=(n-1)\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{...}}}}$$ $$\implies \frac{(n-1)(n+1)}{(n-1)}=\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{...}}}}\qquad \mathcal{\color{navy}{(II)}}$$ $$\implies n+1=\sqrt{1+n\sqrt{1+(n+1)\sqrt{1+(n+2)\sqrt{...}}}}$$ $$\tag*{\blacksquare}$$

There are two errors in the wrong solution:

• We have to prove that the expression $\mathcal{\color{navy}{(I)}}$ converges for all $n$, so that the claim is meaningful and $1 = \sqrt{1+ 0(...)}$ holds.

• In $\mathcal{\color{navy}{(II)}}$ we have to check we did not devide by zero. Actually the induction step fails from $n = 1$ to $n = 2$. I'm not sure changing the base case (e.g. $2=\sqrt{1+\sqrt{1+2\sqrt{1+3\sqrt{...}}}}$) helps!

Let $(a_n)$ be a sequence given by the recurrence relation below : $$\begin{cases}a_0=0\\ a_1=1\\ a_2=?\\ a_n^2=1+(n-1)a_{n+1}& \text{if n>1} \end{cases}$$ We calculate $a_2$. Assuming the sequence as a differentiable function $f$, we have $$f(x)^2=1+(x-1)f(x+1)\text{, then}\\ 2f(x)f'(x)=f(x+1)+(x-1)f'(x+1)$$ Therefore, $$2f(0)f'(0)=f(1)+(0-1)f'(1)\implies f'(1)=1\\ 2f(1)f'(1)=f(2)+(1-1)f'(2)\implies f(2)=2$$ We have $a_2=2$. Now mathematical induction can be used. Assuming that $a_n=n$, which is true for $n=0,1,2$, we have then $$n^2=1+(n-1)a_{n+1}\implies a_{n+1}=\frac{n^2-1}{n-1}=n+1$$

• Good job! I expected a much more complicated answer. Oct 9, 2016 at 17:47
• Where do you prove that the sequence $$\sqrt{1+1\sqrt{1+2\sqrt{1+3\sqrt{\cdots\cdots+(n-1)\sqrt{1+n}}}}}$$ converges?
– Did
Oct 9, 2016 at 18:22
• @Did In fact, l'Hôpital's rule is used when we calculate $a_2$. The problem is, if we give different $a_2$, for example $a_2=3$, the recurrence relation can also be well-defined. Therefore, if there is no $a_2$ given by the formula, it makes nonsense. What I did is just to find a reasonable value of $a_2$ so that the recurrence relation is well-defined. Oct 10, 2016 at 1:44
• But one cannot chose values at will, can one? The task is to prove that if $$a_{n,n}=1\qquad a_{k-1,n}=\sqrt{1+ka_{k,n}}$$ for every $1\leqslant k\leqslant n$, then $(a_{0,n})$ converges (and that its limit is $2$).
– Did
Oct 10, 2016 at 5:16
• @Did I think that in your formula, we can never know the value of $a_{n,n}$ for each $n$. Why should we have the same valve when $n$ changes? However, if $a_{n,n}$ is constant (not even equal to $1$), your sequence is surely convergent to $2$, and it seems not easy to prove that.... Oct 10, 2016 at 10:51