6.4 Binomial Coefficients & Identities

The numbers $(k n)$ are called binomial coefficients because they're the coefficients when you expand $(x + y)^{n}$ . This section is about that expansion and the identities that come with it.

The binomial theorem

Binomial theorem

For $n \in N$ :
$(x + y)^{n} = j = 0 \sum n (j n) x^{n - j} y^{j} = (0 n) x^{n} + (1 n) x^{n - 1} y + \dots + (n n) y^{n} .$

Why (combinatorial reasoning): $(x + y)^{n} = (x + y) (x + y) \dots (x + y)$ . A term $x^{n - j} y^{j}$ comes from picking $y$ from $j$ of the $n$ factors and $x$ from the rest, which can be done in $(j n)$ ways.

From class: expand

(x + y)^{4}

$(x + y)^{4} = x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4}$
The coefficients 1, 4, 6, 4, 1 are row 4 of Pascal's triangle.

Finding one coefficient: the recipe

For $(a x^{p} + b y^{q})^{n}$ :

Write the general term: $(j n) (a x^{p})^{n - j} (b y^{q})^{j} = (j n) a^{n - j} b^{j} x^{p (n - j)} y^{q j}$ .
Match exponents to solve for $j$ . If there's no integer solution, the coefficient is 0.
Plug in, keeping the constants $a^{n - j} b^{j}$ and the sign (a negative $b$ means $(- 1)^{j}$ ).

From class: coefficient of

x^{12} y^{13}

(2 x - 3 y)^{25}

General term: $(j 25) (2 x)^{25 - j} (- 3 y)^{j}$ . Need $j = 13$ :
$(13 25) 2^{12} (- 3)^{13} = - (13 25) 2^{12} 3^{13} .$
For plain $(x + y)^{25}$ the coefficient would be just $(13 25) = (12 25)$ .

Quick facts

$(x + y)^{n}$ has $n + 1$ terms.
Coefficient of $x^{k}$ in $(1 + x)^{n}$ is $(k n)$ .

Corollaries: plug in numbers

Plug in

x

and

y

to get sums

Plug in	Identity	Meaning
$x = y = 1$	$k = 0 \sum n (k n) = 2^{n}$	total number of subsets
$x = 1, y = - 1$	$k = 0 \sum n (- 1)^{k} (k n) = 0$ ( $n \geq 1$ )	# even-size subsets = # odd-size subsets
$x = 1, y = 2$	$k = 0 \sum n 2^{k} (k n) = 3^{n}$

From class: even vs. odd subsets

From $0 = \sum_{i} (- 1)^{i} (i n) = \sum_{i even} (i n) - \sum_{i odd} (i n)$ , we get
$i even \sum (i n) = i odd \sum (i n) = 2^{n - 1} .$
A nonempty set has as many even-size subsets as odd-size subsets.

Pascal's identity and triangle

Pascal's identity

For $1 \leq k \leq n$ :
$(k n + 1) = (k - 1 n) + (k n)$

Combinatorial proof (from class). Know how to write this.

Let $S = {x_{1}, \dots, x_{n}, x_{n + 1}}$ . Count the $k$ -subsets of $S$ , which is $(k n + 1)$ , by splitting on whether $x_{n + 1}$ is chosen:

Contains $x_{n + 1}$ : choose the other $k - 1$ from ${x_{1}, \dots, x_{n}}$ , which is $(k - 1 n)$ .
Doesn't contain $x_{n + 1}$ : choose all $k$ from ${x_{1}, \dots, x_{n}}$ , which is $(k n)$ .

The cases are disjoint, so by the sum rule $(k n + 1) = (k - 1 n) + (k n)$ .

Pascal's triangle: each entry is the sum of the two above it, and the edges are $(0 n) = (n n) = 1$ .

$n$	row
0	1
1	1 1
2	1 2 1
3	1 3 3 1
4	1 4 6 4 1
5	1 5 10 10 5 1
6	1 6 15 20 15 6 1
7	1 7 21 35 35 21 7 1
8	1 8 28 56 70 56 28 8 1
9	1 9 36 84 126 126 84 36 9 1
10	1 10 45 120 210 252 210 120 45 10 1

Other identities

Vandermonde's identity (from class)

For $m, n, r \in N$ with $r \leq m$ and $r \leq n$ :
$(r m + n) = k = 0 \sum r (r - k m) (k n)$

Combinatorial proof: choose $r$ people from $m$ men and $n$ women. Split by the number of women $k$ : $(k n)$ ways to choose the women, $(r - k m)$ for the men. Sum over $k$ .

Special case ( $m = n = r$ , using $(n - k n) = (k n)$ ): $(n 2 n) = k = 0 \sum n (k n)^{2}$ .

Hockey-stick identity

k = 0 \sum r (k n + k) = (r n + r + 1)

Committee-and-leader identity

k (k n) = n (k - 1 n - 1), k = 1 \sum n k (k n) = n 2^{n - 1}

How to write a combinatorial proof

Template: count one set in two ways

Describe a set of objects (committees, subsets, bit strings, paths…).
Count it one way, and get the left side.
Count it another way, and get the right side.
Conclude: both count the same set, so they're equal.

k (k n) = n (k - 1 n - 1)

: choose a

k

-person committee with a leader from

n

people

Proof

Way 1: choose the committee ( $(k n)$ ), then its leader from the $k$ members ( $k$ ). Total $k (k n)$ .
Way 2: choose the leader from all $n$ people ( $n$ ), then the other $k - 1$ members from the remaining $n - 1$ ( $(k - 1 n - 1)$ ). Total $n (k - 1 n - 1)$ .
Both count the same thing, so they're equal. ∎

Algebraic proofs work too

Write each binomial as factorials, get a common denominator, and simplify. Pascal's identity this way:
$(k - 1 n) + (k n) = \frac{n !}{( k - 1 )! ( n - k + 1 )!} + \frac{n !}{k ! ( n - k )!} = \frac{n ! [ k + ( n - k + 1 )]}{k ! ( n - k + 1 )!} = \frac{( n + 1 )!}{k ! ( n + 1 - k )!} = (k n + 1) .$

Common mistakes

Forgetting to raise the constant to the power: in $(2 x)^{12}$ the coefficient is $2^{12}$ , not 2.
Losing the sign: $(- 3 y)^{13} = - 3^{13} y^{13}$ (odd power is negative).
Mixing up which exponent goes with $j$ . Always write the general term first.

About your class notes

In "Simplify $\sum_{i = 0}^{\infty} (i n) (- 1)^{i}$ ," the upper limit should be $n$ . (The terms are 0 past $n$ anyway, so the answer 0 is unaffected.)

Exam checklist

Expand $(x + y)^{n}$ for small $n$ using Pascal's triangle.
Find a specific coefficient in $(a x^{p} + b y^{q})^{n}$ , including sign and constants, or answer 0.
Number of terms: $n + 1$ .
Evaluate sums by plugging values into the binomial theorem.
Generate the next row of Pascal's triangle.
Prove Pascal's identity (combinatorially and algebraically); write a simple combinatorial proof.