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?


  • 2
    $\begingroup$ No, the second part is wrong. $\endgroup$ – xpaul Apr 26 '16 at 17:43
  • $\begingroup$ Yes, sequence must be decreasing or increasing on all $n$ , what's about second statement? $\endgroup$ – Evgeny Semyonov Apr 26 '16 at 17:45
  • $\begingroup$ 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?) $\endgroup$ – Théophile Apr 26 '16 at 18:18
  • $\begingroup$ @Théophile Part 1: $0 \le x_n \le 1$ $\endgroup$ – Evgeny Semyonov Apr 26 '16 at 18:21
  • 1
    $\begingroup$ 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. $\endgroup$ – Théophile Apr 26 '16 at 18:23


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:

Plot for $0\leq n\leq 35$

  • 2
    $\begingroup$ 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$. $\endgroup$ – Clement C. Apr 26 '16 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.