Elegant proof that maximum of sums is, at most, sum of maximums

Question

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.

Answer 1

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$.

Answer 2

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)

Answer 3

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$.