Identitet av toppar och dalar

Identiteten för maxima och minima är ett matematiskt förhållande mellan det maximala elementet i en ändlig uppsättning tal och minimielementen för alla dess icke-tomma delmängder .

Formulering

Låta vara godtyckliga reella tal . Då säger identiteten : ${\displaystyle x_{1},\ldots ,x_{n))$

\max(x_{1},\ldots ,x_{n})=\summa _{i}x_{i}-\summa _{i<j}\min(x_{i},x_{j })+\summa _{i<j<k}\min(x_{i},x_{j},x_{k})+\ldots +(-1)^{n-1}\,\min( x_{1},\ldots ,x_{n})

Ett liknande förhållande gäller om minima och maxima är utbytta:

\min(x_{1},\ldots ,x_{n})=\summa _{i}x_{i}-\summa _{i<j}\max(x_{i},x_{j })+\summa _{i<j<k}\max(x_{i},x_{j},x_{k})+\ldots +(-1)^{n-1}\,\max( x_{1},\ldots ,x_{n})

Bevis

Låt oss till exempel bevisa det första av ovanstående samband.

Observera att om vi ersätter , där är ett godtyckligt tal, så ändras också båda delarna av relationen som bevisas till . $x\mapsto x+a$ $a$ $a$

Ja, den vänstra sidan:

\max(x_{1}+a,\ldots ,x_{n}+a)=\max(x_{1},\ldots ,x_{n})+a

Höger del:

${\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)=\\&=\summa _{k=1}^{n}\summa _{i_{ 1}<\ldots <i_{k}}(-1)^{k-1}\,\min(x_{i_{1}},\ldots ,x_{i_{k}})+a\summa _ {k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\!\!\!1\ end{aligned}}$

Den andra termen är exakt lika med , på grund av den välkända egenskapen hos binomialkoefficienter : $a$

\sum _{k=1}^{n}(-1)^{k-1}\!\!\!\sum _{i_{1}<\ldots <i_{k}}\! \!\!1=\summa _{k=1}^{n}(-1)^{k-1}{n \choose k}=1

Låt oss nu ersätta allt med , där . På grund av ovanstående överväganden kommer relationen för uppsättningen att vara uppfylld om och endast om relationen för uppsättningen är uppfylld . Men samtidigt är alla och ett eller flera nummer från mängden lika . $x_{i}$ $x'_{i}=x_{i}+a$ $a=-\min(x_{1},\ldots ,x_{n})$ ${\displaystyle x'_{i))$ $x_{i}$ $x'_{i}\geq 0$ ${\displaystyle x'_{i))$ $0$

Om allt så gäller uppenbarligen förhållandet. $x'_{i}=0$

Tänk på fallet när inte alla . Låt, för bestämdhet , och . Då kan, som är lätt att se, alla nollor uteslutas från den jämlikhet, som alltså blir $x'_{i}=0$ $x'_{1},\ldots ,x'_{m}>0$ $x'_{m+1}=\ldots =x'_{n}=0$ ${\displaystyle x'_{i))$

\max(x'_{1},\ldots ,x'_{m})=\summa _{i}x'_{i}-\summa _{i<j}\min(x' _{i},x'_{j})+\summa _{i<j<k}\min(x'_{i},x'_{j},x'_{k})+\ldots +(-1)^{m-1}\,\min(x'_{1},\ldots ,x'_{m})

Vi har alltså reducerat förhållandet för siffror till ett liknande förhållande för ett mindre antal siffror. Härifrån, i kraft av principen om matematisk induktion , följer det att det ursprungliga förhållandet är sant för alla naturliga . $n$ $m<n$ $n$

Se även

Formel för inkludering-uteslutning