View source for Maximum-minimums identity

{{short description|Relates the maximum element of a set of numbers and the minima of its non-empty subsets}}
In [[mathematics]], the '''maximum-minimums identity''' is a relation between the maximum element of a [[Set (mathematics)|set]] ''S'' of ''n'' numbers and the minima of the 2<sup>''n''</sup>&thinsp;−&thinsp;1 [[Empty set|non-empty]] [[subset]]s of ''S''.

Let ''S'' = {''x''<sub>1</sub>, ''x''<sub>2</sub>, ..., ''x''<sub>''n''</sub>}.  The [[identity (mathematics)|identity]] states that

:<math>\begin{align}
\max\{x_1,x_2,\ldots,x_{n}\} 
& = \sum_{i=1}^n x_i - \sum_{i<j}\min\{x_i,x_j\} +\sum_{i<j<k}\min\{x_i,x_j,x_k\} - \cdots \\
& \qquad \cdots + \left(-1\right)^{n+1}\min\{x_1,x_2,\ldots,x_n\},\end{align}</math>
or conversely

:<math>\begin{align}
\min\{x_1,x_2,\ldots,x_{n}\} 
& = \sum_{i=1}^n x_i - \sum_{i<j}\max\{x_i,x_j\} +\sum_{i<j<k}\max\{x_i,x_j,x_k\} - \cdots \\
& \qquad \cdots + \left(-1\right)^{n+1}\max\{x_1,x_2,\ldots,x_n\}.
\end{align}
</math>

<!--
OK, this didn't go as planned
==Inductive proof==
Clearly the identity holds for ''n'' = 1. Assume it holds for ''n'' and let 
:<math>
M_n = \max(x_1,x_2,\ldots,x_n)
</math>
Then for arbitrary ''x''<sub>''n''+1</sub>,
:<math>
M_{n+1} = \max(x_{n+1}, M_n)
</math>
and
:<math>
M_{n+1} = x_{n+1} + M_n - \min(x_{n+1}, M_n)
</math>
By the inductive hypothesis,
:<math>
M_{n+1} = x_{n+1} + \sum_{i=1}^n x_i - \sum_{i<j}\min(x_i,x_j) +\sum_{i<j<k}\min(x_i,x_j,x_k) +\cdots+\left(-1\right)^{n+1}\min(x_1,x_2,\ldots,x_n) - \min(x_{n+1}, \sum_{i=1}^n x_i - \sum_{i<j}\min(x_i,x_j) +\sum_{i<j<k}\min(x_i,x_j,x_k) +\cdots+\left(-1\right)^{n}\min(x_1,x_2,\ldots,x_n))
</math>
collecting terms and applying the fact that the minimum operator is [[distributive property|distributive]],
:<math>
M_{n+1} = \sum_{i=1}^{n+1} x_i - \sum_{i<j}\min(x_i,x_j) +\sum_{i<j<k}\min(x_i,x_j,x_k) +\cdots+\left(-1\right)^{n+1}\min(x_1,x_2,\ldots,x_n) - \min(x_{n+1}, \sum_{i=1}^n x_i) + \min(x_{n+1}, \sum_{i<j}\min(x_i,x_j)) - \min(x_{n+1},\sum_{i<j<k}\min(x_i,x_j,x_k) )+\cdots+\min(x_{n+1}, \left(-1\right)^{n+1}\min(x_1,x_2,\ldots,x_n))
</math>
-->
For a probabilistic proof, see the reference.

== See also ==

* [[Inclusion–exclusion principle]]
* {{section link|Maxima and minima|In relation to sets}}

==References==
* {{cite book | last = Ross | first = Sheldon | title = A First Course in Probability | publisher = Prentice Hall | location = Englewood Cliffs | year = 2002 | isbn = 0-13-033851-6 | url-access = registration | url = https://archive.org/details/firstcourseinpro00ross }}

[[Category:Mathematical identities]]