# Find a limit of the recursive sequence

The task is to prove sequence convergence and find a limit. $x_0=0$ $x_1=1$ $x_{n+1}=\frac {x_n + n \cdot x_{n-1}} {n+1}$

I have computed some values of a sequence to build up some idea of the data: elements with even indexes converge from 0 to ~0.68, and elements with odd indexes converge from 1 to the same value.

It's obvious that the sequence isn't monotonic, hence I had to stick with a Cauchy theorem. But it led me nowhere: $|x_{n+p}-x_{n}| < | \frac {n \cdot x_{n-1}} {n + 1} + 2 \cdot \sum_{i=n}^{2n-2} x_i + { \frac {x_{2n-1}} {2n} } |$ (I got there under the assumption that $n = p$.)

Then I tried another move: $x_{n+1} - x_{n} = \frac {x_n + n \cdot x_{n-1}} {n+1} - x_n =$
$= \frac {-n \cdot ( x_n - x_{n-1})} {n+1}$
$x_{n} - x_{n-1} = \frac {(1-n) \cdot (x_{n-1} - x_{n-2})} {n}$

It looks like progress, but I still don't know how to go next.

-
This is the question from preliminary examination to Yadex's school of data analysis. Have you passed it? – DoctorMoisha Mar 12 '15 at 8:37
@DoctorMoisha, Yes. – wf34 Mar 12 '15 at 9:20
Congratulations! How was the third part - oral examination? Do they ask to prove something? I will be very grateful if you answer me even briefly. You can send me letter on vigorous.activity@gmail.com and letter could be in Russian) Thank you! – DoctorMoisha Mar 12 '15 at 10:01

You're on the right track. If you write $d_n=x_{n+1}-x_n$, you have $d_n=-\frac n{n+1}d_{n-1}$

So $d_n=(-\frac n{n+1})(-\frac {n-1}{n})(-\frac {n-2}{n-1})\ldots\frac12d_0=\frac{(-1)^n}{n+1}d_0=\frac{(-1)^n}{n+1}$

Then $x_n=x_0+\sum\limits_{k=0}^{n-1}d_k=\sum\limits_{k=0}^{n-1}d_k$

And $\lim\limits_{n\to\infty}x_n=\sum\limits_{n=0}^\infty d_n=\sum\limits_{n=0}^\infty \frac{(-1)^n}{n+1}$ which is a well known expansion of $\log 2$.

-

as you have computed $x_{n+1}-x_n=-n(x_n-x_{n-1})/(n+1)$

we have $(n+1)(x_{n+1}-x_n)=-n(x_n-x_{n-1})$

then denote $g(n) = n(x_n-x_{n-1})$

we have $g(n+1) = -g(n)$

then $g(n) = (-1)^{n-1}g(1) = (-1)^{n-1}$

so $n(x_n-x_{n-1}) = (-1)^{n-1}$

$x_n-x_{n-1} = \frac{(-1)^{n-1}}{n}$

$x_n-x_m = \sum_{i=m+1}^{n}\frac{(-1)^{i-1}}{i}$

Now convergence of $x_n$ follows from convergence of $\sum{\frac{(-1)^n}{n}}$ and $x_n$ converges to $\ln{2}$

-

The sequence converges to $\log 2$.

You can show inductively the following:

a. $x_{2n}$ is increasing,

b. $x_{2n-1}$ is decreasing,

c. $x_{n+1}-x_n=\dfrac{(-1)^n}{n+1}$.

d. $x_n=\displaystyle\sum_{k=0}^n \dfrac{(-1)^{k-1}}{k}\to\log 2$.

-
@user2345215: Corrected! – Yiorgos S. Smyrlis Mar 4 '14 at 16:18