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

Question

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!

Please help me resolve the errors.

Answer 1

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