n elemanlı bir kümenin 0 elemanlı altkümelerinin sayısı C(n,0)
n elemanlı bir kümenin 1 elemanlı altkümelerinin sayısı C(n,1)
n elemanlı bir kümenin 2 elemanlı altkümelerinin sayısı C(n,2)
⋮
n elemanlı bir kümenin n elemanlı altkümelerinin sayısı C(n,n)
O halde cevap C(n,0)+C(n,1)+C(n,2)+…+C(n,n)
olacaktır. Şimdi bu toplamın
2n
olduğunu gösterelim.
(1+x)n=C(n,0)⋅xn+C(n,1)⋅xn−1+C(n,2)⋅xn−2+…+C(n,n)
olduğunu biliyoruz.
x=1 için aradığımız eşitlik bulunur.