Convergence of positive sequence in which each term is less than the average of preceding 2 terms It is easy to prove any sequence generated by
$$
x_{n+1}:=\frac{x_n+x_{n-1}}{2}
$$
is convergent. But how about if the sequence only satisfies
$$
0\leq x_{n+1}\leq\frac{x_n+x_{n-1}}{2}
$$
with positive $x_0$ and $x_1$?

@Martin R gives a proof. Could this result be extended to $n$ preceding terms?
 A: Yes, such a sequence is necessarily convergent. One possible approach is to show that $(\max(x_n, x_{n+1}))_n$ is a monotonically decreasing sequence which is bounded below and therefore is convergent. Then one can show that $(x_n)$ converges to the same limit.
In fact this works for the more general case where each sequence element is less than (or equal to) the average of the preceding $k$ elements, with a fixed $k \ge 2$. We have the following:

Let $(x_n)$ be a sequence of non-negative real numbers and $k \ge 2$ such that
  $$
 x_{n+k} \le \frac{x_n + \ldots + x_{n+k-1}}{k}
$$
  for all $n$. Then $(x_n)$ is convergent.

Proof: We consider the sequence $(y_n)$ defined as
$$
 y_n = \max(x_n, x_{n+1}, \ldots, x_{n+k-1}) \, .
$$
Then $x_{n+k} \le y_n$, so that
$$
 y_{n+1} = \max(x_{n+1}, \ldots, x_{n+k-1}, x_{n+k}) \\
 \le \max(x_{n+1}, \ldots, x_{n+k-1}, y_n) = y_n \, ,
$$
i.e. $(y_n)$ is a decreasing sequence (and bounded below by zero). It follows that
$$
 a = \lim_{n \to \infty} y_n 
$$
exists. Now we show that $(x_n)$ has the same limit $a$:
For $\epsilon > 0$ there is an $N$ such that
$$ \tag{*}
 a \le y_n = \max(x_n, x_{n+1}, \ldots, x_{n+k-1}) < a + \epsilon
$$
for $n \ge N$. We'll show that
$$
 a - (k-1)\epsilon < x_n < a + \epsilon
$$
for $n \ge N$. The right inequality is clear, since $x_n \le y_n < a + \epsilon$. It remains to show that $a - (k-1)\epsilon < x_n$.
Case 1: $x_n =  \max(x_n, x_{n+1}, \ldots, x_{n+k-1})$. Then $(*)$ gives
$$
a \le y_n = x_n \, .
$$
Case 2: $x_j = \max(x_n, x_{n+1}, \ldots, x_{n+k-1})$ for some $j \in \{  n+1, \ldots n+k-1 \}$. Then $(*)$ gives
$$
 a \le y_n = x_j \, .
$$
It follows that
$$
 ka \le k x_j \le x_{j-1} + x_{j-2} + \ldots + x_{j-k+1} 
\le x_n + (k-1) (a + \epsilon) 
$$
which implies
$$
a - (k-1) \epsilon < x_n \, .
$$
This concludes the proof.
A: The sequence converges to its superior limit.
Denote the superior limit by $a$. If there are finitely many terms below $a$, the sequence is eventually bounded below by its superior limit and thus convergent. So assume that there are infinitely many terms below $a$.
Two consecutive terms cannot both be below $a$, since the sequence could then never recover towards $a$. So the terms before and after a term below $a$ are at or above $a$. The distance of the second of these from $a$ can be at most half the distance of the first from $a$. Thus the terms at or above $a$ converge towards $a$. But a term below $a$ cannot be further below $a$ than the term before it is above $a$ (since otherwise the following term would again be below $a$). Thus the terms below $a$ also converge to $a$.
