$x_{n+m}\le \frac{x_n+x_{n+1}+\cdots+x_{n+m-1}}{m}$. Prove that this sequence has a limit. 
Let $m \ge 2 -$ fixed positive integer. The sequence of non-negative real numbers $\{x_n\}_{n=1}^{\infty}$ is that for all $n\in \mathbb N$
  $$x_{n+m}\le \frac{x_n+x_{n+1}+\cdots+x_{n+m-1}}{m}$$
  Prove that this sequence has a limit.

I know I need to prove 1) the sequence is monotone; 2) the sequence is limited. But I can not do any of these items. 
 A: The following solution is due to Dean Hickerson (but any errors are mine):

Let $\color{blue}{M_n=\max\{x_n, x_{n+1}, \cdots, x_{n+m-1}\}}$ for each $n$.
Since $x_{n+m}$ is less than or equal to the average of the previous $m$ terms, $x_{n+m}\le M_n$; hence $M_{n+1}\le M_n$.
Therefore $(M_n)$ is a nonincreasing sequence bounded below by zero, so
$\displaystyle\lim_{n\to\infty}M_n$ exists;  call it A.  
Obviously $\displaystyle A=\limsup_{n\to\infty}x_n$; I claim that also $\displaystyle A=\liminf_{n\to\infty} x_n$.

If not, then there's a number $B<A$ such that there are infinitely many $n$ with
$x_n < B$.  
Choose such an $n$ so large that  $\displaystyle x_k < A + \frac{A-B}{m-1}$  for all  $k\ge n-m$.
$\hspace{.25 in}$[Choose $N$ with $M_N<A+\frac{A-B}{m-1}$, and then choose $n>N+m$ with $x_n<B$.]
Then $\color{blue}{\displaystyle x_{n+i} \le \frac{x_{n+i-m} + \cdots + x_{n+i-1}}{m}}$ for $1\le i\le m$.
The $x's$ being averaged here include $x_n$, which is less than B; 
and the other $m-1$  $x's$
are each less than $\displaystyle A + \frac{A-B}{m-1}$, so
$\color{blue}{\displaystyle x_{n+i} < \frac{B + (m-1)(A + \frac{A-B}{m-1})}{m}=\frac{B+(m-1)A+A-B}{m}=A}$ for $1\le i\le m$.
Therefore $M_{n+1}<A$, contradicting the fact that $(M_n)$ is a
decreasing sequence with limit $A$.

Thus $\displaystyle\liminf_{n\to\infty}x_n=A=\limsup_{n\to\infty}x_n, \text{ so }\lim_{n\to\infty}x_n=A$.
A: I'll show for only $m=2$, and this method can be easily generalized to $m\geq 3$. 
Boundedness of sequence can be shown by induction on $n$. Suppose $\{x_{n}\}$ satisfies $x_{n+2}\leq \frac{x_{n}+x_{n+1}}{2}$ for all $n\geq 1$. 
Now, define $y_{n}:=x_{n}+2x_{n+1}$, then the condition is equivalent to $y_{n+1}\leq y_{n}$, i.e. $y_{n}$ is monotone decreasing. Since $x_{n}$ is bounded, $y_{n}$ is also bounded so it converges to some $\alpha\geq 0$ by monotone convergence theorem. Now, by definition we can show
\begin{align}
x_{n+1}=\frac{1}{2}y_{n}-\frac{1}{4}y_{n-1}+\cdots+(-1)^{n-1}\frac{1}{2^{n}}y_{1}+(-1)^{n}\frac{1}{2^{n}}x_{1}
\end{align}
in many ways. 
We claim that $\lim_{n\to \infty} x_{n}=\frac{\alpha}{3}$ (this is the only candidate for the limit of sequence $x_{n}$ because of $y_{n}=x_{n}+2x_{n+1}$). 
For any $\epsilon>0$, there exists $N$ s.t $|y_{n}-\alpha|<\epsilon$ for $n>N$. Then
\begin{align}
\Bigl|x_{n+1}-\frac{\alpha}{3}\Bigr|&=\Bigr|\frac{1}{2}(y_{n}-\alpha)-\frac{1}{4}(y_{n-1}-\alpha)+\cdots+(-1)^{n-1}\frac{1}{2^{n}}(y_{1}-\alpha)+(-1)^{n}\frac{1}{2^{n}}x_{1}-\frac{1}{3}\left(-\frac{1}{2}\right)^{n}\alpha\Bigr| \\
&\leq \left(\frac{1}{2}+\cdots+\frac{1}{2^{n-N}}\right)\epsilon+\frac{1}{3}\left(\frac{1}{2}\right)^{n}\alpha+\frac{1}{2^{n}}x_{1}+\Bigl|\frac{1}{2^{n+1-N}}(y_{N}-\alpha)+\cdots+\frac{(-1)^{N-1}}{2^{n}}(y_{1}-\alpha)\Bigr| \\
&\leq \epsilon+\frac{1}{3}\left(\frac{1}{2}\right)^{n}\alpha+\frac{1}{2^{n}}x_{1}++\frac{1}{2^{n}}(2^{N}-1)M
\end{align}
where $M=y_{1}-\alpha$ (note that $0\leq y_{n}-\alpha\leq y_{1}-\alpha$). Since last expression goes to $0$ as $\epsilon\to 0$ and $n\to \infty$, we get the desired result. 
For the general $m$, use
\begin{align}
y_{n}:=x_{n}+2x_{n+1}+\cdots+mx_{n+m-1}
\end{align}
which is monotone decreasing and bounded, so converges. If $\lim_{n\to\infty}y_{n}=\alpha$, then we can show that $\lim_{n\to \infty} x_{n}=\frac{2}{m(m+1)}\alpha$. I think computation would be much more complicated. 
A: One can also view this problem probabilistically in light of the renewal theory. To see this, let $a_k = \frac{1}{m}$ for $k=1,\ldots,m$ and $b_n = x_n -\frac{1}{m}(x_{n-1}+\cdots+ x_{n-m})$. (We regard $x_j=0$ for non-positive integers $j$.) Then we may write the given condition in the form of a (discrete) renewal equation:
$$x_n = -b_n +\sum_{k=0}^{n}x_{n-k}a_k, \quad \forall n\geq 0.$$
According to the Blackwell's renewal theorem(Or Key renewal theorem), if $b_n$ is absolutely summable and $0<\sum_{j\geq 0} ja_j\leq\infty$, then the limit of $x_n$ exists and is equal to
$$\lim_{n\to \infty} x_n = -\frac{\sum_{j= 0}^\infty b_j}{\sum_{j= 0}^\infty ja_j}.$$
We can easily see that $\sum_{j= 0}^\infty ja_j = (m+1)/2>0$, so it remains to show $\sum_j |b_j| <\infty$. Since $b_n\geq 0$ for all $n\geq m$, it suffices to show $\sum_{j\geq m} b_j$ is bounded. However, a little bit of calculation easily shows that
$$\sum_{j= m}^N b_j =\sum_{0\leq j \leq m-1} (1-\frac{j}{m})\left(x_{N-j}-x_j\right)\leq 2m\cdot\left(\sup_{j\geq 1} x_j\right),$$giving the desired result.
