Limit of certain recurrence relation

Question

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.

Answer 1

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$

Answer 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)} $$