Putnam 2001, Problem B-6

Assume that $(a_n)_{n \geq 1}$ is an increasing sequence of positive real numbers such that $\lim_{n \to \infty} a_n/n = 0$. Must there exist infinitely many positive integers $n$ such that $a_{n-i} + a_{n+i} < 2a_n$ for $i = 1, 2, \ldots, n-1$?


Solution:
Yes, there must exist infinitely many such $n$. Let $S$ be the convex hull of the set of points $(n,a_n)$ for $n \geq 0$. Geometrically, $S$ is the intersection of all convex sets (or even all halfplanes) containing the points $(n,a_n)$; algebraically, $S$ is the set of points $(x,y)$ which can be written as $c_1(n_1,a_{n_1}) + \cdots + c_k(n_k,a_{n_k})$ for some $c_1,\ldots,c_k$ which are nonnegative of sum 1.

We prove that for infinitely many $n$, $(n,a_n)$ is a vertex on the upper boundary of $S$, and that these $n$ satisfy the given condition. The condition that $(n,a_n)$ is a vertex on the upper boundary of $S$ is equivalent to the existence of a line passing through $(n,a_n)$ with all other points of $S$ below it. That is, there should exist $m > 0$ such that
$$a_k < a_n + m(k-n) \quad \forall k \geq 1. \tag{1}$$

We first show that $n = 1$ satisfies (1). The condition $a_k/k \to 0$ as $k \to \infty$ implies that $(a_k - a_1)/(k-1) \to 0$ as well. Thus the set $\{(a_k - a_1)/(k-1)\}$ has an upper bound $m$, and now $a_k \leq a_1 + m(k-1)$, as desired.

Next, we show that given one $n$ satisfying (1), there exists a larger one also satisfying (1). Again, the condition $a_k/k \to 0$ as $k \to \infty$ implies that $(a_k - a_n)/(k-n) \to 0$ as $k \to \infty$. Thus the sequence $\{(a_k - a_n)/(k-n)\}_{k>n}$ has a maximum element; suppose $k = r$ is the largest value that achieves this maximum, and put $m = (a_r - a_n)/(r-n)$. Then the line through $(r,a_r)$ of slope $m$ lies strictly above $(k,a_k)$ for $k > r$ and passes through or lies above $(k,a_k)$ for $k < r$. Thus (1) holds for $n = r$ with $m$ replaced by $m - \epsilon$ for suitably small $\epsilon > 0$.

By induction, we have that (1) holds for infinitely many $n$. For any such $n$ there exists $m > 0$ such that for $i = 1,\ldots,n-1$, the points $(n-i,a_{n-i})$ and $(n+i,a_{n+i})$ lie below the line through $(n,a_n)$ of slope $m$. That means $a_{n+i} < a_n + mi$ and $a_{n-i} < a_n - mi$; adding these together gives $a_{n-i} + a_{n+i} < 2a_n$, as desired.