M.I. ///////////////

When n = 1 , 1C0 + 1C1 = 2¹.Assuming that ∑(r=0 → k) kCr = 2ᵏ.When n = k+1 ,
2ᵏ⁺¹
= 2(2ᵏ)
= 2 ∑ (r= 0 → k) kCr
= ∑ (r= 0 → k) kCr + ∑ (r= 0 → k) kCr
= kC0 + (∑ (r= 1 → k) kCr + ∑ (r= 0 → k-1 ) kCr) + kCk
= kC0 + ∑ (r= 1 → k) (kCr + kCr-1) + kCk
= kC0 + ∑ (r= 1 → k) ( k! / (r!(k -r)!) + k! / ((r -1)!(k -r+1)!)) +kCk
= kC0 + ∑ (r= 1 → k) ( k! (k -r+1 + r) / (r! (k -r+1)!) ) + kCk
= kC0 + ∑ (r= 1 → k) ( (k+1)! / [r! (k -r+1)!] + kCk
= kC0 + ∑ (r= 1 → k) k+1 C r + kCk
= k+1C0 + ∑ (r= 1 → k) k+1 C r + k+1Ck+1
= ∑ (r= 0 → k+1) k+1 C r ∴ By mathematical induction , ∑(r=0 → n) nCr = 2ⁿ for integer n > 0.

Suppose P(n) denotes the proposition : "∑[r=0, n] n_C_r = 2^n for all natural number n "

For n=1,
∑[r=0, 1] 1_C_r = 1C0 + 1C1 = 2^1

So, P(1) is true.

Assume, P(k) is true.
i.e. ∑[r=0, k] k_C_r = 2^k

Consider n=k+1,

By using n+1Cr = nCr+nCr-1,
we have

∑[r=0, k+1] k+1_C_r

=∑[r=0, k+1] (k_C_r + k_C_r-1 )

=∑[r=0, k+1] k_C_r + ∑[r=0, k+1] k_C_r-1

=∑[r=0, k] k_C_r + ∑[r=1, k+1] k_C_r-1

=∑[r=0, k] k_C_r + ∑[r=0, k] k_C_r

= 2 ∑[r=0, k] k_C_r

= 2 (2^k)

= 2^(k+1)

By, M.I. P(n) is true