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.