# Limit of certain recurrence relation

So given this recurrence relation (not how it was presented, but equivalent and much nicer)

$$x_{n+1} = \dfrac{x_n + nx_{n-1}}{n+1}; \ x_0 = 0,\ x_1 = 1$$

I just can't find what the limit as $n$ goes to infinity is. It was straightforward to show it was convergent, and oscillatory about its limit, and I know the limit is going to be between $0.6$ and $0.75$ (through repeated calculation). The next step of finding the exact limit, though, I'm completely lost on.

-
An approach is to compute the series $X(t)=\sum\limits_nx_nt^n$ and to deduce $\lim\limits_{n\to\infty}x_n=\lim\limits_{t\to1}(1-t)X(t)$ (which should equal $\ln(2)$, unless I am mistaken). – Did Aug 7 '13 at 14:36
I can say that the limit is somewhere in $(0.613606,0.613806)$ after 10000 iterations. – TZakrevskiy Aug 7 '13 at 14:36
The Maple commands $$sol := rsolve({(n+1)*S(n+1) = S(n)+n*S(n-1), S(0) = 0, S(1) = 1}, S(n))$$ and $$limit(sol, n = infinity)$$ produce $$\ln \left( 2 \right) -1/2\, \left( -1 \right) ^{n} \left( \Psi \left( 1/2\,n+1 \right) -\Psi \left( 1/2\,n+1/2 \right) \right)$$ and $\ln 2$. – user64494 Aug 7 '13 at 15:35
hi Anyone here can give some input on: [What is the Probability that a Knight stays on chessboard after N hops][1] [1]: math.stackexchange.com/questions/464049/… – Arnab Dutta Aug 10 '13 at 10:46

If $$S_n = \sum_{j=1}^{n} \frac{(-1)^{j+1}}{j}$$

then we can prove that

$$(n+1)S_{n+1} = S_n + nS_{n-1}$$

Since $x_1 = S_1$ and $x_2 = S_2$ we have that $x_n = S_n$ for $n \ge 1$

Thus $\lim x_n = \lim S_n = \log 2$

-

Define ${\rm F}\left(z\right) \equiv \sum_{n = 0}^{\infty}z^{n}\,x_{n}\ \ni\ {\rm F}\left(0\right) = 0$ and ${\rm F}\,'\left(1\right) = 1$. Then

\begin{eqnarray*} 0 & = & \sum_{n = 1}^{\infty}z^{n}\left\lbrack% \left(n + 1\right)x_{n + 1} - x_{n} - nx_{n - 1} \right\rbrack \\ & = & \sum_{n = 2}^{\infty}z^{n - 1}\,n\,x_{n} - \sum_{n = 1}^{\infty}z^{n}\,x_{n} - \sum_{n = 0}^{\infty}z^{n + 1}\left(n + 1\right)x_{n} \\ & = & \left\lbrack{\rm F}\,'\left(z\right) - 1\right\rbrack - {\rm F}\left(z\right) - \left\lbrack z^{2}{\rm F}\,'\left(z\right) + z{\rm F}\left(z\right)\right\rbrack \\ & = & \left(1 - z^{2}\right){\rm F}\,'\left(z\right) - \left(1 + z\right){\rm F}\left(z\right) - 1 \end{eqnarray*}

$$\left(z - 1\right){\rm F}\,'\left(z\right) + {\rm F}\left(z\right) = -\,{1 \over z + 1} \quad\Longrightarrow\quad {{\rm d}\left\lbrack\left(z - 1\right){\rm F}\left(z\right)\right\rbrack \over {\rm d}z} = -\,{1 \over z + 1}$$

$$\left(z - 1\right){\rm F}\left(z\right) = -\int_{0}^{z}{{\rm d}z \over z + 1} = -\ln\left(1 + z\right)$$

$$\quad\Longrightarrow\quad {\rm F}\left(z\right) = {\ln\left(1 + z\right) \over 1 - z} = z+z^2/2+(5 z^3)/6+(7 z^4)/12+(47 z^5)/60+O(z^6)$$

$$x_{0} = 0,\ x_{1} = 1,\ x_{2} = {1 \over 2},\ x_{3} = {5 \over 6}\,\ x_{4} = {7 \over 12}\,\ x_{5} = {47 \over 60}\,\quad\mbox{etc...}$$

In general \begin{align} {\rm F}\left(z\right) &= {\ln\left(1 + z\right) \over 1 - z} = \sum_{s = 0}^{\infty}z^{s}\sum_{k = 0}^{\infty}{\left(-1\right)^{k} \over k + 1}\,z^{k + 1} \sum_{n = 1}^{\infty}\delta_{n, s + k + 1} = \sum_{n = 1}^{\infty}z^{n} \sum_{s = 0}^{\infty}\sum_{k = 0}^{\infty}{\left(-1\right)^{k} \over k + 1}\, \delta_{k,n - s -1} \\[3mm]&= \sum_{n = 1}^{\infty}z^{n} \sum_{s = 0}^{n - 1}{\left(-1\right)^{n - s -1} \over \left(n - s -1\right) + 1} = \sum_{n = 1}^{\infty}z^{n} \sum_{s = 0}^{n - 1}{\left(-1\right)^{s} \over s + 1} \end{align}

$$\quad\Longrightarrow\quad x_{n} = \sum_{s = 0}^{n - 1}{\left(-1\right)^{s} \over s + 1}\,, \qquad n \geq 1$$

$$\lim_{n \to \infty}x_{n} = \sum_{s = 0}^{\infty}{\left(-1\right)^{s} \over s + 1} = \sum_{s = 0}^{\infty}{\left(-1\right)^{s} \over s + 1}\ 1^{s + 1} = \ln\left(1 + 1\right) = {\Large \ln\left(2\right)}$$

-