Binomial Theorem

For any positive integer n,

(x+y)n = n ∑ k = 0  n k xn-kyk

proof by induction:

For n = 1,

(x+y)1 = x+y = 1 0 x1-0y0+ 1 1 x1-1y1 = 1 ∑ k = 0  1 k x1-kyk.

Suppose

(x+y)n-1 = n-1 ∑ k = 0  n-1 k x(n-1)-kyk

Consider (x+y)ⁿ.

(x+y)n = (x+y)(x+y)n-1 = (x+y) n-1 ∑ k = 0  n-1 k x(n-1)-kyk = n-1 ∑ k = 0  n-1 k xn-kyk + n-1 ∑ j = 0  n-1 j x(n-1)-jyj+1 = n-1 ∑ k = 0  n-1 k xn-kyk+ n-1 ∑ j = 0  n-1 (j+1)-1 xn-(j+1)yj+1 = n-1 ∑ k = 0  n-1 k xn-kyk+ n ∑ k = 1  n-1 k-1 xn-kyk = n ∑ k = 0  n-1 k xn-kyk - n-1 n x0yn + n ∑ k = 0  n-1 k-1 xn-kyk - n-1 -1 xny0 = n ∑ k = 0  n-1 k + n-1 k-1 xn-kyk = n ∑ k = 0  n k xn-kyk