Kombinatorisk bevis
Lagt inn: 19/02-2013 15:32
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?
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?