Mathematical Induction

The set of all subsets S has :
nC0 + nC1 + nC2 + ... + nCn elements.
By binomial theorem :
(a + b)^n = (nC0) a^n + (nC1)[a^(n-1)]b + (nC2)[a^(n-2)]b^2 + ...
+ (nCn) b^n
Let : a = b = 1
(1 + 1)^n = nC0 + nC1 + nC2 + ... + nCn
2^n = nC0 + nC1 + nC2 + ... + nCn
Or prove by Mathematical Induction :
The result referred to is : nCr + nC(r-1) = (n+1)Cr......★
L.H.S. = n!/[r!(n-r)!] + n!/[(r-1)!(n-r+1)!]
= n! (n - r + 1 + r) / [r! (n - r + 1)!]
= (n + 1)! / [r! (n - r + 1)!]
= (n + 1) C r
= R.H.S.
Let the set of all subsets S has 2^n elements when n = k be true :
kC0 + kC1 + kC2 + ... + kCk = 2^k......
圖片參考：http://l.yimg.com/f/i/tw/ugc/rte/smiley_39.gif

Assume k = 0 :
0C0 = 1 = 2^0 is true.
When n = k+1 :
2^(k+1) = (2 )* 2^k
= (kC0 + kC1 + kC2 + ... + kCk)+(kC0 + kC1 + kC2 +...+ kCk)
= [ kC0 + kC1 + kC2 + kC3 ... + kCk
+*******kC0 + kC1 + kC2 ... + kC(k-1) + kCk]
By ★ :
= kC0 + (k+1)C1 + (k+1)C2 + (k+1)C3 +...+ (k+1)Ck + kCk
=(k+1)C0 +(k+1)C1 + (k+1)C2 + (k+1)C3 +...+ (k+1)Ck + (k+1)C(k+1)
Now this is of exactly the same form as
圖片參考：http://l.yimg.com/f/i/tw/ugc/rte/smiley_39.gif
.
By Mathematical Induction it is true for any integer of n.

When there are k elements, there are 2^k subsets.
When one more element, x, is added to S, the 2^k subsets are still subset of the new S.
Another 2k sets can be created by adding x into the 2^k subsets, and each of these sets are also subsets of S. 2^k + 2^k = 2^(k+1)