Elegant proof that maximum of sums is, at most, sum of maximums I'm looking for an elegant way to show that, among non-negative numbers,
$$
\max \{a_1 + b_1, \dots, a_n + b_n\} \leq \max \{a_1, \dots, a_n\} + \max \{b_1, \dots, b_n\}
$$
I can show that $\max \{a+b, c+d\} \leq \max \{a,c\} + \max \{b,d\}$ by exhaustively checking all possibilities of orderings among $a,c$ and $b,d$.
But, I feel like there should be a more intuitive/efficient way to show this property for arbitrary sums like the one above.
 A: For any index $j$, $a_j+b_j\leq \max\{a_1,\dots,a_n\}+\max\{b_1,\dots,b_n\}$. Now take the maximum over all $j$.
A: How about proof by induction?
You've proved the following by slogging it out. 
max(a+b,c+d) <= max(a,c) + max(b,d)
To show the induction step, consider the case for three terms:
max(a+b,c+d,e+f) = max(max(a+b,c+d), e+f )    ( max is associative).
             = max( max(a,c) + max(b,d), e+f)  (1st application of result).            

               max( max(a,c)+e) ) + max( max(b,d)+ f)  (2nd application of  result).

               max(a,c,e) + max(b,d,f)  (associativity of max).

This is the pattern for the general case, adding the n+1 term x+y 
max(a+b,c+d,.....y+z) = max(max(a+b,c+d,....), y+z )
             = max( max(a,c,...) + max(b,d,....), y+z)
               max( max(a,c,.....)+y) ) + max( max(b,d,.....) + z)

                    max(a,c,.....,y) + max(b,d,.....z)

A: More than this is true.
Let $P$ be a permutation of
$[1, 2, ..., n]$.
Then
$\max \{a_1 + b_{P(1)}, \dots, a_n + b_{P(n)}\} 
\leq \max \{a_1, \dots, a_n\} + \max \{b_1, \dots, b_n\}
$.
This is proved
in the same way
as carmichael561's proof:
For all $i$ from
$1$ to $n$,
$a_i \le \max \{a_1, \dots, a_n\} $
and
$b_{P(i)} \le \max \{b_1, \dots, b_n\}
$
so
$a_i+b_{P(i)}
\le \max \{a_1, \dots, a_n\} + \max \{b_1, \dots, b_n\}
$.
The similar,
but reversed inequality
holds 
for $\min$.
