Binomial Theorem

ABSTRACT

The Binomial Theorem provides a powerful algebraic method for expanding expressions of the form $(x+y{)}^n$. In combinatorics, it serves as a fundamental identity that links algebra to counting, specifically through the use of Combinations (binomial coefficients).

---

1. The Theorem

For any non-negative integer $n$, the expansion of $(x+y{)}^n$ is given by:

$(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k$

Expanding this summation, we get:

$(x+y{)}^n=(\genfrac{}{}{0ex}{}{n}{0})x^n{y}^0+(\genfrac{}{}{0ex}{}{n}{1})x^{n-1}{y}^1+(\genfrac{}{}{0ex}{}{n}{2})x^{n-2}{y}^2+\cdots +(\genfrac{}{}{0ex}{}{n}{n})x^0{y}^n$

---

2. Combinatorial Interpretation

The coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$, often read as ”$n$ choose $k$,” represents the number of ways to choose $k$ items from a set of $n$.

In the context of the expansion $(x+y)(x+y)\dots (x+y)$, to obtain the term $x^{n-k}{y}^k$, we must choose the variable $y$ from exactly $k$ of the $n$ available binomial factors. The remaining $n-k$ factors must contribute an $x$.

• There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways to make this selection.
• This is why binomial coefficients are also the entries in Pascal’s Triangle.

---

3. Useful Identities derived from the Theorem

By substituting specific values for $x$ and $y$, we can derive several important counting identities:

The Sum of Coefficients

Let $x=1$ and $y=1$:

$(1+1{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})⟹2^n=(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{1})+\cdots +(\genfrac{}{}{0ex}{}{n}{n})$

• Counting Meaning: The total number of subsets of a set of size $n$ (the Power Set) is $2^n$.

Alternating Sum

Let $x=1$ and $y=-1$:

$(1-1{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})(-1{)}^k⟹0=\left(\genfrac{}{}{0ex}{}{n}{0}\right)-\left(\genfrac{}{}{0ex}{}{n}{1}\right)+\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\dots$

• Counting Meaning: For any non-empty set, the number of subsets of even size is exactly equal to the number of subsets of odd size.

---

4. Connection to De Morgan’s Law and PIE

While the Binomial Theorem describes how to expand a union-like algebraic structure, it is often used to simplify the terms found in the Principle of Inclusion-Exclusion (PIE).

When applying PIE to $n$ properties where each intersection of $k$ properties has the same size (symmetry), the formula simplifies into a binomial expansion pattern:

$|S|-\sum |A_i|+\sum |A_i\cap A_j|\cdots ⟹{\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})N(k)$

This structure mirrors the alternating sum derived from the Binomial Theorem, often allowing complex counting problems to be reduced to a single compact expression.