Limit $(n - a_n)$ of sequence $a_{n+1} = \sqrt{n^2 - a_n}$

Consider the sequence $\{a_n\}_{n=1}^{\infty}$ defined recursively by $$a_{n+1} = \sqrt{n^2 - a_n}$$ with $a_1 = 1$. Compute $$\lim_{n\to\infty} (n-a_n)$$

I am having trouble with this. I am not even sure how to show the limit exists. I think if we know the limit exists, it is just algebra, but I'm not sure.

• Have you tried computing this? It seems that the limit doesn't exists. \begin{align} &\texttt{a(1) = 1;}\\ &\texttt{for i = 2:10}\\ &\texttt{ a(i) = sqrt((i-1)^2-a(i-1));}\\ &\texttt{endfor} \end{align} – GNUSupporter 8964民主女神 地下教會 Jan 7 '16 at 3:59
• @GNUSupporter I just computed it myself, and it's apparent that the limit does indeed exist. In Mathematica try a[n_]:=a[n]=Sqrt[(n-1)^2-a[n-1]];a[1]=1;ListPlot[Table[{n,n-a[n]},{n,1,20}]] Further, assuming $a_n = n + b + o(1)$ and expanding things in Taylor series indicates that $b = -3/2$, and so the limit in question should be $3/2$. The numerics support this. – Antonio Vargas Jan 7 '16 at 4:01
• @AntonioVargas Sorry. I mistaken $n-a_n$ to be $a_n$. – GNUSupporter 8964民主女神 地下教會 Jan 7 '16 at 4:05
• May be useful: $n-a_{n+1}=\frac{a_n}{n+a_{n+1}}$, – Aloizio Macedo Jan 7 '16 at 4:06
• $$(n+1)-a_{n+1}=\dfrac{(3n+1)+(a_n-n)}{(n+1)+\sqrt{(n^2-n)-(a_n-n)}}$$ Assume that $\lim_{n\to\infty}(n-a_n)=l$ exist as a real number. Then we can obtain that $l=\dfrac{3}{2}.$ This shows if the limit exist, then it should be $\dfrac{3}{2}$ – Bumblebee Jan 7 '16 at 5:04

First, we'll show that $0 \le n-a_n \le 2$ for all $n$. Then, we will show that $n-a_n \to \dfrac{3}{2}$ as $n \to \infty$.

Since, $a_1 = 1$, we have $1-a_1 = 0$, so $0 \le 1-a_1 \le 2$, as desired.

Now, suppose $0 \le n-a_n \le 2$ for some positive integer $n$. Then, we have:

$$\sqrt{n^2-n} \le \sqrt{n^2-a_n} \le \sqrt{n^2-n+2}$$

$$\sqrt{(n-\tfrac{1}{2})^2-\tfrac{1}{4}} \le a_{n+1} \le \sqrt{(n-\tfrac{1}{2})^2+\tfrac{7}{4}}$$

$$(n+1) - \sqrt{(n-\tfrac{1}{2})^2+\tfrac{7}{4}} \le (n+1)-a_{n+1} \le (n+1) - \sqrt{(n-\tfrac{1}{2})^2-\tfrac{1}{4}}$$

$$\tfrac{3}{2} + (n-\tfrac{1}{2}) - \sqrt{(n-\tfrac{1}{2})^2+\tfrac{7}{4}} \le (n+1)-a_{n+1} \le \tfrac{3}{2} + (n-\tfrac{1}{2}) - \sqrt{(n-\tfrac{1}{2})^2-\tfrac{1}{4}}$$

$$\dfrac{3}{2} - \dfrac{\tfrac{7}{4}}{(n-\tfrac{1}{2}) + \sqrt{(n-\tfrac{1}{2})^2+\tfrac{7}{4}}} \le (n+1)-a_{n+1} \le \dfrac{3}{2} + \dfrac{\tfrac{1}{4}}{(n-\tfrac{1}{2}) + \sqrt{(n-\tfrac{1}{2})^2-\tfrac{1}{4}}}.$$

For $n \ge 1$, we have $(n-\tfrac{1}{2}) + \sqrt{(n-\tfrac{1}{2})^2+\tfrac{7}{4}} \ge \tfrac{1}{2}+\sqrt{(\tfrac{1}{2})^2+\tfrac{7}{4}} = \tfrac{1}{2}+\sqrt{2} \ge \tfrac{7}{6}$,

as well as $(n-\tfrac{1}{2}) + \sqrt{(n-\tfrac{1}{2})^2-\tfrac{1}{4}} \ge \tfrac{1}{2}+\sqrt{(\tfrac{1}{2})^2-\tfrac{1}{4}} = \tfrac{1}{2}$.

Thus, the last equation implies $0 \le (n+1)-a_{n+1} \le 2$.

So by induction, $0 \le n-a_n \le 2$ for all positive integers $n$.

Then by repeating the above algebra, we have that $$\dfrac{3}{2} - \dfrac{\tfrac{7}{4}}{(n-\tfrac{1}{2}) + \sqrt{(n-\tfrac{1}{2})^2+\tfrac{7}{4}}} \le (n+1)-a_{n+1} \le \dfrac{3}{2} + \dfrac{\tfrac{1}{4}}{(n-\tfrac{1}{2}) + \sqrt{(n-\tfrac{1}{2})^2-\tfrac{1}{4}}}$$ holds for all positive integers $n$.

By using the squeeze theorem, we get $\displaystyle\lim_{n \to \infty}[(n+1)-a_{n+1}] = \dfrac{3}{2}$, and thus, $\displaystyle\lim_{n \to \infty}(n-a_n) = \dfrac{3}{2}$.

• Very nice solution ++1 – Bumblebee Jan 7 '16 at 5:06
• Please can you check this question. This is an old question similar to this one post by me. But I did not get a satisfactory answer for it. – Bumblebee Jan 7 '16 at 8:36

Here is a briefer answer which illustrates that the difficulty of the problem lies in bounding the growth of $a_n$. All we need is $a_n \sim n$, in the sense that $$\lim_{n\to\infty} \frac{a_n}{n} = 1.$$ This would follow if we knew e.g. that $n - a_n$ is bounded. JimmyK's sharp result that $0 \le n - a_n \le 2$ is more than enough! So, indeed, $a_n \sim n$. From here, using difference of squares, $$(n+1) - a_{n+1} = \frac{(n+1)^2 - (n^2 - a_n)}{(n+1) + a_{n+1}} = \frac{2n + 1 + a_n}{n + 1 + a_{n+1}} = \frac{2 + \frac{1}{n} + \frac{a_n}{n}}{1 + \frac{1}{n} + \frac{a_{n+1}}{n}} \to \frac{2 + 0 + 1}{1 + 0 + 1} = \frac{3}{2}.$$