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