tlp5169 – Proofs in the Pudding

Saying Hi to Binomials

May 30, 2023tlp5169 1 Comment

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:

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.… Read the rest