Kombinatorisk bevis

[Determined]

Vi har at [tex]2^n = \sum_{k=0}^n {n \choose k}[/tex]. Jeg har et kombinatorisk bevis for dette, men er ikke sikker på om det holder mål.

Antar at vi har en samling av n objekter. Da kan jeg trekke ut en delmengde av nøyaktig k av dem på [tex]{n \choose k}[/tex] forskjellige måter (dette blir dermed summen av alle måtene, høyresiden av ligningen). Men det totale antallet delmengder er også [tex]2^n[/tex].

Jeg beviser det siste her med at om vi skal trekke ut delmengder fra n elementer, så kan det i'te elementet enten være med eller ikke være med. Det er altså 2 mulige utfall for det i'te elementet. Da blir det [tex]2^n[/tex] mulige måter for alle n elementene tilsammen.

Holder dette beviset?

[Brahmagupta]

Det holder det, kunne eventuelt tatt med hvorfor summen av alle delmengder er 2^n.

Et annet bevis er:

[tex]2^n=(1+1)^n=\sum_{k=0}^n{n\choose k}[/tex]
Hvor binominalteoremet brukes i andre overgang.

[Determined]

Takk for svar!

Ja skulle bevise dette på to måter...