*This is an exercise proposed by Timothy Gowers: Write down all you think of while trying to solve a math problem.*

**Problem.**
Let $a_0\lt a_1\lt a_2\cdots$ be an infinite sequence of positive integers.
Prove that there exists a unique integer $n\ge1$ such that
$$a_n \le \frac{a_0+\cdots+a_n}{n} \le a_{n+1}$$

**Brain dump.**
First, it's curious that the sum of $n+1$ numbers is divided by $n$, instead of $n+1$.
Second, the fact that the sequence is *strictly* increasing is clearly important.
These two seem to indicate that I might want to look at differences:
(1) there are $n$ differences between $n+1$ numbers, and
(2) these differences are positive.
So, let's set $b_n=a_{n+1}-a_n$.
Then $a_0+\cdots+a_n$ is $b_0+\cdots+b_{n-1}$ (just $n$ numbers!).

Hmm $\ldots$ I need some way to express the $a_n\lt\cdots\lt a_{n+1}$ part of the inequality. It seems convenient to set $a_{-1}=0$ and change the definition of $b_n$ to $a_n-a_{n-1}$. Then the initial inequality is $\ldots$

(Oh, dear: I just noticed that I made a terrible mistake earlier. The sum $a_0+\cdots+a_n$ is not what I said. Anyway, now I changed the definition of $b_n$, so let's see what is it supposed to be using the new definition.)

$\ldots$ so, the initial inequality is $$ b_0+\cdots+b_n \le \frac{(n+1)b_0+nb_1+(n-1)b_2+\cdots+b_n}{n} \le b_0+\cdots+b_{n+1}$$ This one can be rearranged as $$ 0 \le (n+1)b_0+nb_1+\cdots+b_n \le nb_{n+1}$$ OK, it looks like the left part always hold. I need to compile this and look at the equations to check if they're OK $\ldots$ Seems fine.

Right. On to the second part of the inequality. We have two parts here. First, to show that the inequality eventually holds, as $n$ increases. Second, to show that once it holds, it cannot hold for bigger $n$. Let's unpack the inequality for a few small values of $n$: \begin{align} b_0 &\le 0 \\ 2b_0 + b_1 &\le b_2 \\ 3b_0 + 2b_1 + b_2 &\le 2b_3 \\ 4b_0 + 3b_1 + 2b_2 + b_3 &\le 3b_4 \end{align} The first inequality can't be true because $b$s are positive. The second could be so let's suppose it is. How does this imply that the third inequality doesn't hold?

(OK.
I'm just terrible.
Earlier I said I need to check some inequalities, said I did, and all is well.
They are *wrong*!
They are *so* wrong.
I'm very tempted to find excuses and blame my family who keeps interrupting, asking questions about the history of the coffee machine, whether I really want to sit on the floor instead of going to the table, and whatnot.)

Anyway, for the third time $\ldots$ the initial inequality, expressed in terms of $b$s, is:
$$ 0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) \le nb_{n+1}$$
The left part does *not* always hold.
In fact, it's clear that it holds in the beginning ($0\le b_0$) but will eventually fail, because its right side keeps decreasing.
So, let's look at what happens at that step.
That is, we pick $n$ such that
$$ 0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) $$
and
$$ 0 \gt b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n + nb_{n+1}) $$
Or, rewritten
$$ (b_2+2b_3+\cdots+(n-1)b_n) \le b_0 \le (b_2+2b_3+\cdots+nb_{n+1}) $$
The first question is what happens with the other inequality at this $n$.
The second question is what happens in general with the other inequality, not only at this $n$.
Actually, part of the second question is very easy to answer: for bigger $n$ the right inequality holds, because the middle term is negative, while the right one is positive.
For $n$ itself, the right inequality still holds: just add $nb_{n+1}$ to both sides of $0>b_0-(\ldots)$.

All that is left to do at this point is to show that for smaller $n$ than the picked one, the right inequality fails.

(I should say that at this point I feel close to the answer, and I let myself be distracted by what people talk around me.
Now that I think about it, I may *not* be close to the answer.
What I did so far feels rather easy, so the perhaps all I did was to reach the hard part.
Let's continue.)

What happens at $n-1$?
$$ 0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-2)b_{n-1}) \le (n-1)b_n$$
Subtract $(n-1)b_n$:
$$ -(n-1)b_n \lt 0\le b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) \le 0$$
This is not immediately a contradiction, although it would've been if I would've looked at $n-2$ instead of $n-1$.
I'm a bit confused as to why this doesn't seem like a contradiction, so let's look at an example.
I pick $b$s to be $3, 1, 1, 1, \ldots.$
Then
\begin{align}
&b_0 - (b_2 + 2b_3 + 3b_4 + \cdots + (n-1)b_n) &&\text{is} &&3,2,0,-3,-7,\ldots \\
&nb_{n+1} &&\text{is} && 0,2,2,\phantom{-}2,\phantom{-}2,\ldots
\end{align}
It looks like indeed there are *two* $n$s such that both inequalities hold.
What mistake did I do?
Let me check in terms of the original statement.
$$\begin{align}
&n &&0 &&1 &&2 &&3 &&4 \\
&a_n &&3 &&4 &&5 &&6 &&7 \\
&\sum_{k\le n} a_k
&&3 &&7 &&12 &&18 &&25 \\
&\sum/n
&& &&7 &&6 &&6 &&6.25
\end{align}$$
I'm confused:
It seems both $n=2$ and $n=3$ work.
I will now go and brush my teeth.

**Update:**
My mistake was in the copying of the problem statement.
This was revealed in comments back at the original post.

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.