Putnam

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, \dots, 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
$$\text{a k < a n + m(k-n) k 1.}$$

We first show that $n=1$ satisfies $\text{( ).}$ 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 $\text{( ),}$ there exists a larger one also satisfying $\text{( ).}$ 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 $\text{( )}$ holds for $n=r$ with $m$ replaced by $m-\epsilon$ for suitably small $\epsilon > 0$.

By induction, we have that $\text{( )}$ holds for infinitely many $n$. For any such $n$ there exists $m>0$ such that for $i=1, \dots, 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.