About the limit of a recursive sequence 
*

*The question is the following:


$x_0 >0$, $\forall n \in \mathbb{N},x_{n+1}=|x_n - n|$. Prove that $\lim_{n\to \infty} \frac{x_n}{n} = \frac{1}{2}$
I tried to remove the absolute value treating two cases:


*

*if, for any n, the n-th term of the sequence is greater than n, then the sequence $({x_n})$ converges and thus $(\frac{x_n}{n})$ tends to 0 as n tend to infinity.

*I wasn't able to deduce anything when $x_n<n$
 A: First, it comes handy to prove that, being $M\in \mathbb{N}$ the minimum of the naturals such that $x_n < n$, then we have that $x_n < n \hspace{.1cm} \forall n \geq M$. Prove this by induction.


*

*The set of naturals $n\in \mathbb{N}$ with $x_n < n$ is non-empty. Prove it by contradiciton, let's assume $x_n \geq n$ for all naturals, this sequence works as $x_n = x_0 - \sum_{i=1}^{n-1} i$, and knowing that $x_0$ finite and that sum diverges, we know there is a $M$ with $x_M < 0$, if this was the case. This is a contradiction because $x_M \geq M > 0$, so the set wasn't empty.

*Once $x_M < M$, the next element will be $x_{M+1} = |x_M - M| = M - x_M < M+1$, so we have that induction step proved.


Now it's way easier because we can just study what happens after $M$ where we know $x_n < n$. Let's call $k = x_M < M$. The first terms are $\{k, M-k, k+1, M-k+1, k+2, ... \}$, and if you keep going there will be an obvious pattern: we're adding $1$ each two steps, because:
$$x_{n+2} = n+1 - x_{n+1} = n+1 - n + x_n = 1 + x_n.$$
So when you calculate $x_n/n$ we can substitute that by:
$$\frac{k+(n-M)/2}{n}, \text{if } n-M | 2,$$
$$\frac{M-k+(n-M-1)/2}{n}, \text{if } n-M-1 | 2,$$
in both cases it's pretty clear that the limit is now $\frac{1}{2}$ because the constants doesn't matter when $n\rightarrow \infty$.
