Jim Lavrenz Coding Insider

Proof of the Binomial Theorem

Let's recall what the binomial theorem states. The theorem gives us a formula for calculating the expansion of a binomial made up of first degree monomials (i.e. expansion of \((x+y)^n\)). What's a binomial or a monomial for that matter? Let's start with a monomial. A monomial is an expression like \(y^2\); more complex monomials can be written, but they won't apply to this theorem. A first degree monomial is anything like \(x,y,z\). Easy, right? Pascal appears rather celebrated in this domain. He has something called Pascal's triangle named after him. To avoid getting sidetracked I will refer the interested reader to Wikipedia for a great discussion on Pascal's triangle. https://en.wikipedia.org/wiki/Pascal's_triangle


Proof of the Binomial Theorem

The proof is based on induction. Just recall when doing proofs, that involve proving something is true up to some variable \(n\), induction is your friend. Hence, this proof uses induction as well. So let's start. We want to prove that,

\[ (x+y)^n=\sum_{j=0}^n {n \choose j} x^jy^{n-j} \] Where, \[ {n \choose j}=\frac{n!}{j!(n-j)!} \] Proof by induction, for \(n=1\), \[ (x+y)^1=\sum_{j=0}^1 {1 \choose j} x^1 y^{1-j}=y+x \] Which is true. So, now assume true for \(n\) and show it's true for \(n+1\), \begin{align*} (x+y)^n&=\sum_{j=0}^n {n \choose j} x^j y^{n-j}\\ (x+y)(x+y)^n&=(x+y)\sum_{j=0}^n {n \choose j} x^j y^{n-j}\\ (x+y)^{n+1}&=\sum_{j=0}^n {n \choose j}x^{j+1} y^{n-j}+\sum_{j=0}^n {n \choose j} x^j y^{n-j+1} \end{align*} Let \(k=j+1\) which \(\Rightarrow j=k-1\) so therefore \(n-j=n-(k-1)\) or \(n-j=n-k+1\) \begin{align*} &=\sum_{k=1}^{n+1} {n \choose {k-1}}x^k y^{n-k+1}+\sum_{k=0}^n x^k y^{n-k+1}\\ &=\sum_{k=1}^n\left[{n \choose {k-1}}+{n\choose k}\right]x^k y^{n-k+1}+y^{n+1}+x^{n+1} \end{align*} by Pascal's rule (see proof at bottom of post) we have, \[ =\sum_{k=0}^{n+1}{{n+1}\choose k} x^k y^{n+1-k} \] So this proves it is true for \(n+1\), hence we have, \[ (x+y)^n=\sum_{j=0}^n {n\choose j}x^jy^{n-j} \]

Whew, that was non-trivial as they say.

If you want to know more about the Binomial Theorem, consider checking out the Wikipedia article,

http://en.wikipedia.org/wiki/Binomial_theorem

P.S. Note: the binomial theorem is often our friend when we are doing more advanced math proofs that require expanding on the form \((x+\Delta x)^n\), as seen in some calculus proofs.