Binomial Theorem, Pascal & Combinatorial Identities

For any nonnegative integer $n$,

The coefficient $\binom{n}{k}$ is called a binomial coefficient. The term containing $y^k$ (and hence $x^{n-k}$) is

Why it is true (combinatorial view): expanding $(x+y)^n=\underbrace{(x+y)(x+y)\cdots(x+y)}_{n}$ means choosing, from each of the $n$ factors, either $x$ or $y$. A term $x^{n-k}y^k$ arises from every way of choosing $y$ in exactly $k$ of the factors, and there are $\binom{n}{k}$ such choices.

Every interior entry of Pascal's Triangle is the sum of the two entries directly above it. Row $n$ (starting at $n=0$) lists $\binom{n}{0},\binom{n}{1},\dots,\binom{n}{n}$.

Combinatorial proof: to form a $k$-element committee from $n$ people, fix one person $P$. Either $P$ is on the committee (choose the other $k-1$ from the remaining $n-1$: $\binom{n-1}{k-1}$ ways) or $P$ is not (choose all $k$ from the remaining $n-1$: $\binom{n-1}{k}$ ways).

Set $x=y=1$ in the Binomial Theorem for the first; set $x=1,\,y=-1$ for the second. Combinatorial view of $2^n$: the total number of subsets of an $n$-element set, counted by size, is $\sum_k\binom{n}{k}$; but each element is independently in or out, giving $2^n$ subsets.

Summing a diagonal of Pascal's Triangle (the “stick”) gives the entry just below and to the side of its end (the “blade”). Combinatorial proof: to choose $r+1$ numbers from $\{1,2,\dots,n+1\}$, condition on the largest chosen number $i+1$. The remaining $r$ numbers come from $\{1,\dots,i\}$ in $\binom{i}{r}$ ways; summing over $i=r,\dots,n$ gives the total $\binom{n+1}{r+1}$.

Combinatorial proof: to choose a committee of $p$ people from a group of $m$ women and $n$ men, choose $k$ women and $p-k$ men; summing over all valid $k$ counts every committee exactly once, giving $\binom{m+n}{p}$. The special case $m=n=p$ gives $\sum_{k}\binom{n}{k}^2=\binom{2n}{n}$ (using symmetry $\binom{n}{n-k}=\binom{n}{k}$).

Combinatorial proof (choose a committee and a chair): count pairs (committee of size $k$, a distinguished chair on it). Left side: pick the committee ($\binom{n}{k}$ ways), then the chair from its $k$ members. Right side: pick the chair first ($n$ ways), then the remaining $k-1$ members from the other $n-1$ people. Two useful consequences:

The number of lattice paths from the origin $(0,0)$ to $(m,n)$ using only unit steps right ($R$) and up ($U$) is

Each path is a sequence of $m+n$ steps of which exactly $m$ are $R$; choosing which steps are $R$ determines the path.

1. Combinatorial (double counting). Count a set of objects two different ways; the two counts must be equal. This proved Pascal's Rule, Hockey Stick, Vandermonde, and the committee--chair identity above.

2. Generating functions. Treat $(1+x)^n=\sum_k\binom{n}{k}x^k$ as a polynomial whose coefficients store the binomial coefficients. Multiplying series adds exponents, so identities about sums become statements about products of polynomials. For instance, Vandermonde falls out of

by comparing the coefficient of $x^p$ on both sides: the left side gives $\sum_k\binom{m}{k}\binom{n}{p-k}$, the right gives $\binom{m+n}{p}$.

3. Extracting coefficients. The symbol $[x^p]F(x)$ means “the coefficient of $x^p$ in $F$.” Many contest problems reduce to computing $[x^p]$ of a product of simple factors---exactly the specific-coefficient technique from Section 1.

Let $\omega=e^{2\pi i/m}$ be a primitive $m$th root of unity. The key fact is the orthogonality relation

This average acts as an on/off switch that survives only when the exponent is a multiple of $m$. Apply it to the generating polynomial $f(x)=(1+x)^n=\sum_{k=0}^{n}\binom{n}{k}x^k$. Substituting $x=\omega^j$, weighting by $\omega^{-jr}$, and averaging over $j$ isolates exactly the terms with $k\equiv r\pmod m$:

The $m=2$, $r=0$ case recovers the even-index sum $2^{n-1}$ from Section 3; the filter is its far-reaching generalization.

Define, for any real (or complex) $\alpha$ and integer $k\ge 0$,

Newton's generalized binomial theorem then extends the expansion to non-integer exponents: for $|x|<1$,

When $\alpha=n$ is a nonnegative integer the numerator eventually hits the factor $(\alpha-\alpha)=0$, killing all terms past $k=n$ and recovering the ordinary finite Binomial Theorem. For other $\alpha$ the series is genuinely infinite.

Negative integer upper index (ties back to stars and bars). Setting $\alpha=-n$ and simplifying the falling product gives

so that

The coefficient $\binom{n+k-1}{k}$ is exactly the stars-and-bars count of the ways to write $k$ as an ordered sum of $n$ nonnegative integers---so the negative binomial series is the generating function for distributing $k$ identical items into $n$ distinct boxes.

Every summation identity in this unit is a shadow of a single equation between generating functions, read off by comparing one coefficient. The recipe: encode each side as a power series, multiply, and equate $[x^N]$. Because multiplying series convolves their coefficients,

a product of two known series manufactures a sum of products of coefficients---precisely the shape of Vandermonde, the subcommittee identity, and their kin. This “snake-oil” method turns the search for a closed form into the routine task of recognizing a product.