Binomial Coefficients & Identities

Textbook

Rosen 8e, Section 6.4

Study day

Monday, Nov 9

Homework

Written HW 8: 1–35 odd

Progress

Notes not read 0 / 21 problems graded

Work each problem on paper before opening its solution, then mark it Got it or Review. Do the Core problems first if you're short on time.

6.4 #1 Core Expansion

Find the expansion of $(x + y)^{4}$

a) using combinatorial reasoning, as in Example 1.
b) using the binomial theorem.

Show solution

Answer

x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4}

a) $(x + y)^{4} = (x + y) (x + y) (x + y) (x + y)$ . Each term in the expansion picks $x$ or $y$ from each of the 4 factors. A term $x^{4 - j} y^{j}$ arises once for each way to choose which $j$ factors contribute $y$ : $(j 4)$ ways. So the coefficients are $(0 4), \dots, (4 4) = 1, 4, 6, 4, 1$ .

b) $(x + y)^{4} = j = 0 \sum 4 (j 4) x^{4 - j} y^{j} = x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4} .$

6.4 #3 Core Expansion

Find the expansion of $(x + y)^{6}$ .

Show solution

Answer

x^{6} + 6 x^{5} y + 15 x^{4} y^{2} + 20 x^{3} y^{3} + 15 x^{2} y^{4} + 6 x y^{5} + y^{6}

Row 6 of Pascal's triangle is 1, 6, 15, 20, 15, 6, 1:
$(x + y)^{6} = x^{6} + 6 x^{5} y + 15 x^{4} y^{2} + 20 x^{3} y^{3} + 15 x^{2} y^{4} + 6 x y^{5} + y^{6} .$

6.4 #5 Core Number of terms

How many terms are there in the expansion of $(x + y)^{100}$ after like terms are collected?

Show solution

Answer

101

Terms are $x^{100 - j} y^{j}$ for $j = 0, 1, \dots, 100$ : 101 terms.

6.4 #7 Core Coefficient

What is the coefficient of $x^{9}$ in $(2 - x)^{19}$ ?

Show solution

Answer

- 2^{10} (9 19) = - 94, 595, 072

General term: $(j 19) 2^{19 - j} (- x)^{j} = (j 19) 2^{19 - j} (- 1)^{j} x^{j}$ .

For $x^{9}$ : $j = 9$ :
$(9 19) 2^{10} (- 1)^{9} = - 2^{10} (9 19) = - 1024 \cdot 92, 378 = - 94, 595, 072.$

6.4 #9 Core Coefficient

What is the coefficient of $x^{101} y^{99}$ in the expansion of $(2 x - 3 y)^{200}$ ?

Show solution

Answer

- 2^{101} 3^{99} (99 200)

General term: $(j 200) (2 x)^{200 - j} (- 3 y)^{j}$ . Need $j = 99$ (then $200 - j = 101$ ✓):
$(99 200) 2^{101} (- 3)^{99} = - 2^{101} 3^{99} (99 200) .$
The sign is negative because 99 is odd.

6.4 #11 Core Expansion

Use the binomial theorem to expand $(3 x^{4} - 2 y^{3})^{5}$ into a sum of terms of the form $c x^{a} y^{b}$ .

Show solution

Answer

243 x^{20} - 810 x^{16} y^{3} + 1080 x^{12} y^{6} - 720 x^{8} y^{9} + 240 x^{4} y^{12} - 32 y^{15}

$j = 0 \sum 5 (j 5) (3 x^{4})^{5 - j} (- 2 y^{3})^{j}$ , with row 5 = 1, 5, 10, 10, 5, 1:

$j$	$(j 5) 3^{5 - j} (- 2)^{j}$	term
0	$1 \cdot 243 \cdot 1 = 243$	$243 x^{20}$
1	$5 \cdot 81 \cdot (- 2) = - 810$	$- 810 x^{16} y^{3}$
2	$10 \cdot 27 \cdot 4 = 1080$	$1080 x^{12} y^{6}$
3	$10 \cdot 9 \cdot (- 8) = - 720$	$- 720 x^{8} y^{9}$
4	$5 \cdot 3 \cdot 16 = 240$	$240 x^{4} y^{12}$
5	$1 \cdot 1 \cdot (- 32) = - 32$	$- 32 y^{15}$

6.4 #13 Core Coefficient

Use the binomial theorem to find the coefficient of $x^{a} y^{b}$ in the expansion of $(2 x^{3} - 4 y^{2})^{7}$ , where

a) $a = 9, b = 8$
b) $a = 8, b = 9$
c) $a = 0, b = 14$
d) $a = 12, b = 6$
e) $a = 18, b = 2$

Show solution

Answer

a) 71,680 b) 0 c) −16,384 d) −35,840 e) −1,792

General term: $(j 7) (2 x^{3})^{7 - j} (- 4 y^{2})^{j} = (j 7) 2^{7 - j} (- 4)^{j} x^{3 (7 - j)} y^{2 j}$ .

a) $2 j = 8 \Rightarrow j = 4$ ; check $3 (3) = 9$ ✓. $(4 7) 2^{3} (- 4)^{4} = 35 \cdot 8 \cdot 256 = 71, 680$ .

b) $2 j = 9$ has no integer solution: 0.

c) $j = 7$ , $x^{0}$ ✓: $(7 7) 2^{0} (- 4)^{7} = - 16, 384$ .

d) $j = 3$ , $3 (4) = 12$ ✓: $(3 7) 2^{4} (- 4)^{3} = 35 \cdot 16 \cdot (- 64) = - 35, 840$ .

e) $j = 1$ , $3 (6) = 18$ ✓: $(1 7) 2^{6} (- 4) = 7 \cdot 64 \cdot (- 4) = - 1, 792$ .

6.4 #15 Challenge Coefficient formula

Give a formula for the coefficient of $x^{k}$ in the expansion of $(x^{2} - 1/ x)^{100}$ , where $k$ is an integer.

Show solution

Answer

$(- 1)^{(200 - k) /3} (( 200 - k ) /3 100)$ if $k \equiv 2 (mod 3)$ and $- 100 \leq k \leq 200$ ; otherwise 0.

General term:
$(j 100) (x^{2})^{100 - j} (- \frac{1}{x})^{j} = (- 1)^{j} (j 100) x^{200 - 2 j - j} = (- 1)^{j} (j 100) x^{200 - 3 j} .$
Set $200 - 3 j = k$ , so $j = \frac{200 - k}{3}$ . This must be an integer between 0 and 100:

integer exactly when $k \equiv 200 \equiv 2 (mod 3)$
$0 \leq j \leq 100$ exactly when $- 100 \leq k \leq 200$

So the coefficient is $(- 1)^{(200 - k) /3} (( 200 - k ) /3 100)$ in that case, and $0$ otherwise.

6.4 #17 Core Pascal's triangle

What is the row of Pascal's triangle containing the binomial coefficients $(k 9)$ , $0 \leq k \leq 9$ ?

Show solution

Answer

1 9 36 84 126 126 84 36 9 1

Build from row 8 (1, 8, 28, 56, 70, 56, 28, 8, 1) by adding neighbors:
$1, 1 + 8 = 9, 8 + 28 = 36, 28 + 56 = 84, 56 + 70 = 126, 126, 84, 36, 9, 1.$

6.4 #19 Core Inequality proof

Show that $(k n) \leq 2^{n}$ for all positive integers $n$ and all integers $k$ with $0 \leq k \leq n$ .

Show solution

By the binomial theorem with $x = y = 1$ : $j = 0 \sum n (j n) = 2^{n}$ . Every term is nonnegative, so any single term is at most the whole sum: $(k n) \leq 2^{n}$ . ∎

(Combinatorially: $(k n)$ counts the $k$ -subsets of an $n$ -set, which are some of the $2^{n}$ subsets.)

6.4 #21 Extra Inequality proof

Show that if $n$ and $k$ are integers with $1 \leq k \leq n$ , then $(k n) \leq n^{k} / 2^{k - 1}$ .

Show solution

(k n) = \frac{n ( n - 1 ) ( n - 2 ) \dots ( n - k + 1 )}{k ( k - 1 ) ( k - 2 ) \dots 2 \cdot 1} .

Numerator: $k$ factors, each $\leq n$ , so it is $\leq n^{k}$ .
Denominator: the $k - 1$ factors $k, k - 1, \dots, 2$ are each $\geq 2$ , so $k! \geq 2^{k - 1}$ .

Therefore $(k n) \leq \frac{n ^{k}}{2 ^{k - 1}}$ . ∎

6.4 #23 Core Pascal's identity

Prove Pascal's identity, using the formula for $(r n)$ .

Show solution

Show $(k - 1 n) + (k n) = (k n + 1)$ for $1 \leq k \leq n$ :
$(k - 1 n) + (k n) = \frac{n !}{( k - 1 )! ( n - k + 1 )!} + \frac{n !}{k ! ( n - k )!} = \frac{n ! \cdot k}{k ! ( n - k + 1 )!} + \frac{n ! ( n - k + 1 )}{k ! ( n - k + 1 )!} = \frac{n ! ( k + n - k + 1 )}{k ! ( n - k + 1 )!} = \frac{( n + 1 )!}{k ! ( n + 1 - k )!} = (k n + 1) . common denominator$ ∎

6.4 #25 Core Combinatorial proof

Prove that if $n$ and $k$ are integers with $1 \leq k \leq n$ , then $k (k n) = n (k - 1 n - 1)$ ,

a) using a combinatorial proof.
b) using an algebraic proof based on the formula for $(r n)$ .

Show solution

a) Count the ways to pick, from $n$ people, a committee of $k$ with a designated chair.

Pick the committee ( $(k n)$ ), then its chair from its $k$ members ( $k$ ): $k (k n)$ .
Pick the chair from all $n$ people ( $n$ ), then the other $k - 1$ members from the remaining $n - 1$ ( $(k - 1 n - 1)$ ): $n (k - 1 n - 1)$ .

Same set counted two ways, so the two are equal. ∎

b)
$k (k n) = k \cdot \frac{n !}{k ! ( n - k )!} = \frac{n !}{( k - 1 )! ( n - k )!} = n \cdot \frac{( n - 1 )!}{( k - 1 )! ( ( n - 1 ) - ( k - 1 ) ) !} = n (k - 1 n - 1) .$ ∎

6.4 #27 Extra Identity + recursion

Show that if $n$ and $k$ are positive integers, then $(k n + 1) = (n + 1) (k - 1 n) / k$ . Use this identity to construct an inductive definition of the binomial coefficients.

Show solution

Identity:
$\frac{n + 1}{k} (k - 1 n) = \frac{n + 1}{k} \cdot \frac{n !}{( k - 1 )! ( n - k + 1 )!} = \frac{( n + 1 )!}{k ! ( n + 1 - k )!} = (k n + 1) .$

Inductive definition:

Basis: $(0 n) = 1$ for all $n \geq 0$ , and $(k 0) = 0$ for $k \geq 1$ .
Recursive step: for $n \geq 0$ , $k \geq 1$ : $(k n + 1) = \frac{n + 1}{k} (k - 1 n)$ .

6.4 #29 Extra Identity

Let $n$ be a positive integer. Show that $(n + 1 2 n) + (n 2 n) = (n + 1 2 n + 2) / 2$ .

Show solution

LHS: by Pascal's identity, $(n + 1 2 n) + (n 2 n) = (n + 1 2 n + 1)$ .

RHS: by Pascal's identity, $(n + 1 2 n + 2) = (n 2 n + 1) + (n + 1 2 n + 1)$ . By symmetry $(n 2 n + 1) = (( 2 n + 1 ) - n 2 n + 1) = (n + 1 2 n + 1)$ . So $(n + 1 2 n + 2) = 2 (n + 1 2 n + 1)$ , i.e. $(n + 1 2 n + 2) /2 = (n + 1 2 n + 1)$ .

Both sides equal $(n + 1 2 n + 1)$ . ∎

6.4 #31 Challenge Hockey stick

Prove the hockey-stick identity $k = 0 \sum r (k n + k) = (r n + r + 1)$ whenever $n$ and $r$ are positive integers,

a) using a combinatorial argument.
b) using Pascal's identity.

Show solution

a) The RHS counts bit strings of length $n + r + 1$ with exactly $r$ zeros and $n + 1$ ones (choose the positions of the zeros).

Classify these strings by the position of the last 1. Say $k$ zeros come before the last 1 (so $0 \leq k \leq r$ ). Then the last 1 is at position $n + k + 1$ ; before it are $n$ ones and $k$ zeros in some order ( $(k n + k)$ ways); after it, the remaining $r - k$ positions are all 0. Summing over $k$ gives the LHS. ∎

b) Induction on $r$ .
Basis ( $r = 1$ ): $(0 n) + (1 n + 1) = 1 + (n + 1) = n + 2 = (1 n + 2)$ . ✓
Step: assume $\sum_{k = 0}^{r} (k n + k) = (r n + r + 1)$ . Then
$k = 0 \sum r + 1 (k n + k) = (r n + r + 1) + (r + 1 n + r + 1) = (r + 1 n + r + 2),$
by Pascal's identity, which is the statement for $r + 1$ . ∎

6.4 #33 Challenge Combinatorial proof

Give a combinatorial proof that $k = 1 \sum n k (k n) = n 2^{n - 1}$ . (Hint: count in two ways the number of ways to select a committee and then select a leader of the committee.)

Show solution

Count (committee, leader) pairs from $n$ people, where the committee is any nonempty subset and the leader is one of its members.

Leader first: choose the leader ( $n$ ways), then decide for each of the other $n - 1$ people whether they're on the committee ( $2^{n - 1}$ ways). Total $n 2^{n - 1}$ .
Committee first: for a committee of size $k$ there are $(k n)$ choices and then $k$ choices of leader. Summing over $k = 1, \dots, n$ gives $\sum_{k = 1}^{n} k (k n)$ .

Both count the same set. ∎

6.4 #35 Core Binomial corollary

Show that a nonempty set has the same number of subsets with an odd number of elements as it does subsets with an even number of elements.

Show solution

Let $∣ S ∣ = n \geq 1$ . Binomial theorem with $x = 1$ , $y = - 1$ :
$0 = (1 + (- 1))^{n} = k = 0 \sum n (- 1)^{k} (k n) = [(0 n) + (2 n) + (4 n) + \dots] - [(1 n) + (3 n) + \dots] .$
So $(0 n) + (2 n) + \dots = (1 n) + (3 n) + \dots$ . The left side counts even-size subsets and the right side counts odd-size subsets. ∎

(Needs $n \geq 1$ : for $n = 0$ , $(1 - 1)^{0} = 1$ , not 0.)

Custom (from lecture) Core Coefficient Not from HW

a) What is the coefficient of $x^{12} y^{13}$ in $(x + y)^{25}$ ?
b) What is the coefficient of $x^{12} y^{13}$ in $(2 x - 3 y)^{25}$ ?
c) What is the coefficient of $x^{5}$ in $(1 + 2 x)^{8}$ ?

Show solution

Answer

a) $(13 25)$ b) $- (13 25) 2^{12} 3^{13}$ c) $(5 8) 2^{5} = 1792$

a) $(13 25) = (12 25) = 5, 200, 300$ .

b) General term $(j 25) (2 x)^{25 - j} (- 3 y)^{j}$ with $j = 13$ : $(13 25) 2^{12} (- 3)^{13} = - (13 25) 2^{12} 3^{13}$ .

c) General term $(j 8) (2 x)^{j}$ (with $1^{8 - j} = 1$ ), $j = 5$ : $(5 8) 2^{5} = 56 \cdot 32 = 1792$ .

Custom Core Sums via binomial theorem Not from HW

Evaluate in closed form:

a) $k = 0 \sum n 3^{k} (k n)$
b) $k = 0 \sum n (- 1)^{k} 2^{n - k} (k n)$
c) $k = 0 \sum 10 (k 10)^{2}$ (use Vandermonde)

Show solution

Answer

a) $4^{n}$ b) $1$ c) $(10 20) = 184, 756$

a) $(x + y)^{n}$ with $x = 1$ , $y = 3$ : $\sum_{k} (k n) 1^{n - k} 3^{k} = (1 + 3)^{n} = 4^{n}$ .

b) $x = 2$ , $y = - 1$ : $\sum_{k} (k n) 2^{n - k} (- 1)^{k} = (2 - 1)^{n} = 1$ .

c) Vandermonde with $m = n = r = 10$ : $(10 20) = \sum_{k = 0}^{10} (10 - k 10) (k 10) = \sum_{k} (k 10)^{2}$ . So the sum is $(10 20) = 184, 756$ .

Custom (from lecture) Core Combinatorial proof Not from HW

Give a combinatorial proof of Pascal's identity: $(k n + 1) = (k - 1 n) + (k n)$ for $1 \leq k \leq n$ .

Show solution

Let $S = {x_{1}, \dots, x_{n}, x_{n + 1}}$ . The left side counts the $k$ -element subsets of $S$ . Count them a second way by splitting on whether $x_{n + 1}$ is included:

Subsets containing $x_{n + 1}$ : the other $k - 1$ elements come from ${x_{1}, \dots, x_{n}}$ : $(k - 1 n)$ .
Subsets not containing $x_{n + 1}$ : all $k$ elements come from ${x_{1}, \dots, x_{n}}$ : $(k n)$ .

These cases are disjoint and cover everything, so by the sum rule $(k n + 1) = (k - 1 n) + (k n)$ . ∎

Next: 6.5 Generalized Permutations & Combinations