In Probability,
(p+q)n=k=0∑n(kn)pkqn−k Proof
Base case
Let n=1. Then
k=0∑1(k1)pkqn−k=(01)p0q1+(11)p1q0 Induction Hypothesis
Assume that (p+q)m=k=0∑m(m1)pkqm−k. Let n=m+1. Then
(p+q)m+1=(p+q)(p+q)m=(p+q)k=0∑m(m1)pkqm−k pk=0∑m(km)pkqm−k+qk=0∑m(km)pkqm−k k=0∑m(km)pk+1qm−k+k=0∑m(km)pkqm−k+1 Let j=k+1 and k=j−1 for the first and j=k for the second sum. Then,
j=1∑j=m+1(j−1m)pjqm+1−j+j=0∑j=m(jm)pjqm−j+1 (mm)pm+1q0+j=1∑j=m(j−1m)pjqm+1−j+j=1∑j−m(jm)pjqm+1−j+(0m)p0qm+1 This equals
(m+1m+1)pm+1q0+j=1∑j=m((j−1m)+(jm))+j=1∑j−m(jm)pjqm+1−j+(0m+1)p0qm+1 (m+1m+1)pm+1q0+j=1∑m(jm+1)pjqm+1−j+(0m+1)p0qm+1 =j=0∑m+1(jm+1)pjqm+1−j ■