Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

Bewijs voor een som

Goeiedag,

Ik ben momenteel bezig met een opgave waarbij ik het volgende probeer te bewijzen:

$
\sum\limits_{k = 1}^n {k\left( {\matrix{
n \cr
k \cr

} } \right)} = n \cdot 2^{n - 1}
$

Een algebraïsch bewijs heb ik kunnen geven maar voor een combinatorisch bewijs zie ik niet waar ik kan beginnen. Ik zie wel een 'overeenkomst' met de driehoek van Laplace.

Albert
Student universiteit - dinsdag 16 februari 2021

Antwoord

Je kunt de som ook lezen als
$$\sum_{k=1}^nk\binom{n}{n-k}
$$De rechterkant kun je als volgt interpreteren: tel voor elke $i$ het aantal deelverzamelingen van $\{1,2,\dots,n\}\setminus\{i\}$ (alle deelverzamelingen waar $i$ niet in zit). Dat geeft $n$ keer $2^{n-1}$.

Kijk nu hoevaak de lege verzameling wordt geteld: $n$ keer, dat kun je schrijven als $n\cdot\binom{n}{0}=n\cdot\binom{n}{n-n}$.

Elke verzameling met één element wordt $n-1$ keer geteld, dat levert $(n-1)\cdot\binom{n}{1}=(n-1)\binom{n}{n-1}$.
Elke verzameling met $n-k$ elementen wordt $k$ keer geteld en dat geeft $k\cdot\binom{n}{n-k}$.

kphart
dinsdag 16 februari 2021

 Re: Bewijs voor een som 

©2001-2024 WisFaq