# Calculate the limit of recursively defined sequence

Given a sequence $x_{n}$, $x_0=0, x_1=1, x_{n+1}=\frac{x_n + nx_{n-1}}{n+1}$. Prove, that $x_{n}$ converges and find the limit.

$$x_{k+1}=\frac{x_k + kx_{k-1}}{k+1} \\ (k+1)x_{k+1}=x_k + kx_{k-1} \\ (k+1)x_{k+1}=(k+1)x_k-kx_k+kx_{k-1} \\ (k+1)(x_{k+1}-x_k)=-k(x_k-x_{k-1})$$

When $k=1..n$

$$2(x_2-x_1)=-1(x_1-x_0)=-1 \\ 3(x_3-x_2)=-2(x_2-x_1)=1 \\ \ldots \\ (n+1)(x_{n+1}-x_n)=-n(x_n-x_{n-1})=(-1)^n$$

$$x_2-x_1=-\frac{1}{2} \\ x_3-x_2=\frac{1}{3} \\ \ldots \\ x_{n+1}-x_n=\frac{(-1)^n}{n+1}$$

$$x_{n+1}-x_1=-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\ldots+\frac{(-1)^n}{n+1} \\ x_{n+1}=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\ldots+\frac{(-1)^n}{n+1}= \\ =\sum_{i=1}^{n+1} \frac{(-1)^{i+1}}{i}$$

This series converges, therefore, a sequence converges too. But how to calculate a limit, which is equal to the sum of a series?

$$x_{n}=\sum_{i=0}^{n-1} \frac{(-1)^{i}}{i+1}=\sum_{i=0}^{n-1} (-1)^{i}\int_0^1x^i\,dx=\int_0^1\sum_{i=0}^{n-1}(-1)^ix^i\,dx=\int_0^1\frac{1-(-x)^n}{1-(-x)}\,dx$$
$$=\int_0^1\frac{1}{1+x}\,dx+\int_0^1\frac{-(-x)^n}{1+x}\,dx$$
The first term is $\log2$, and the second term can be bounded in absolute value by noting that:
$$\left\vert\int_0^1\frac{-(-x)^n}{1+x}\,dx\right\vert\le\int_0^1\left\vert\frac{-(-x)^n}{1+x}\right\vert\,dx=\int_0^1\frac{x^n}{1+x}\,dx\le\int_0^1\frac{x^n}{1}\,dx=\frac{1}{n+1}$$
$x_n=\log2+\frac{\theta_n}{n+1}$, where $-1\le\theta_n\le1$, i.e. the sequence converges to $\log2$.