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.

  • 1
    $\begingroup$ While the sequence is bounded it's not monotone, so that will lead us to nothing. $\endgroup$ – Stefan4024 Jun 28 '16 at 18:34
  • $\begingroup$ Refer to this answer to other post $\endgroup$ – G Cab Oct 30 '16 at 0:07

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.

  • $\begingroup$ I think you can just use induction on $m$ to show that convergence of $y_{n}$ implies convergence of $x_{n}$. $\endgroup$ – Seewoo Lee Jun 29 '16 at 8:00
  • $\begingroup$ Refer to this answer to other post $\endgroup$ – G Cab Oct 30 '16 at 0:08

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


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.


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.