# Inductive formula for binomial coefficients

In the last post on the mean and variance of a binomial random variable, we used the following formula:
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.$$ Let's just take a moment to prove this formula. Of course, how we prove it depends on what definition you use of the binomial coefficients. We have to start somewhere, after all. So, we'll start with the definition that $\binom{n}{k}$ is the number of ways of choosing $k$ objects from $n$ objects, where the order of the objects do not matter. If $k > n$ of course this is impossible so $\binom{n}{k}$ is zero and similarly for $k < 0$. Basic combinatorial reasoning allows us to write down the formula $$\binom{n}{k} = \frac{n!}{(n-k)!k!}$$ for $0\leq k\leq n$. For example, $$\binom{329}{4} = 479318126.$$ In actually computing this formula of course, you don't compute the factorials individually. It's much more efficient to compute as $$\binom{n}{k} = n(n-1)\cdots (n-k+1)/k!$$ or reverse the formula by replacing $k$ with $n-k$.

Anyways, this formula allows us to write down a simple computational proof of
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ as follows:
\begin{align*}\binom{n-1}{k-1} + \binom{n-1}{k} &= \frac{(n-1)!}{(n-k)!(k-1)!} + \frac{(n-1)!}{(n-k-1)!k!}\\ ~\\ &= \frac{(n-1)!k + (n-1)!(n-k)}{(n-k)!k!}\\~\\ &= \frac{n!}{(n-k)!k!} = \binom{n}{k}.\end{align*}

We can prove the formula
$$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$$ in an entirely different way, by using the combinatorial definition we started with. To arrange $k$ objects from $n$ objects, first set the $n$th object aside. Now, either an arrangement with contain this $n$th object, or it will not. Therefore, there are
$$\binom{n-1}{k}$$ ways of obtaining $k$ objects from $n$ objects that do not contain the $n$th object. To get the remaining arrangements that do contain the $n$th object, just select $k-1$ objects from the first $n-1$ objects, and then add the $n$th. There are
$$\binom{n-1}{k-1}$$ ways to do this. That proves the formula! Cool, right?

Still, we could have started from a different definition altogether. We could define
$$\binom{n}{k}$$ as the coefficient in front of $a^kb^{n-k}$ in the expansion of $(a + b)^n$. Then, the inductive formula for the binomial coefficients follows by considering the factorization $(a + b)^n = (a + b)^{n-1}(a + b)$.

Each of these three ways is a slightly different way of looking at binomial coefficients, and in general this combinatorial interplay between formulas and combinatorial reasoning can be a powerful tool in working with more complex combinatorial formulas.