La $n$ og $m$ være positive heltall slik at $n>m$. Vis at
$$\sum_{k=m}^{n}(-1)^{k+m}\binom{n}{k}\binom{k}{m}=0.$$
Binomialkoeffisienter
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Brahmagupta
- Guru
- Innlegg: 628
- Registrert: 06/08-2011 01:56
Fin oppgave! Vi viser først at $\binom{n}{k}\binom{k}{m}=\binom{n-m}{k-m}\binom{n}{m}$. Dette
kan lett vises algebraisk, men la oss heller benytte et kombinatorisk argument. Det er $\binom{n}{m}$
måter å gjøre et uordnet utvalg på $m$ av $n$ personer. Anta nå i stedet at vi først velger ut $k$,
$n\geq k\geq m$, personer og deretter velger ut $m$ av de allerede valgte $k$ personene. Dette gir
$\binom{n}{k}\binom{k}{m}$ utvalg, men det er helt klart at flere av disse utvalgene vil bestå av de
samme personene. Vi ønsker derfor å avgjøre hvor mange ganger hver distinkte gruppe på $m$ personer
blir talt når man går frem på denne måten.
Fikser en gruppe $A$ på $m$ personer. Hvis $A$ er inneholdt i det første utvalget på $k$ personer
gjenstår det å velge ut $k-m$ personer fra de $n-m$ resterende personene. Videre er det kun en
måte å velge $A$ fra disse $k$ personene. Det vil si at $A$ blir talt $\binom{n-m}{k-m}$ ganger.
Siden $A$ var en vilkårlig gruppe på $m$ personer må enhver slik gruppe bli talt samme antall ganger
følger identiteten.
Nå forenkles summen til $\binom{n}{m}\sum_{k=m}^{n}(-1)^{k+m}\binom{n-m}{k-m}$, og hvis vi innfører
$r=n-m$ og $s=k-m$, hvor $s$ går fra $0$ til $r$ ser vi at
\[\sum_{k=m}^{n}(-1)^{k+m}\binom{n-m}{k-m}=\sum_{s=0}^{r}(-1)^{s}\binom{r}{s}=(1-1)^r=0,\]
og vi er ferdige.
kan lett vises algebraisk, men la oss heller benytte et kombinatorisk argument. Det er $\binom{n}{m}$
måter å gjøre et uordnet utvalg på $m$ av $n$ personer. Anta nå i stedet at vi først velger ut $k$,
$n\geq k\geq m$, personer og deretter velger ut $m$ av de allerede valgte $k$ personene. Dette gir
$\binom{n}{k}\binom{k}{m}$ utvalg, men det er helt klart at flere av disse utvalgene vil bestå av de
samme personene. Vi ønsker derfor å avgjøre hvor mange ganger hver distinkte gruppe på $m$ personer
blir talt når man går frem på denne måten.
Fikser en gruppe $A$ på $m$ personer. Hvis $A$ er inneholdt i det første utvalget på $k$ personer
gjenstår det å velge ut $k-m$ personer fra de $n-m$ resterende personene. Videre er det kun en
måte å velge $A$ fra disse $k$ personene. Det vil si at $A$ blir talt $\binom{n-m}{k-m}$ ganger.
Siden $A$ var en vilkårlig gruppe på $m$ personer må enhver slik gruppe bli talt samme antall ganger
følger identiteten.
Nå forenkles summen til $\binom{n}{m}\sum_{k=m}^{n}(-1)^{k+m}\binom{n-m}{k-m}$, og hvis vi innfører
$r=n-m$ og $s=k-m$, hvor $s$ går fra $0$ til $r$ ser vi at
\[\sum_{k=m}^{n}(-1)^{k+m}\binom{n-m}{k-m}=\sum_{s=0}^{r}(-1)^{s}\binom{r}{s}=(1-1)^r=0,\]
og vi er ferdige.