Is $\max\{a_1,...,a_n\}+ \max\{b_1,...,b_m\}=\max_{(i,j)\in \{1,...,n\}\times \{1,...,m\}}\{a_i+b_j\}$

Question

Consider two finite sets of real numbers $\max\{a_1,...,a_n\}$, $\max\{b_1,...,b_m\}$.

Let $C$ be the sum of the maxima of the two sets, i.e., $$ C\equiv \max\{a_1,...,a_n\}+ \max\{b_1,...,b_m\}. $$

Is $C$ equal to the maximum of pairwise sums, i.e., $$ C=\max_{(i,j)\in \{1,...,n\}\times \{1,...,m\}}\{a_i+b_j\}? $$

I think the answer is yes, but I would like a formal proof (or a counterexample in case the answer is no)

Answer 1

In general, if $A,B$ are non empty we have $\sup (A+B) = \sup A + \sup B$.

If $a \in A, b \in B$ then $a+b \le \sup (A+B)$ hence $\sup A + b \le \sup (A+B)$, and so $\sup A + \sup B \le \sup (A+B)$.

Since $a +b \le \sup A + \sup B$ we have $\sup (A+B) \le \sup A + \sup B$.

In the above, we have $A=\{ a_k \}, B= \{ b_k \}$. Since $A,B$ are finite, we can replace the $\sup$ by $\max$.

Answer 2

Yes it is true. If $\max_i a_i = a_k$, say, and $\max_j b_j = b_l$, say, then $a_i + b_j \leq a_k + b_j \leq a_k + b_l$ for all pairs $(i,j)$, where the max of the LHS is obtained for the pair $(i,j) = (k,l)$.