Proof of the binomial theorem

While working on How To Prove It, I found this in the exercises.
To me, the binomial formula is really trivial, but it’s an interesting thing to prove because it requires manipulating summations and some algebra tricks. So let’s get started.

Prove that for all real number x and y, and every natural n:
(x+y)^n = \sum_{k=0}^{n} {n \choose k} x^{n-k} y^k
We will use mathematical induction on n.

Base case:
n = 0: (x+y)^0 = 1 = {0 \choose 0} x^0 y^0

Inductive hypothesis:
Assume that the formula holds for n = j:
(x+y)^j = \sum_{k=0}^{j} {j \choose k} x^{j-k} y^k

Using this identity we need to show that it also holds for n = j + 1.

Multiply both sides of the inductive hypothesis by x + y:
(x+y)^{j+1} = (x+y)\sum_{k=0}^{j} {j \choose k} x^{j-k} y^k

Now we can split the summation like so:
(x+y)^{j+1} = \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k+1} y^{k+1}

Consume the first element of the first summation:
(x+y)^{j+1} = x^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j} {j \choose k} x^{j-k} y^{k+1}

Consume the last element of second summation:
(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=0}^{j-1} {j \choose k} x^{j-k} y^{k+1}

Shift the bounds of the second summation to match the first:
(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {j \choose k} x^{j-k+1} y^k + \sum_{k=1}^{j} {j \choose {k-1}} x^{j-k+1} y^k

From here, we can factor the same elements:
(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} [x^{j-k+1} y^k] ({j \choose k} + {j \choose k-1})

We will use the identity {j \choose k} + {j \choose {k - 1}} = {{j + 1} \choose k} to simplify:
(x+y)^{j+1} = x^{j+1} + y^{j+1} + \sum_{k=1}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]

Note that {{j + 1} \choose 0} x^{j + 1} y^0 = x^{j+1}, so we can insert first element of first summation back into the summation by setting lower bound to 0:
(x+y)^{j+1} = y^{j+1} + \sum_{k=0}^{j} {{j + 1} \choose k} [x^{j-k+1} y^k]

Apply similar reasoning for the upper bound to move y^{j+1} inside the summation:
(x+y)^{j+1} = \sum_{k=0}^{j + 1} {{j + 1} \choose k} [x^{j-k+1} y^k]

Now, by setting m = j + 1 we get the induction hypothesis, thus the identity is proven.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s