# Find limit recursion of sequence $x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1}$

Prove sequence

$$x_{n+1} = \frac{x_n+ n x_{n-1}}{n+1}$$

$$x_0 = 0, x_1 = 1$$

converges and find it's limit

My attempt

1. Let's prove $0 \le x_n \le 1$:

$x_n \ge 0$ (obvious)

By induction

if $x_n \le 1$ and $x_{n-1} \le 1$ then: $$\frac{x_n+ n x_{n-1}}{n+1} \le \frac{1+ n}{n+1}=1 \implies x_{n+1}<=1$$

2. Let's prove convergence

$$\lim_{n \to \infty }{x_{n+1}} = \lim_{n \to \infty }{ \frac{x_n + n x_{n-1}}{n+1} } = \lim_{n \to \infty }{ (\frac{x_n}{n+1} } + \frac{x_{n-1}}{1+\frac{1}{n}}) = x_{n-1}$$

So, sequence converges.

Question: I'm right so far and how to find the limit?

Thanks

• No, the second part is wrong. – xpaul Apr 26 '16 at 17:43
• Yes, sequence must be decreasing or increasing on all $n$ , what's about second statement? – Evgeny Semyonov Apr 26 '16 at 17:45
• For part 2, notice that $n$ is an "internal variable" on the left-hand side (it's used for the purpose of the finding a limit), yet it appears as a fixed value on the right-hand side (in $x_{n-1}$). This tells you that something is off. Also, you seem to assume that $\frac{x_n}{n+1} = 0$. How do you know this? (What if $x_n \approx n$, for example?) – Théophile Apr 26 '16 at 18:18
• @Théophile Part 1: $0 \le x_n \le 1$ – Evgeny Semyonov Apr 26 '16 at 18:21
• Ah, sorry, I missed that. In any case, my first comment still holds; if $n$ appears inside a limit on the left, it shouldn't appear outside a limit on the right. – Théophile Apr 26 '16 at 18:23

## 1 Answer

Hint:

Check that $\displaystyle \forall n\geq 0, x_{n+1}-x_n=\frac{(-1)^n}{n+1}$

The series $\displaystyle \sum (x_{n+1}-x_n)$ is therefore convergent, and so is the sequence $(x_n)$, say $x_n\to l$

Furthermore, $\displaystyle l= \sum_{k=0}^\infty (x_{k+1}-x_k) =\sum_{k=0}^\infty \frac{(-1)^k}{k+1} = \log 2$.

Edit: from a simulation on Mathematica, here is the plot of the first few terms of the sequence, giving intuition about its behavior: • Without using series (but less immediate): Once you have the above relation between $x_{n+1}-x_n$, or even just show by induction that $x_{n+1}-x_n$ has alternating sign (e.g. by induction), it is easy to show that the sequence $(x_{2n})_n$ is increasing, and that $(x_{2n+1})_n$ is decreasing. Since both are bounded, both converge. And the limits are the same, since $x_{n+1}-x_n \to 0$. – Clement C. Apr 26 '16 at 17:54