Proof of Binomial Formula

The binomial formula states that for x,yRx,y \in \mathbb{R} and nN+n \in \mathbb{N}^+ we have (x+y)n=k=0n(nk)xkynk.(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,(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 adad stems from aa that is "picked" from (a+b)(a+b) and dd is "picked" from (c+d)(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 bdebde term for illustration: (a+b)(c+d)(e+f)=ace+acf+ade+adf+bce+bcf+bde+bdf.(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).(x+y) (x+y) (x+y).

Can we determine how many of the resulting terms will be equal to for example xxyxxy 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 xxyxxy will be these:

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

Let's try to rephrase the question in combinatorics lingo: In how many ways can you choose two xxs 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: (32)=3!2!(32)!=3.{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 (1)(x+y)n=(x+y)(x+y)n times.(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 nn factors (since each product "picks up" one factor from each parentheses).

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

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