IRL ABooklet

We claim that concavity of $(a_n)$ implies that
$$a_i + a_j \le 2a_{(i+j)/2}, \quad \text{for all non-negative } i, j \in \mathbb{Z}, \qquad (31)$$
where $a_r$ is defined for $r$ halfway between two integers as follows:
$$a_{n-1/2} := \frac{a_{n-1} + a_n}{2} \quad \text{for all } n \in \mathbb{N}. \qquad (32)$$

Because of its symmetry, it suffices to prove (31) when $i \le j$. Writing $d = j-i$ and $m = (i+j)/2$, we are required to prove
$$a_{m-d/2} + a_{m+d/2} \le 2a_m, \qquad (34)$$
where $m$ and $d$ can take on any values allowed by their definition in terms of $i, j$; in particular, $m$ is an integer if and only if $d$ is even so that $m \pm d/2$ are always integers in (34).

We proof (34) by induction. It is trivially true if $d = 0$, it follows from (33) if $d = 1$, and from the assumed concavity if $d = 2$. Suppose inductively that (34) holds for all $d < p$ for some integer $p \ge 3$ (and all valid associated values of $m$). We then need to prove it for $d = p$. There are two cases to consider.

Case 1. $p = 2q$ is even (and so $m$ is an integer). We need to prove
$$a_{m-q} + a_{m+q} \le 2a_m.$$
We use the assumption (34) for $d = q < p$ and replace $m$ by $m \pm q/2$ to get
$$a_{m-q} + a_m \le 2a_{m-q/2} \quad \text{and} \quad a_m + a_{m+q} \le 2a_{m+q/2}.$$
Adding and rearranging gives
$$a_{m-q} + a_{m+q} \le 2a_{m-q/2} + 2a_{m+q/2} - 2a_m. \quad (35)$$
If $q$ is even, we use (34) with $d = q$ to get $a_{m-q/2} + a_{m+q/2} \le 2a_m$ which implies the required inequality.
If $q = 2t + 1$ is odd, we use (34) with $d = 2t$ and $d = 2t + 2 < 4t + 2 = p$. Note that $t > 0$ because $p > 2$. We get
$$a_{m-t} + a_{m+t} \le 2a_m \quad \text{and} \quad a_{m-t-1} + a_{m+t+1} \le 2a_m.$$
Together with definition (32) this gives
$$\begin{aligned} a_{m-q/2} + a_{m+q/2} &= a_{m-t-1/2} + a_{m+t+1/2} \\ &= \frac{1}{2} (a_{m-t-1} + a_{m-t} + a_{m+t} + a_{m+t+1}) \le 2a_m \end{aligned}$$
which again implies the required inequality.

Case 2. $p = 2q - 1$ is odd (and so $m$ is not an integer). We need to prove
$$a_{m-q+1/2} + a_{m+q-1/2} \le 2a_m.$$
We use the assumption (34) for $d = q - 1 < p$ and replace $m$ by $m \pm q/2$ to obtain
$$a_{m-q+1/2} + a_{m-1/2} \le 2a_{m-q/2} \quad \text{and} \quad a_{m+1/2} + a_{m+q-1/2} \le 2a_{m+q/2}.$$
Adding, rearranging and using (33) gives
$$a_{m-q+1/2} + a_{m+q-1/2} \le 2a_{m-q/2} + 2a_{m+q/2} - 2a_m. \quad (36)$$

Now, to prove the statement for $(c_n)$, note that for any $n \ge 0$,
$$c_n = \max_{0 \le i \le n} (a_i + b_{n-i})$$
Let $i_0$ be the index where the maximum is attained for $c_n$, i.e., $c_n = a_{i_0} + b_{n-i_0}$.

Consider $c_{n-1}$ and $c_{n+1}$:
$$c_{n-1} = \max_{0 \le j \le n-1} (a_j + b_{n-1-j})$$
$$c_{n+1} = \max_{0 \le k \le n+1} (a_k + b_{n+1-k})$$
For any $i_0$, we have
$$c_{n-1} \ge a_{i_0-1} + b_{n-i_0} \quad \text{(if $i_0 \ge 1$)}$$
$$c_{n+1} \ge a_{i_0+1} + b_{n-i_0} \quad \text{(if $i_0 \le n$)}$$
Similarly,
$$c_{n-1} \ge a_{i_0} + b_{n-i_0-1} \quad \text{(if $n-i_0 \ge 1$)}$$
$$c_{n+1} \ge a_{i_0} + b_{n-i_0+1} \quad \text{(if $n-i_0 \le n+1$)}$$
Now, by concavity of $(a_n)$ and $(b_n)$,
$$a_{i_0} \ge \frac{a_{i_0-1} + a_{i_0+1}}{2}$$
$$b_{n-i_0} \ge \frac{b_{n-i_0-1} + b_{n-i_0+1}}{2}$$
Adding,
$$a_{i_0} + b_{n-i_0} \ge \frac{a_{i_0-1} + b_{n-i_0} + a_{i_0+1} + b_{n-i_0}}{2}$$
and
$$a_{i_0} + b_{n-i_0} \ge \frac{a_{i_0} + b_{n-i_0-1} + a_{i_0} + b_{n-i_0+1}}{2}$$
Thus,
$$c_n \ge \frac{c_{n-1} + c_{n+1}}{2}$$
Therefore, $(c_n)$ is concave.