The average of a bounded, decreasing-difference sequence

(not sure if "decreasing-difference" is the right way to put it - please edit away if you know the proper technical term)

From my analysis homework:

Does there exist a bounded sequence $\{x_n\}_{n \in \mathbb{N}}$ such that $x_{n+1}-x_n \to 0$, but the sequence $(\sum_{i=1}^n x_i)/n$ does not have a limit? Give an example or show none exist.

In a previous part, I showed that there exists a bounded sequence $\{x_n\}_{n \in \mathbb{N}}$ such that $\left| x_{n+1}-x_n \right| \to 0$, yet $x_n$ does not converge, using a rearrangement of the alternating harmonic series.

Intuitively, I believe none exist. I've tried showing that the sequence is Cauchy, but that does not seem to help:

$$\left| \frac{ \sum_{i=1}^m x_i}{m} - \frac{ \sum_{i=1}^n x_i}{n} \right| = \left| \frac{ (n-m) \sum_{i=1}^m x_i - m \sum_{i=m+1}^n x_i}{mn} \right|$$

I feel like I can't use my normal series tools because I am looking at an average, and the series does not necessarily converge.

-
I think you're confusing the question. You've taken $x_n =\frac{1}{n}$. It satisfies the first condition and the sum also diverges. So there is your example. Why would you want to prove that none exists? – Please Delete Account Mar 13 '11 at 22:21
But if I take $x_n = \frac{1}{n}$, then $(\sum_{i=1}^n x_i)/n = \sum_{i=1}^n \frac{1}{(i)(n)} \leq \sum_{i=1}^n \frac{1}{i^2}$, which converges. Am I missing something here? – Michael Chen Mar 13 '11 at 23:32
I think this is equivalent to finding a sequence $\{x_n \}$ such that $\frac{\left(\sum_{i=1}^{n} x_i \right)}{n} \to L$ but $x_{n+1}-x_n \not \to 0$. – PEV Mar 14 '11 at 1:11

Edit 2: for your actual question, the answer is yes, you can find counterexamples. Consider the sequence $(1/n)$, and build your sequence as follows.

Start at $x_1 = 1$, and let $\alpha_1$ be a running counter which we start at 2. We then alternate between a decreasing phase and an increasing phase.

Decreasing phase: let $x_i = x_{i-1} - 1/\alpha_{i}$ if $x_{i-1} > 1/\alpha_i$. And increase $\alpha_{i+1} = \alpha_i + 1$. If $x_{i-1} < 1/\alpha_i$, set

$$x_i = x_{i+1} = \cdots = x_{100i} = x_{i-1}\qquad \qquad \alpha_{100i + 1} = \alpha_{i}$$

and then enter the increasing phase starting from the $100i+1$'th term.

Increasing phase: let $x_i = x_{i-1} + 1/\alpha_i$ if $x_{i-1} + 1/\alpha_i < 1$. And increase $\alpha_{i+1} = \alpha_{i} + 1$. Else set

$$x_i = x_{i+1} = \cdots = x_{100i} = x_{i-1} \qquad \qquad \alpha_{100i + 1} = \alpha_{i}$$

and enter the decreasing phase starting from the $100i+1$'th term.

Due to the long constant phases, you see that $\limsup_{n\to\infty} \frac{1}{n} \sum_1^n x_i = 1$, and the $\liminf = 0$. (The length of the constant phases grow exponentially, so that each constant phase completely dominates all previous terms in the average.)

The sequence looks like this:

1, 1/2, 1/6, {300 terms of 1/6}, 5/12, 37/60, 47/60, 389/420, {repeat 30700 times}, 673/840 ...

Edit: oh wait, the below doesn't actually address your question.

As a side note, the limit $\lim_{n\to\infty} \frac1n \sum_1^n x_i$ is known as the Cesàro mean of the sequence $x_i$. It is a fact that for any converging sequence $x_i\to \bar{x}$, the sequence $c_n = \frac{1}{n} \sum_1^n x_i$ also converges to $\bar{x}$.

To do this, let $\delta > 0$. It suffices to find $N$ large enough that for all $m > N$, $|c_m - \bar{x}| < \delta$. Because $x_i\to \bar{x}$, we can find $I$ large such that for all $j > I$, $|x_i - \bar{x}| < \delta / 3$. Now choose $N > I$ large enough such that

$$\sum_1^I x_i < \frac{\delta}{3}N \qquad \textrm{and} \qquad \frac{I}{N} < \frac{\delta}{3|\bar{x}|}$$

Then we have for all $m > N$:

$$m c_m = \sum_1^I x_i + \sum_{I+1}^m x_i$$

$$|c_m - \bar{x}| \leq | \frac{1}{m} \sum_1^I x_i | + | \frac{1}{m} \sum_{I+1}^m x_i - \bar{x} |$$

The first term on the right hand side is bounded by $\delta/3$. The second term we estimate

$$|\frac{1}m \sum_{I+1}^m x_i - \bar{x}| \leq |\frac{1}{m} \sum_{I+1}^m (x_i - \bar{x})| + |\frac{I}{m} \bar{x}|$$

and by construction both of the terms on the RHS are bounded by $\delta / 3$. So we have the desired inequality.

-
Basically, the idea is to take the bounded sequence with decreasing differences that is not converging, and force it to stay at the same place for longer and longer periods of time whenever it gets close to, or exceeds, the $\limsup$ and $\liminf$. This way you force the average of the function to also have roughly the same $\limsup$ and $\liminf$, and so you get non-convergence. – Willie Wong Mar 14 '11 at 2:10
Aha, that does it! Thanks! – Michael Chen Mar 17 '11 at 14:18