binomialtheorem

Binomial Theorem

(a+b)**n = SUM(k=0 to n) (nCk)a**(n-k)b**k

nCk=n!/(k!(n-k)!)

Proof:

Basis for induction:

(a+b)**1 = a+b

Inductive hypothesis:

(a+b)**(m+1)=a(a+b)**m + b(a+b)**m

=a**(m+1) + {SUM(k=1 to m) [mCk + mC(k-1)]a**(m+1-k)b**k} + b**(m+1)

= SUM(k=0 to m+1) ((m+1)Ck)a**(m+1-k)b**k [by Pascal’s Rule]

LEMMA 1 (Pascal’s Rule)

mCk + mC(k-1) = (m+1)Ck