Bewijzen met verhaaltjes

Hoe bewijs je volgende formule? 

    \[k(k-1)\binom{n}{k}=n(n-1)\binom{n-2}{k-2}\]

Het gaat zeer snel door gebruik te maken van de definitie van  binomiaalcoëfficiënten. Maar er is ook een andere manier, die je ook kan gebruiken als het gebruik van de definitie wat ingewikkelder ligt. We verzinnen gewoon een verhaaltje …

Je wilt op school met n leerlingen een leerlingenraad van k personen oprichten, waarbij een voorzitter en een ondervoorzitter moeten aangeduid worden.

  • Het linkerlid van bovenstaande vergelijking komt overeen met volgende procedure: kies eerst k leden uit de n leerlingen. Dit  kan op \binom{n}{k} manieren. Kies in die groep van k gekozenen een voorzitter ( k mogelijkheden) en een ondervoorzitter ( k-1 mogelijkheden).
  • Het rechterlid correspondeert met de procedure: kies uit de n leerlingen eerst een voorzitter ( n mogelijkheden), dan een ondervoorzitter( n-1 mogelijkheden) en vul tenslotte aan tot je een groep van k leden hebt. Je moet dus nog k-2 leerlingen kiezen uit de n-2 beschikbare (\binom{n-2}{k-2} mogelijkheden).
  • Aangezien beide procedures hetzelfde probleem oplossen , zijn linkerlid en rechterlid gelijk aan elkaar.