Valaki tudná szemléltetni a következő bizonyítást?

Vegyünk a k elemű halmazhoz még egy k+1-edik elemet. A k elemű halmaznak eredetileg N darab eleme volt. Vegyük az új halmaznak azokat a részhalmazait, amikben nincsen benne a k+1-edik elem. Ezekből ugye N darab van. Most számoljuk össze azokat a részhalmazokat is, amikben benne van a k+1-edik elem. Ezek pontosan az előbbi részhalmazok lesznek úgy, hogy még hozzájuk van csapva a k+1-edik, tehát ezekből is N darab van. És mivel egy részhalmazban vagy benne van a k+1-edik elem, vagy nincs, ezért másmilyen részhalmaz már nem jöhet szóba. N + N = 2N részhalmaz van összesen. (Miután N-ról tudjuk, hogy az 2^k, ezért 2*N = 2*2^k = 2^(k+1).)

Az egyelemű halmaznak ugye 2 részhalmaza van.

A (a halmaz elemei)

0 (a részhalmazban nincs benne ez az elem)

1 (a részhalmazban benne van ez az elem)

A kételemű halmaz esetén:

AB

00 Az első két sorban azok a részhalmazok,

10 amikben nincsen benne a k+1 = 2-ik elem.

01 Itt azok, amikben benne van a 2-ik elem.

11

Háromelemű halmaz esetén:

ABC

000

100

010

110

001

101

011

111

Tehát a részhalmazok: {}, {A}, {B}, {A,B} + még ugyanezek úgy, hogy beléjük tesszük a C elemet: {C}, {A,C}, {B,C}, {A,B,C}. Összesen 8-an.

HF.: Írd fel a négyelemű {A,B,C,D} halmaz részhalmazait.

Tekintsünk egy n elemű halmazt és képezzünk az elemiből részhalmazokat! Vegyük sorra a halmaz minden elemét. Minden elemnél 2 lehetőség közül választhatunk: 1.) az adott elemet beletesszük a részhalmazba, 2.) az adott elemet nem tesszük bele a részhalmazba. Így a részhalmazok száma 2*2*2*...*2=2^n.

Másik megoldás. Válasszunk ki n különböző elem közül 0-t, ezt n alatt a 0 féleképpen tehetjük meg. Majd válasszunk ki n különböző elem közül 1-et, erre n alatt az 1 lehetőségünk van, és így tovább ... . Tehát n különböző elem közül kiválasztunk k különböző elemet úgy, hogy azok sorrendjére nem vagyunk tekintettel, erre n alatt a k lehetőségünk van. Így a részhalmazok száma: n alatt a 0 + ... + n alatt a k + ... n alatt az n, ez összeg 2^n-nel egyenlő, amely a binomiális tételből következik (a=1, b=1 esetén).