Given the sequence $a_1=1$,$a_{n+1}=1+\frac{n}{a_n}$, does the sequence $a_n+n-a_n^2$ converges? 
Given the sequence $a_1=1$,$a_{n+1}=1+\frac{n}{a_n}$, does the sequence $a_n+n-a_n^2$ converges? If it converges, find the limit.

Now, I proved
$\frac{1+\sqrt{1+4(n-1)}}{2}\leq a_n\leq \frac{1+\sqrt{1+4n}}{2}$,
and
$0\leq p_n=a_n+n-a_n^2\leq 1,p_{n+1}+\frac{n}{a_n^2}p_n=1$,which implies $\lim\limits_{n\rightarrow+\infty}p_{n+1}=\lim\limits_{n\rightarrow\infty}p_{n-1}$,
but I cannot prove $\lim\limits_{n\rightarrow+\infty}p_{n+1}=\lim\limits_{n\rightarrow\infty}p_{n}$ which means the squence $a_n+n-a_n^2$ limit equals to ${1\over2}$
so the question is: how can I prove $\lim\limits_{n\rightarrow+\infty}p_{n+1}=\lim\limits_{n\rightarrow\infty}p_{n}$ ?
 A: I don't like my following solution. By giving it, I just want to tell to others that this sequence is indeed convergent (contradicting to what I'm used to think).
I'm still looking forward to seeing other approaches to this question.
Lemma(Some sort of controlled time series)
Let $(a_n)$ and $(b_n)$ be two real sequence such that:

*

*$\lim_{n \rightarrow+ \infty} a_n= \lim_{n \rightarrow +\infty} b_n= 0$

*$a_n \ge 0$ and $ \sum_{n \ge 0} a_n =+\infty$
Then for any sequence $(q_n)$ such that:
$$ q_{n+1}=q_n+a_n( b_n-q_n)$$
we have: $$\lim q_n=0$$
$\square$
Back to our main question
Main solution( If your work is true)
We have :
$$ p_{n+1}=1-\frac{n}{a_n^2}p_n=1-\frac{n}{a_n^2}(1-\frac{n-1}{a_{n-1}^2}p_{n-1})=\frac{n(n-1)}{a_n^2a_{n-1}^2}p_{n-1}+(1-\frac{n}{a_n^2})$$
Thus by choosing:

*

*$r_n:=p_{n}-\frac{1}{2}$

*$c_n:=1-\frac{n(n-1)}{a_n^2a_{n-1}^2}$

*$d_n:= \dfrac{1-\frac{n}{a_n^2} }{1-\frac{n(n-1)}{a_n^2a_{n-1}^2}}-\frac{1}{2}$
We have:

*

*$r_{n+1}= r_{n-1}-c_n( d_n-r_{n-1})$

*$\lim c_n= \lim d_n= 0$

*$c_n \ge 0$ and $\sum_{k} c_{2k} = \sum_{k} c_{2k+1}=+\infty$
(Note that:  $1- \frac{n}{a_n^2} \sim \frac{1}{\sqrt{n}}$)
From which, we apply my lemma at the very beginning for two sequence $(r_{2n})$ and $(r_{2n-1})$.
Hence, we have the conclusion that :
$$ \lim p_n=\frac{1}{2}$$
$\square$
Comments

*

*Though my solution is not complicated, this question should not be this complicated.

*I think this question is a simple one until I have to manually craft a  lemma for it.

*It would be nice if Mr.Grape can extend my knowledge by telling me where did you find this question.

*I'm still looking forward to nicer solution.

Updated comment
Oh, so this question is not a simple question. And so my lemma provides a general method to deal with this kind of question and even proves (apparently) the convergence when $a_0$ arbitrary. (which is some bit more general than the newled provided link)
A: *

*Link with the number of involutions in the symmetric goup $S_n$.
Let $I_0=1$. Let, for $n\geqslant 1$, $I_n$ be the number of involutions in the symmetric group $S_n$ (i.e $\ \sigma \in S_n \ | \ \sigma^2=I$). We can show that $\ I_1=1 \ $ , and $\ \forall n \in \mathbb N^{\star} \ , \ I_{n+1}=I_n+nI_{n-1}$. And, by induction, $\ \forall n\in \mathbb N \ , \ a_n=\frac{I_{n+1}}{I_n}\  $ .

*L Moser and M Wyman, On solutions of x^d=1 in symmetric groups, Canad. J. Math., 7 (1955)  This paper can be found here . In this article, it is shown that exists $(\beta_n)_{n\in\mathbb N}$ such that $\ \forall p \in \mathbb N \ , \ a_n =\sqrt{n} +\displaystyle \sum_{k=0}^p \dfrac{\beta_k}{n^{k/2}}+{\rm o}\left(\dfrac{1}{n^{p/2}}\right)\ $. For example $\ a_n=\sqrt{n}+\dfrac{1}{2}-\dfrac{1}{8\sqrt{n}} +{\rm o}\left(\dfrac{1}{\sqrt{n}}\right)$. With that  result, it's easy to show that $\ \lim (a_n+n-a_n^2)=\dfrac{1}{2}$ .

*If $\ b_0 \in \mathbb R_+^{\star}\ $ and $\ \forall n \in \mathbb N \ , \ b_{n+1}=1+\frac{n}{b_n} \ $, then, $(b_n)_{n\in\mathbb N}$ has the same asymptotic expansion: $\ \forall p \in \mathbb N \ , \ a_n =\sqrt{n} +\displaystyle \sum_{k=0}^p \dfrac{\beta_k}{n^{k/2}}+{\rm o}\left(\dfrac{1}{n^{p/2}}\right)\ $. (the same coefficients $\beta_k$ )

