Kombinatorisk bevis

[Wentworth]

Oppgave 8.b) fra seksjon 1.4 lyder som følger;
En formel er gitt som følger;
[tex]2^{n}= \sum_{k=0}^{n} {n\choose k} 2^{k}[/tex]

Gi et kombinatorisk bevis for denne formelen basert på følgende observasjoner. Anta at jeg har en samling med n ting. Da kan jeg plukke ut en delmengde av nøyaktig k ting på [tex]\: n\choose k \:[/tex] forskjellige måter. På den andre siden er det totale antallet delmengder lik [tex]\: 2^{n} \:[/tex].

[Karl_Erik]

Det ser ut som du har slurvet litt, for den formelen der gjelder dessverre ikke. Kan det tenkes at du mente å skrive [tex]2^n= \sum_{k=0} ^n {n \choose k} [/tex]? Uansett - tenk litt over hintene du fikk i oppgaven. Hvis du kan plukke ut en delmengde av [tex]k[/tex] ting fra en samling på [tex]n[/tex] ting på [tex] {n \choose k} [/tex] måter - hvordan finner du da ut hvor mange forskjellige delmengder det finnes totalt?

[Charlatan]

Gi et kombinatorisk bevis for dette:

[tex]3^n=\sum{n \choose k}2^k[/tex]