<s>[INST] Approximating a sequence with funny recurrence Consider the sequence $a_n$ defined as $a_1=a_2=1, a_{n+1}(1+a_{n})=n+1$. 
This sequence describes the average number of fixed points of an involution on an $n$-set, and one can approach the problem of approximating it using complex analysis, but I want to avoid it. Can some approximation be obtained by elementary methods?
EDIT: If it is true that the sequence is monotone increasing, we get the estimates $-\frac{1}{2} + \sqrt{n+\frac{1}{4}} \le a_n \le -\frac{1}{2} + \sqrt{n+\frac{5}{4}}$, i.e. $a_n = -\frac{1}{2} + \sqrt{n} + O(\frac{1}{\sqrt{n}})$, but why is it monotone?
EDIT2: Just to clarify the generating function part, note that $\exp(x+x^2/2)$ is the exponential generating function of the number of involutions and $\frac{\partial(\exp(tu+t^2/2))}{\partial u}|_{u=1} = t\exp(t+t^2/2)$ is the exponential generating function of $a_n \times b_n$ where $a_n$ is the number of involutions and $b_n$ the average of fixed points. This gives $b_n = na_{n-1} / a_{n}$ and the recurrence of $a_n$ gives a recurrence on $b_n$, the one I posted here. This can also be proved combinatorially.
 [/INST] After you have guessed the bounds, it is now straightforward to prove them using induction.
We shall induct on $n$ to prove the statement $-\frac{1}{2} + \sqrt{n+\frac{1}{4}} \leq a_n \leq -\frac{1}{2} + \sqrt{n+\frac{5}{4}}$.
When $n=1$, we have $-\frac{1}{2}+\sqrt{1+\frac{1}{4}} \leq 1=a_1=-\frac{1}{2}+\sqrt{1+\frac{5}{4}}$.
Suppose it holds for $n=k$. Now $\frac{1}{2} + \sqrt{k+\frac{1}{4}} \leq a_k+1 \leq \frac{1}{2} + \sqrt{k+\frac{5}{4}}$, so using $a_{k+1}=\frac{k+1}{a_k+1}$, we get
$$-\frac{1}{2} + \sqrt{k+\frac{5}{4}}=\frac{(k+1)(-\frac{1}{2} + \sqrt{k+\frac{5}{4}})}{(k+\frac{5}{4})-\frac{1}{4}} =\frac{k+1}{\frac{1}{2} + \sqrt{k+\frac{5}{4}}} \leq a_{k+1} \leq \frac{k+1}{\frac{1}{2} + \sqrt{k+\frac{1}{4}}}$$
We now need to prove that $$k+1 \leq \left(\frac{1}{2}+\sqrt{k+\frac{1}{4}}\right)\left(-\frac{1}{2}+\sqrt{k+\frac{9}{4}}\right)$$.
Let $x=k+\frac{5}{4} \geq \frac{9}{4}>2$, so it suffices to prove that 
\begin{align}
&x-\frac{1}{4} \leq -\frac{1}{4}+\frac{1}{2}\sqrt{x+1}-\frac{1}{2}\sqrt{x-1}+\sqrt{x^2-1} \\
\Leftrightarrow &\sqrt{x^2}-\sqrt{x^2-1} \leq \frac{1}{2}(\sqrt{x+1}-\sqrt{x-1}) \\
\Leftrightarrow &\frac{1}{\sqrt{x^2}+\sqrt{x^2-1}} \leq \frac{1}{\sqrt{x+1}+\sqrt{x-1}} \\
\Leftrightarrow & \sqrt{x+1}+\sqrt{x-1} \leq \sqrt{x^2}+\sqrt{x^2-1}
\end{align}
This last inequality is true since $x \geq 2$ implies $x^2 \geq 2x>x+1$.
We are thus done by induction.
</s>