$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.

Solution 1:

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$.

Solution 2:

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.

Solution 3:

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.