7.3 Binomial Coefficients and Identities

Binomial Coefficients and Pascal's Triangle

Understanding Binomial Coefficients

A binomial coefficient counts the number of ways to choose k items from a set of n items, where order doesn't matter and you don't replace items. It's denoted ${n \choose k}$ (read "n choose k") or C(n,k), and calculated with:

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

For example, ${5 \choose 2} = \frac{5!}{2! \cdot 3!} = \frac{120}{2 \cdot 6} = 10$. There are 10 ways to pick 2 items from a set of 5.

Key properties to know:

• Symmetry: ${n \choose k} = {n \choose n-k}$. Choosing which 2 items to take from 5 is the same as choosing which 3 to leave behind, so ${5 \choose 2} = {5 \choose 3} = 10$.
• Boundary values: ${n \choose 0} = {n \choose n} = 1$. There's exactly one way to choose nothing, and one way to choose everything.
• Recursive formula (Pascal's Rule): ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$. This says: for any particular element, either you include it in your selection (leaving you to choose k−1 from the remaining n−1) or you exclude it (leaving you to choose k from n−1).
• Binomial coefficients appear as the coefficients when you expand $(x+y)^n$.

Exploring Pascal's Triangle

Pascal's Triangle arranges binomial coefficients in a triangular grid. Row n contains the values ${n \choose 0}, {n \choose 1}, \ldots, {n \choose n}$, and each entry equals the sum of the two entries directly above it (that's Pascal's Rule in visual form).

</>Code
Row 0:         1
Row 1:        1 1
Row 2:       1 2 1
Row 3:      1 3 3 1
Row 4:     1 4 6 4 1

Row 4, for instance, gives the coefficients of $(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$.

A few useful patterns hidden in the triangle:

• Each row sums to a power of 2. Row n sums to $2^n$ (e.g., row 3: 1+3+3+1 = 8 = $2^3$).
• The triangle is symmetric left-to-right, reflecting the symmetry property.
• The diagonals produce natural numbers, triangular numbers, and tetrahedral numbers as you move deeper.

Beyond being a nice visual, Pascal's Triangle gives you a quick way to look up small binomial coefficients without computing factorials.

Applying Combinatorial Proofs

A combinatorial proof shows that two expressions are equal by demonstrating they count the same thing in different ways. Instead of algebraic manipulation, you argue about counting.

Steps for writing a combinatorial proof:

1. Identify a counting problem that one side of the identity answers.
2. Reinterpret the other side as a different way of counting the exact same set.
3. Conclude equality, since both sides count the same collection of objects.

For example, to prove Pascal's Rule ${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}$:

• The left side counts the number of ways to choose k items from n.
• For the right side, single out one specific element (call it element #n). Every k-element subset either contains element #n or it doesn't. If it does, you choose the remaining k−1 items from the other n−1 elements: ${n-1 \choose k-1}$ ways. If it doesn't, you choose all k items from the other n−1 elements: ${n-1 \choose k}$ ways.
• Both sides count the same subsets, so they're equal.

Combinatorial proofs often give you more intuition about why an identity is true than a purely algebraic derivation would.

Binomial Theorem and Expansion

Exploring the Binomial Theorem

The Binomial Theorem tells you exactly how to expand $(x+y)^n$ for any non-negative integer n:

$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

Each term in the expansion has the form $\binom{n}{k} x^{n-k} y^k$. The exponents of x decrease from n to 0 while the exponents of y increase from 0 to n, and the exponents in each term always sum to n.

Why does this formula work? When you multiply out $(x+y)(x+y)\cdots(x+y)$ (n copies), each term in the product comes from picking either x or y from each factor. The coefficient ${n \choose k}$ counts how many ways you can pick y from exactly k of the n factors (and x from the rest).

Applying Binomial Expansion

To expand a specific binomial power, follow these steps:

1. Identify x, y, and n in your expression $(x+y)^n$.
2. Write each term for k = 0, 1, 2, …, n using $\binom{n}{k} x^{n-k} y^k$.
3. Simplify each term's coefficient and powers.

Example: Expand $(2a + 3)^3$.

Here x = 2a, y = 3, n = 3.

• k=0: ${3 \choose 0}(2a)^3(3)^0 = 1 \cdot 8a^3 \cdot 1 = 8a^3$
• k=1: ${3 \choose 1}(2a)^2(3)^1 = 3 \cdot 4a^2 \cdot 3 = 36a^2$
• k=2: ${3 \choose 2}(2a)^1(3)^2 = 3 \cdot 2a \cdot 9 = 54a$
• k=3: ${3 \choose 3}(2a)^0(3)^3 = 1 \cdot 1 \cdot 27 = 27$

Result: $(2a+3)^3 = 8a^3 + 36a^2 + 54a + 27$.

You can also find a single term without expanding everything. The (k+1)th term is $\binom{n}{k} x^{n-k} y^k$, so if you only need, say, the $a^2$ term above, just compute the k=1 case.

Understanding Binomial Identities

Binomial identities are equations involving binomial coefficients that hold for all valid values of n. They're useful for simplifying sums and solving counting problems. Here are the most important ones:

Sum of all coefficients: $\sum_{k=0}^{n} \binom{n}{k} = 2^n$

This follows directly from the Binomial Theorem by setting x = 1 and y = 1: $(1+1)^n = 2^n$.

Alternating sum: $\sum_{k=0}^{n} \binom{n}{k} (-1)^k = 0$

Set x = 1 and y = −1 in the Binomial Theorem: $(1-1)^n = 0$. This means the sum of coefficients at even positions equals the sum at odd positions.

Pascal's Rule: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Already discussed above. This is the recursive identity that builds Pascal's Triangle.

Each of these can be proved algebraically, by induction, or with a combinatorial argument. The substitution approach (plugging specific values into the Binomial Theorem) is often the fastest.

Advanced Binomial Identities

Exploring Vandermonde's Identity

Vandermonde's Identity states:

$\sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k} = \binom{m+n}{r}$

The combinatorial interpretation makes this intuitive. Suppose you have a group of m men and n women, and you want to choose a committee of r people. The right side counts this directly: ${m+n \choose r}$. The left side splits by cases: for each k, choose k men from m and the remaining r−k women from n, then sum over all possible values of k.

Both sides count the same committees, so they're equal.

A useful special case: setting m = n = r gives $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$, since ${n \choose r-k} = {n \choose n-k} = {n \choose k}$ by symmetry. This identity comes up frequently in probability.

Applying Combinatorial Proofs to Advanced Identities

The same proof strategy from earlier scales to harder identities. The challenge is finding the right counting interpretation.

For the identity $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$:

1. The right side counts ways to choose n items from a set of 2n.
2. Split the 2n items into two groups of n (call them Group A and Group B). To select n items total, you can choose k from Group A and n−k from Group B, for any k from 0 to n.
3. The number of ways to do this for a given k is ${n \choose k}{n \choose n-k} = {n \choose k}^2$.
4. Summing over all k gives the left side.

When tackling these proofs, the key move is to find a concrete scenario (committees, paths, subsets) where both sides naturally arise as different ways of organizing the count.

Exploring Additional Binomial Identities

A few more identities worth knowing:

Absorption/Extraction identity: $\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$

You can verify this directly from the factorial formula. It's handy for pulling a factor of n or k out of a binomial coefficient during algebraic manipulation.

Weighted sum identity: $\sum_{k=0}^{n} k \binom{n}{k} = n \cdot 2^{n-1}$

To see why, use the absorption identity: $k{n \choose k} = n{n-1 \choose k-1}$. Substituting and re-indexing the sum gives $n \sum_{j=0}^{n-1}{n-1 \choose j} = n \cdot 2^{n-1}$.

Binomial series (generalized form): $\sum_{k=0}^{n} \binom{n}{k} x^k = (1+x)^n$

This is just the Binomial Theorem with y = 1, written in summation form. It's the version you'll use most often when working with generating functions.

These identities form a toolkit for simplifying combinatorial sums. When you encounter a complicated sum involving binomial coefficients, check whether one of these standard identities (or a substitution into the Binomial Theorem) applies before attempting a proof from scratch.