Her n doğal sayısı için n elemanlı bir kümenin tüm altkümelerinin 2 üzeri n tane olduğunu
a-Tümevarımla
b-Binom teoremi yardımıyla kanıtlayınız.

a- tümevarımla

1) n = 1 için önermeye göre 2^1 = 2 tane alt küme vardır.
peki bu doğru mudur ?
1 elemanlı kümenin boş küme ve kendisi olmak üzere iki tane alt kümesi vardır.

2) k, doğal sayısı için k elemanlı bir kümenin alt kümeleri sayısı 2^k olsun.

3) k+1 elemanlı kümenin alt kümelerini bulmak için,

k elemanlı kümeyi, A = { a(1), a(2),...,a(k) } olarak gösterirsem ( parantez içleri indisleri olmaktadır.)

A kümesinin alt kümeleri de C(p),(buradaki p de indistir.)
C(p), A nın p. alt kümesidir.

A kümesine a(k+1) dahil edilmesiyle B kümesi elde olunsun,

Yeni elde edilmiş B kümesinin alt kümeleri;

C(1) ve C(1) U { a(k+1) }
C(2) ve C(2) U { a(k+1) }
...
C(2^k) ve C(2^k) U { a(k+1) }

burada toplam 2^k + 2^k = 2^(k+1) tane yeni alt küme vardır. Dolayısıyla önerme doğrudur.

özel bir durum ile örnek vereyim, A = { 1 ,4 ,7} kümesi olsun

A nın alt kümeleri,

boş küme = O
{1}
{4}
{7}
{1, 4}
{4, 7}
{1, 7}
{1, 4, 7} bunlar C(p) ler

yeni dahil edilen eleman 13 olsun. yeni alt kümelerin kurulması mantığı burada şudur, eskileri ve bu eskilerin 13 ü içeren hâlleri.

yeni alt kümeler,

O ve 13
{1} ve {1, 13}
{4} ve {4, 13}
{7} ve {7, 13}
{1, 4} ve {1, 4, 13}
{4, 7} ve {4, 7, 13}
{1, 7} ve {1, 7, 13}
{1, 4, 7} ve {1, 4, 7, 13}
toplamda 8 + 8 = 16 tane küme oldu.

b- binom yöntemi ile
(bunun cevabını pek irdelemeden veriyorum, yalnızca aklıma gelen bir ifade)
bunu sözle yazsam,

6 nın 0 lı kombinasyonunu, K(6,0) olarak yazarsam,

(x + y)^6 = K(6,0). x^6. y^0 + K(6,1) x^5 . y^2 + ... + K(6,6). x^0 . y^6

x = 1 ve y = 1 için gösterir ki 6 nın tüm kombinasyonlarının toplamı 2^6 dır.( hoş da bir ifadedir bu )

(x + y)^s ifadesinde x = 1 ve y = 1 alınırsa s elemanlı kümenin tüm kombinasyonlarının toplamı bulunurve bu da 2^s çıkar.