De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  prikbord |  gastenboek |  wie is wie? |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ's
links
twitter
boeken
help

inloggen

colofon

  \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 



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3