Докажем, например, первое из приведённых соотношений.
Заметим, что если заменить
x
↦
x
+
a
{\displaystyle x\mapsto x+a}
, где
a
{\displaystyle a}
— произвольное число, то обе части доказываемого соотношения также изменятся на
a
{\displaystyle a}
.
Действительно, левая часть:
max
(
x
1
+
a
,
…
,
x
n
+
a
)
=
max
(
x
1
,
…
,
x
n
)
+
a
{\displaystyle \max(x_{1}+a,\ldots ,x_{n}+a)=\max(x_{1},\ldots ,x_{n})+a}
Правая часть:
∑
k
=
1
n
∑
i
1
<
…
<
i
k
(
−
1
)
k
−
1
min
(
x
i
1
+
a
,
…
,
x
i
k
+
a
)
=
=
∑
k
=
1
n
∑
i
1
<
…
<
i
k
(
−
1
)
k
−
1
min
(
x
i
1
,
…
,
x
i
k
)
+
a
∑
k
=
1
n
(
−
1
)
k
−
1
∑
i
1
<
…
<
i
k
1
{\displaystyle {\begin{aligned}\sum _{k=1}^{n}\sum _{i_{1}<\ldots <i_{k}}(-1)^{k-1}\,&\min(x_{i_{1}}+a,\ldots ,x_{i_{k}}+a)=\\&=\sum _{k=1}^{n}\sum _{i_{1}<\ldots <i_{k}}(-1)^{k-1}\,\min(x_{i_{1}},\ldots ,x_{i_{k}})+a\sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1\end{aligned}}}
Второе слагаемое в точности равно
a
{\displaystyle a}
, в силу известного свойства биномиальных коэффициентов :
∑
k
=
1
n
(
−
1
)
k
−
1
∑
i
1
<
…
<
i
k
1
=
∑
k
=
1
n
(
−
1
)
k
−
1
(
n
k
)
=
1
{\displaystyle \sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1=\sum _{k=1}^{n}(-1)^{k-1}{n \choose k}=1}
Заменим теперь все
x
i
{\displaystyle x_{i}}
на
x
i
′
=
x
i
+
a
{\displaystyle x'_{i}=x_{i}+a}
, где
a
=
−
min
(
x
1
,
…
,
x
n
)
{\displaystyle a=-\min(x_{1},\ldots ,x_{n})}
. В силу вышеизложенных соображений соотношение для набора
x
i
′
{\displaystyle x'_{i}}
будет выполнено тогда и только тогда, когда выполнено соотношение для набора
x
i
{\displaystyle x_{i}}
. Но при этом все
x
i
′
≥
0
{\displaystyle x'_{i}\geq 0}
, и одно или несколько чисел из набора
x
i
′
{\displaystyle x'_{i}}
равны
0
{\displaystyle 0}
.
Если все
x
i
′
=
0
{\displaystyle x'_{i}=0}
, то соотношение, очевидно, выполнено.
Рассмотрим случай, когда не все
x
i
′
=
0
{\displaystyle x'_{i}=0}
. Пусть для определённости
x
1
′
,
…
,
x
m
′
>
0
{\displaystyle x'_{1},\ldots ,x'_{m}>0}
, а
x
m
+
1
′
=
…
=
x
n
′
=
0
{\displaystyle x'_{m+1}=\ldots =x'_{n}=0}
.
Тогда, как легко видеть, все нулевые
x
i
′
{\displaystyle x'_{i}}
можно исключить из равенства, которое таким образом превращается в
max
(
x
1
′
,
…
,
x
m
′
)
=
∑
i
x
i
′
−
∑
i
<
j
min
(
x
i
′
,
x
j
′
)
+
∑
i
<
j
<
k
min
(
x
i
′
,
x
j
′
,
x
k
′
)
+
…
+
(
−
1
)
m
−
1
min
(
x
1
′
,
…
,
x
m
′
)
{\displaystyle \max(x'_{1},\ldots ,x'_{m})=\sum _{i}x'_{i}-\sum _{i<j}\min(x'_{i},x'_{j})+\sum _{i<j<k}\min(x'_{i},x'_{j},x'_{k})+\ldots +(-1)^{m-1}\,\min(x'_{1},\ldots ,x'_{m})}
Таким образом, мы свели соотношение для
n
{\displaystyle n}
чисел к аналогичному соотношению для меньшего количества
m
<
n
{\displaystyle m<n}
чисел. Отсюда в силу принципа математической индукции следует, что исходное соотношение верно для любого натурального
n
{\displaystyle n}
.