Skip to main content

Binomial Theorem

In Probability,

(p+q)n=∑k=0n(nk)pkqn−k(p+q)^n = \sum\limits_{k=0}^n {n \choose k} p^k q^{n-k}

Proof​

Base case​

Let n=1n=1. Then

∑k=01(1k)pkqn−k=(10)p0q1+(11)p1q0\sum\limits_{k=0}^1 {1 \choose k }p^k q^{n-k} = {1 \choose 0} p^0 q^1 + {1 \choose 1} p^1 q^0

Induction Hypothesis​

Assume that (p+q)m=∑k=0m(1m)pkqm−k(p+q)^m = \sum\limits_{k=0}^m {1 \choose m }p^k q^{m-k}. Let n=m+1n = m+1. Then

(p+q)m+1=(p+q)(p+q)m=(p+q)∑k=0m(1m)pkqm−k(p+q)^{m+1} = (p+q) (p+q)^m = (p+q) \sum\limits_{k=0}^m {1 \choose m }p^k q^{m-k}
p∑k=0m(mk)pkqm−k+q∑k=0m(mk)pkqm−kp \sum\limits_{k=0}^m {m \choose k}p^k q^{m-k} + q \sum\limits_{k=0}^m {m \choose k}p^k q^{m-k}
∑k=0m(mk)pk+1qm−k+∑k=0m(mk)pkqm−k+1\sum\limits_{k=0}^m {m \choose k}p^{k+1} q^{m-k} + \sum\limits_{k=0}^m {m \choose k}p^k q^{m-k+1}

Let j=k+1j=k+1 and k=j−1k=j-1 for the first and j=kj=k for the second sum. Then,

∑j=1j=m+1(mj−1)pjqm+1−j+∑j=0j=m(mj)pjqm−j+1\sum\limits_{j=1}^{j=m+1} {m \choose {j-1}}p^{j} q^{m + 1 - j} + \sum\limits_{j=0}^{j=m} {m \choose j}p^j q^{m-j+1}
(mm)pm+1q0+∑j=1j=m(mj−1)pjqm+1−j+∑j=1j−m(mj)pjqm+1−j+(m0)p0qm+1{m \choose m} p ^{m+1} q^0 + \sum\limits_{j=1}^{j=m} {m \choose {j-1}} p^j q^{m+1-j} + \sum\limits_{j=1}^{j-m} {m \choose j} p^j q^{m+1-j} + {m \choose 0} p^0 q^{m+1}

This equals

(m+1m+1)pm+1q0+∑j=1j=m((mj−1)+(mj))+∑j=1j−m(mj)pjqm+1−j+(m+10)p0qm+1{m+1 \choose m+1} p ^{m+1} q^0 + \sum\limits_{j=1}^{j=m} ({m \choose {j-1}} + {m \choose j}) + \sum\limits_{j=1}^{j-m} {m \choose j} p^j q^{m+1-j} + {m+1 \choose 0} p^0 q^{m+1}
(m+1m+1)pm+1q0+∑j=1m(m+1j)pjqm+1−j+(m+10)p0qm+1{m+1 \choose m+1} p ^{m+1} q^0 + \sum\limits_{j=1}^{m} {m+1 \choose j} p^j q^{m+1-j} + {m+1 \choose 0} p^0 q^{m+1}
=∑j=0m+1(m+1j)pjqm+1−j          ■= \sum\limits_{j=0}^{m+1} {m+1 \choose j} p^j q^{m+1-j} ~~~~~~~~~~ \blacksquare