Saying Hi to Binomials

Teresa Pan

$\displaystyle \binom{H}{i}$

In class, we talked a bit about factorials. Specifically, we defined it like so:

$0! = 1, \ n! = (n-1)! \cdot n$

Now, let’s talk about binomial coefficients. We can define them using recursion:

$\binom{n}{0} = 1$
$\binom{0}{k} = 0$
$\binom{n+1}{k+1} = \binom{n}{k} + \binom{n}{k+1}$

This gives us Pascal’s triangle, which was actually discovered by an Indian mathematician named Pingala in the 3rd century. Pascal didn’t exist until the 17th century, so who knows what they called this triangle during those 1400 years. Anyways, here are the first few rows of Pascal’s triangle, constructed using the recursion above:

Pascal’s Triangle

Sums of binomial coefficients

A very interesting property of Pascal’s triangle is that the sum in every rows add to a power of 2. This can be proved using inductive reasoning:

Base case: When $n = 0$ , we have $\binom{0}{0} = 1 = 2^0$ . The base case is true.

Inductive step: Let’s have $n \geq 0$ . Suppose $\sum_{i = 0}^n \binom{n}{i} = 2^n$ . We want to prove $\sum_{i = 0}^{n+1} \binom{n+1}{i} = 2^{n+1}$ .

$\sum_{i = 0}^{n+1} \binom{n+1}{i} = \binom{n+1}{0} + \sum_{i = 1}^{n+1} \binom{n+1}{i}$

$= 1 + \sum_{j = 0}^{n} \binom{n+1}{j+1}$ by reindexing with $j = i - 1$

$= 1 + \sum_{j = 0}^{n} \binom{n}{j} + \binom{n}{j+1}$ by the recursive definition of binomial coefficients

$= 1 + \sum_{j = 0}^{n} \binom{n}{j} + \sum_{j = 0}^{n} \binom{n}{j+1}$

$= 1 + 2^n + \sum_{j = 0}^{n} \binom{n}{j+1}$ by the inductive hypothesis

For $\sum_{j = 0}^{n} \binom{n}{j+1}$ , we reindex again with $k = j + 1$ and obtain

$\sum_{j = 0}^{n} \binom{n}{j+1} = \sum_{k = 1}^{n+1} \binom{n}{k} = \binom{n}{n+1} -\binom{n}{0} + \sum_{k = 0}^{n} \binom{n}{k}$

We assumed $\sum_{k = 0}^{n} \binom{n}{k} = 2^n$ to be true, and that $\binom{n}{n+1} = 0$ , and $\binom{n}{0} = 1$ . Thus, $\sum_{j = 0}^{n} \binom{n}{j+1} = 2^n - 1$ . Finally,

$\sum_{i = 0}^{n+1} \binom{n+1}{i} = 1 + 2^n + 2^n - 1 = 2(2^n) = 2^{n+1}$ ,

which is what we expected. We are done!

How do factorials relate to binomial coefficients?

Of course, learning combinatorics is how a lot of us were introduced to factorials. Namely,

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$ for all $k \leq n$ .

But why is it true? Let’s proceed using induction again:

Base case: When $n = 0$ , we have $\frac{0!}{0! \cdot 0!} = 1 = \binom{0}{0}$ . The base case is true.

Inductive step: Let $n$ be a natural number. Suppose that $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ is true for all $k \leq n$ . We want to prove $\binom{n+1}{k} = \frac{(n+1)!}{k!(n+ 1 -k)!}$ for all $k \leq n+1$ .

Case 1: If $k = 0$ ,

$\binom{n+1}{0} = 1$ and $\frac{(n+1)!}{0!(n+ 1 -0)!} = \frac{(n+1)!}{(n+1)!} = 1$ .

Case 2: If $0 < k \leq n$ , let $l = k-1$ . Then $\binom{n+1}{k} = \binom{n+1}{l + 1} = \binom{n}{l} + \binom{n}{l + 1}$ . Further,

$\binom{n}{l}=\frac{n!}{l!(n-l)!} = \frac{n!}{l!(n-l)!} \cdot \frac{l+1}{l+1} = \frac{n!(l+1)}{(l+1)!(n-l)!}$ .

Additionally,

$\binom{n}{l + 1} = \frac{n!}{(l+1)!(n-l-1)!} = \frac{n!}{(l+1)!(n-l-1)!} \cdot \frac{n-l}{n-l} = \frac{n!(n-l)}{(l+1)!(n-l)!}$ .

Thus,

$\binom{n+1}{k} = \binom {n+1}{l+1} = \frac{n![(l+1)+(n-l])}{(l+1)!(n-l)!} = \frac{n!(n+1)}{(l+1)!(n-l)!} = \frac{(n+1)!}{(l+1)!(n-l)!} = \frac{(n+1)!}{k!(n-k+1)!}$ .

We have used induction to finally convince ourselves of a formula we have probably all used for some time now. The natural next step is to prove the binomial theorem. That is left as an exercise to the reader. 🙂

Sources

Goss, David. The Ongoing Binomial Revolution. 2011.
Newstead, Clive. An Infinite Descent into Pure Mathematics. 2022.

One Comment


June 5, 2023
Patrick Chen

Hi Teresa,
I really liked your blog post as it gives me a new perspective on binomials that I never saw before. I have never seen the algebraic proof of n choose k using induction before. I greatly appreciate you taking the time and showing the proof of n choose k = n!/(n-k)!k! as it is incredibly rigorous. In my other math classes such as Math 310 and CS 212, I always learned the combinatorial story proof for n choose k that is the number of ways to choose k people from a group of n people, in which there are n!/(n-k)! to choose k people from a group of n people in a sequence. However, we the order does not matter for groups. Thus, we are overcounting by k! since there are k! ways to arrange the k people in the sequence, causing k! sequence arrangements to “map to” 1 group of arrangement. Therefore, we must divide n!/(n-k)! by k! to correct this overcounting. The induction proof you did in your post is a great way to always check that your combinatorial story proof holds true, thus making it extremely valuable.

In regards Pascal’s triangle, it’s incredible how many mathematical concepts in combinatorics is derived from this extremely basic mathematical phenomenon. There are so many properties of Pascal’s Triangle that I was not even aware of such as the one you mentioned in your blog post.

Sums of binomial coefficients

How do factorials relate to binomial coefficients?

Sources

tlp5169

One Comment

Leave a Reply Cancel reply