# Proof for $\max (a_i + b_i) \leq \max a_i + \max b_i$ for $i=1..n$

I know this question is almost trivial because the truth of this statement is completely intuitive, but I'm looking for a nice and as formal as possible proof for $$\max (a_i + b_i) \leq \max a_i + \max b_i$$ with $i=1,\ldots,n$

Federico

-
Let $\max a_i=A$ and $\max b_i=B$. Then $\dots$. –  André Nicolas Sep 1 '11 at 18:35
"Take some of the subexpressions of the formula, and abbreviate them as single letters". Not much of a hint, I'd say. –  Henning Makholm Sep 1 '11 at 18:44
$\dots a_i\le A$ and $b_i\le B$, and therefore $a_i+b_i \le A+B$. –  André Nicolas Sep 1 '11 at 18:50

Choose $j$ so that $a_j=\max a_i$ and $k$ so that $b_k=\max b_i$ (where it is possible that $j=k$). Then for each $i$, $a_i+b_i \le a_j+b_k$, so $\max a_i+b_i \le a_j+b_k=\max a_i + \max b_i$
For any choice of $j$ in $1,2,\ldots,n$, we have that $$a_j\leq\max\{a_i\}\quad\text{and}\quad b_j\leq\max\{b_i\}$$ by the very definition of "$\max$". Then, by additivity of inequalities, we have that for each $j$, $$a_j+b_j\leq\max\{a_i\}+\max\{b_i\}.$$ But because this is true for all $j$, it is true in particular for the largest out of the $a_j+b_j$'s; that is, $$\max\{a_i + b_i\} \leq \max\{a_i\} + \max\{b_i\}$$
$$\max_{1\le i \le n} (a_i + b_i) \le \max_{1\le i \le n}( \max_{1\le k \le n}(a_k) + b_i) = \max_{1\le k \le n}(a_k) + \max_{1\le i \le n}(b_i)$$