WisFaq!

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
16-2-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
16-2-2021