Proof of Binomial Formula

The binomial formula states that for $x,y \in \mathbb{R}$ and $n \in \mathbb{N}^+$ we have $(x + y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}.$

There are several ways to prove this formula. Here I would like to offer an informal proof based on combinatorics.

1. Expanding Parentheses

Before I start the proof, I'd like to revisit a useful fact from from basic algebra. Consider this well-known equation, $(a + b) (c + d) = ac + ad + bc + bd,$ and note that the right-hand side is a sum of all possible products where each factor is "picked" from each of the parentheses on the left hand side. For example, the product $ad$ stems from $a$ that is "picked" from $(a+b)$ and $d$ is "picked" from $(c+d)$. This pattern works for any number of parentheses. For example, note how this property holds in this slighty more advanced example where I have emphasized the $bde$ term for illustration: $(a + \underline{b}) (c + \underline{d}) (\underline{e} + f) = ace + acf + ade + adf + bce + bcf + \underline{bde} + bdf.$

This is starting to smell like a combinatorics problem!

2. Counting Equal Products

Let us also consider the expansion of this special case: $(x+y) (x+y) (x+y).$

Can we determine how many of the resulting terms will be equal to for example $xxy$ without actually doing the algebraic expansion? Based on the observation made above, it hopefully should now be fairly easy to see that the only terms (of the expanded sum) that are equal to $xxy$ will be these:

• $xxy$ (picking $x$ from the first two parentheses, and $y$ from the last),
• $xyx$ (picking $x$ from the first and last parentheses , and $y$ from the second),
• $yxx$ (picking $x$ from the last two parentheses, and $y$ from the first).

There are no other possibilities so the answer is that 3 of the resulting terms will equal $xxy$.

Let's try to rephrase the question in combinatorics lingo: In how many ways can you choose two $x$s from a total of 3 parentheses? It is exactly questions like that that can be answered using the binomial coefficients. If we use the binomial coefficient to answer the question, we luckily get the same answer: ${3 \choose 2} = \frac{3!}{2! (3-2)!} = 3.$

The fact that we can answer this question without actually expanding the parentheses algebraically will be become useful in the following.

3. Putting It Together

Now let us consider the expression $(x + y)^n = \underbrace{(x+y) \ldots (x+y)}_{n\text{ times}}.\tag{1}$

Using the rule established above, we can say that the full expansion of this expression will be a sum of products where each product has $n$ factors (since each product "picks up" one factor from each parentheses).

Since we are only dealing with two variables ($x$ and $y$) we also know that the number of $x$s in each product will be $k \in \{ 0, \ldots , n \}$ and the number of $y$s will be $n-k$ (because the number of factors is $n$). This means that all terms will look like $x^k y^{n-k}$. Based on this we now know we can write equation 1 as $(x + y)^n = \sum_{k=0}^n a_k x^{n-k} y^k\tag{2}$ where $a_k$ are positive integers. We now only need to find an expression for $a_k$, that is to find out how many terms of the expansion imathuals $x^k y^{n-k}$ (for a given $k$). What we are really asking is this: In how many ways is it possible to pick $k$$x$s from $n$ parentheses? As explained in the simpler case above, the answer to such questions are the binomial coefficients, i.e. $a_k = {n \choose k}$.

Plugging this expression for $a_k$ into equation 2 we get the full binomial formula: $(x + y)^n = \sum_{k=0}^n {n \choose k} x^k y^{n-k}.$