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.
 A: 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}$.
A: 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}.$$
