Micromass' big August challenge

[Erland]

Let me also give the nonstandard analysis proof I mentioned. To follow it, the reader needs some knowledge about nonstandard analysis, for which I refer to the literature.

We work in a nonstandard extension of some superstructure over $\mathbb R$. Every number, set, function etc. $x$ in this superstructure has a $*$-transform $^*x$ in the extended superstructure.
Let $\{x_n\}_{n\in \mathbb Z_+}$ be a bounded sequence in $\mathbb R$. Its $*$-transform $^*\{x_n\}_{n\in \mathbb Z_+}$is a bounded hypersequence $\{x_n\}_{n\in \,^*\mathbb Z_+}$ in $^*\mathbb R$.

Pick an infinite positive hyperinteger $H\in\, ^*\mathbb Z_+\setminus\mathbb Z_+$.
For each bounded real sequence $\{x_n\}_{n\in \mathbb Z_+}$, put $F(\{x_n\}_{n\in \mathbb Z_+})=st(x_H)$, i.e. the standard part of $x_H$ (in the corresponding hypersequence). It is easy to verify that $F$ is a real linear functional on the space $\mathcal B$ of all bounded real sequences.
It is also so that $\overline\lim x_n=\max_{K\in\, ^*\mathbb Z_+-\mathbb Z_+}st(x_K)$ and $\underline\lim x_n=\min_{K\in \,^*\mathbb Z_+-\mathbb Z_+}st(x_K)$, so $\underline\lim x_n\le F(\{x_n\}_{n\in \mathbb Z_+})\le \overline\lim x_n$.

Now, define $G: \mathcal B\to\mathcal B$ by $G(\{x_n\}_{n\in \mathbb Z_+}=\{y_n\}_{n\in \mathbb Z_+}$, where $y_n=\frac1n\sum_{k=1}^n x_n$ for all $n\in \mathbb Z_+$. Let $H_1=\,^*\lfloor \,^*\sqrt{H}\rfloor$. Then $H_1$ is an infinite positive hyperinteger such that $H_1/H$ is infinitesimal.

There is a real $M$ such that $|x_n|\le M$ for all $n\in \mathbb Z_+$, and the same holds for all $n\in ^*\mathbb Z_+$, with the same $M$. It follows that $\frac1H\,^*\sum_{k=1}^{H_1}x_k$ is infinitesimal and that $y_H=\frac1H\,^*\sum_{k=1}^{H}x_k$ is finite, and $F(\{x_n\}_{n\in \mathbb Z_+})=st(y_H)=st(\frac1H\,^*\sum_{k=H_1+1}^{H}x_k)$. By the characterizations of $\overline\lim x_n$ and $\underline\lim x_n$ above, this implies that $\underline\lim x_n\le F(\{y_n\}_{n\in \mathbb Z_+})\le \overline \lim x_n$.

With these $\{x_n\}_{n\in \mathbb Z_+}$ and $\{y_n\}_{n\in \mathbb Z_+}$, define $\{u_n\}_{n\in \mathbb Z_+}$ by $u_n=x_{n+1}$, for all $n\in \mathbb Z_+$, and put $\{z_n\}_{n\in \mathbb Z_+}=G(\{u_n\}_{n\in \mathbb Z_+})$. Then $F(\{z_n\}_{n\in \mathbb Z_+})-F(\{y_n\}_{n\in \mathbb Z_+})=st((x_{H+1}-x_1)/H)=0$.

So, if we put $L=G\circ F:\mathcal B\to\mathbb R$, then $L$ is linear, $\underline\lim x_n\le L(\{x_n\}_{n\in \mathbb Z_+})\le \overline \lim x_n$,
since $G(\{x_n\}_{n\in \mathbb Z_+})=\{y_n\}_{n\in \mathbb Z_+}$, and $L(\{u_n\}_{n\in \mathbb Z_+})=L(\{x_n\}_{n\in \mathbb Z_+})$, since $F(\{z_n\}_{n\in \mathbb Z_+})=F(\{y_n\}_{n\in \mathbb Z_+})$.

This means that $L$ satisfies 1, 2, 3, and 5, and hence 4 and 6, in the definition of generalized limit, so $L$ is a generalized limit.

If one tries to convert this proof to a "standard" proof, the result is something like my previous proof. So we see that nonstandard proofs are often considerably shorter!