Binomial theorem

In mathematics (and computer science), we often encounter multiple proofs for the same result. The proofs we have seen so far are classified as "combinatorial" proofs (e.g. relying on counting, bijections, etc). Another famous proof technique is called algebraic proofs which rely on algebraic properties of objects. We will see the first set of examples here (and some more later in these notes).

Here is a super powerful theorem that relates directly to counting.

Theorem 27

$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$

Exercise 71

Prove Theorem 27 by induction on $n$.

This theorem allows us to give alternative algebraic proofs to results about counting.

Example 27

${n \choose 0} + {n \choose 1} + \ldots + {n \choose n} = 2^n$. One way to prove this is to plug $x=1$ into the binomial theorem. Another way is to see that the right-hand-side is the total number of subsets of $[n]$, and the left-hand-side is obtained by summing over the number of size-$k$ subsets (for all $k=0,\ldots, n$).

The previous proof illustrates two different views about the quantities. In the first, these numbers are viewed as just meaningless numbers but the powerful binomial theorem allows us to relate them together. In the second view, each number is associated with some meaning, and these meaningful terms are tied together naturally.

Example 28

Here is an algebraic proof of the fact that the number of odd and even subsets is the same (recall Example 21). We plug in the value $x = -1$ to the binomial theorem, so we get $0= {n \choose 0} - {n \choose 1} + {n \choose 2} - \ldots$. Rearranging it implies that:

${n \choose 0} + {n \choose 2} + \ldots = {n \choose 1} + {n \choose 3} + \ldots$

The left-hand-side and right-hand-side are exactly the number of even and odd subsets respectively.

Example 29

For $n>0$, ${2n \choose n} < 4^n$. We can write $4^n = 2^{2n}$. So we have

${2n \choose 0} + {2n \choose 1} + \ldots + {2n \choose 2n} = 2^{2n}= 4^n$

Notice that ${2n \choose n}$ appears on the left side. As for a combinatorial proof, $2^{2n}$ is the number of subsets of $[2n]$, while ${2n \choose n}$ is the number of subsets of size $n$ (so it should be clear which number is greater 😊).

Exercise 72

Give a closed form expression (no sums and no dots-dots-dots) for $\sum_{k=0}^{n} {n \choose k} 2^k$.

Exercise 73

Let $n$ be a natural number. Using the binomial theorem, count the number of subsets of $[n]$ whose size is divisible by four.

Hint: If $w_1, w_2, w_3 w_4$ are the fourth roots of unity, what is $(w_1)^k + (w_2)^k + (w_3)^k + (w_4)^k$?