4
$\begingroup$

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.

|cite|improve this question
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Good job! I expected a much more complicated answer. $\endgroup$ – Programmer.zip Oct 9 '16 at 17:47
  • 1
    $\begingroup$ 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? $\endgroup$ – Did Oct 9 '16 at 18:22
  • $\begingroup$ @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. $\endgroup$ – Aforest Oct 10 '16 at 1:44
  • $\begingroup$ 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$). $\endgroup$ – Did Oct 10 '16 at 5:16
  • $\begingroup$ @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.... $\endgroup$ – Aforest Oct 10 '16 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.