Aproximación de una secuencia con recurrencia graciosa

Question

Considere la secuencia $a_n$ definido como $a_1=a_2=1, a_{n+1}(1+a_{n})=n+1$ .

Esta secuencia describe el número medio de puntos fijos de una involución sobre un $n$ -y se puede abordar el problema de la aproximación utilizando el análisis complejo, pero quiero evitarlo. ¿Puede obtenerse alguna aproximación por métodos elementales?

EDIT: Si es cierto que la secuencia es monótona creciente, obtenemos las estimaciones $-\frac{1}{2} + \sqrt{n+\frac{1}{4}} \le a_n \le -\frac{1}{2} + \sqrt{n+\frac{5}{4}}$ es decir $a_n = -\frac{1}{2} + \sqrt{n} + O(\frac{1}{\sqrt{n}})$ pero, ¿por qué es monótono?

EDIT2: Sólo para aclarar la parte de la función generadora, tenga en cuenta que $\exp(x+x^2/2)$ es la función generadora exponencial del número de involuciones y $\frac{\partial(\exp(tu+t^2/2))}{\partial u}|_{u=1} = t\exp(t+t^2/2)$ es la función generadora exponencial de $a_n \times b_n$ donde $a_n$ es el número de involuciones y $b_n$ la media de los puntos fijos. El resultado es $b_n = na_{n-1} / a_{n}$ y la recurrencia de $a_n$ da una recurrencia en $b_n$ el que publiqué aquí. Esto también se puede demostrar combinatorialmente.

Answer 1

Una vez adivinados los límites, resulta sencillo demostrarlos mediante inducción.

Induciremos en $n$ para demostrar la afirmación $-\frac{1}{2} + \sqrt{n+\frac{1}{4}} \leq a_n \leq -\frac{1}{2} + \sqrt{n+\frac{5}{4}}$ .

En $n=1$ tenemos $-\frac{1}{2}+\sqrt{1+\frac{1}{4}} \leq 1=a_1=-\frac{1}{2}+\sqrt{1+\frac{5}{4}}$ .

Supongamos que se cumple para $n=k$ . Ahora $\frac{1}{2} + \sqrt{k+\frac{1}{4}} \leq a_k+1 \leq \frac{1}{2} + \sqrt{k+\frac{5}{4}}$ por lo que utilizando $a_{k+1}=\frac{k+1}{a_k+1}$ obtenemos

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

Ahora tenemos que demostrar que $$k+1 \leq \left(\frac{1}{2}+\sqrt{k+\frac{1}{4}}\right)\left(-\frac{1}{2}+\sqrt{k+\frac{9}{4}}\right)$$ .

Sea $x=k+\frac{5}{4} \geq \frac{9}{4}>2$ por lo que basta con demostrar que \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} Esta última desigualdad es cierta ya que $x \geq 2$ implica $x^2 \geq 2x>x+1$ .

Así pues, hemos terminado por inducción.