WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\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

Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 16 februari 2021

Re: Bewijs voor een som