Proof for Binomial theorem

Solution 1:

There are some proofs for the general case, that $$(a+b)^n=\sum_{k=0}^n {n \choose k}a^kb^{n-k}.$$ This is the binomial theorem.

One can prove it by induction on n:

• base: for $n=0$, $(a+b)^0=1=\sum_{k=0}^0{n \choose k}a^kb^{n-k}={0\choose0}a^0b^0$.

• step: assuming the theorem holds for $n$, proving for $n+1$: $$(a+b)^{n+1}=(a+b)(a+b)^n=(a+b)\sum_{k=0}^n {n \choose k}a^kb^{n-k}\\=\sum_{k=0}^n {n \choose k}a^{k+1}b^{n-k}+\sum_{k=0}^n{n \choose k}a^kb^{n-k+1}$$ Putting in the left summation $m=k+1$ gives:

$$\sum_{m=1}^{n+1} {n \choose {m-1}}a^{m}b^{n-m+1}+\sum_{k=0}^n{n \choose k}a^kb^{n-k+1}$$ Adding the two summation gives: $$b^{n+1}+\sum_{k=1}^n({n \choose k}+{n\choose k-1})a^kb^{n-k+1}+a^{n+1}$$. Now, it can be prove (in induction or combinatorial proof) that ${n \choose k}+{n\choose k-1}={n+1\choose k}$, reinsert the a^{n+1} and b^{n+1} into summation and the proof is complete.

Another way - combinatoric(less formal but simpler):

in the expression $(a+b)^n$, the coffecient of $a^kb^{n-k}$ is the number of ways to choose k 'a's and n-k 'b's from n pairs of $(a+b)$. For that we can choose k pairs for 'a's, and 'b's from the others. The number of ways to do it is ${n \choose k}$