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.

$\endgroup$
0

1 Answer 1

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

$\endgroup$
7
  • $\begingroup$ Good job! I expected a much more complicated answer. $\endgroup$ Oct 9, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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.