EF Binomial coefficients

Skip to main content

Section 23.1 Binomial coefficients

binomial: 🔗
an expression of the form $(x + y)^{n},$ where $n \in N$ and $x, y$ are real numbers (or elements of any commutative ring with identity)

Example 23.1.1. Expanding binomials.

Expanding binomials gets more complicated as

n

increases.

\begin{aligned} (x + y)^{2} & = x^{2} + 2 x y + y^{2} \\ (x + y)^{3} & = (x + y) (x^{2} + 2 x y + y^{2}) = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3} \\ (x + y)^{4} & = (x + y) (x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}) = x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4} \\ (x + y)^{5} & = (x + y) (x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4}) \\ = x^{5} + 5 x^{4} y + 10 x^{3} y^{2} + 10 x^{2} y^{3} + 5 x y^{4} + y^{5} \\ ⋮ \end{aligned}

The symmetry in each of these expansions should be expected: we would get the same expression in the summation opposite order if we swapped

x

and

y,

since

(x + y)^{n} = (y + x)^{n} .

binomial coefficient: 🔗
a number appearing as a coefficient in the expansion of $(x + y)^{n}$
$(\binom{n}{k})$: 🔗
the $k^{th}$ coefficient in the expansion of $(x + y)^{n}$ ( $0 \leq k \leq n$ )

To better understand the complexity of binomial expansions, we should look for and exploit patterns. We have already expanded some binomial expressions for small exponents in Example 23.1.1 — let’s extract the binomial coefficients from those expressions.

\begin{matrix} (\binom{0}{0}) \\ (\binom{1}{0}) (\binom{1}{1}) \\ (\binom{2}{0}) (\binom{2}{1}) (\binom{2}{2}) \\ (\binom{3}{0}) (\binom{3}{1}) (\binom{3}{2}) (\binom{3}{3}) \\ (\binom{4}{0}) (\binom{4}{1}) (\binom{4}{2}) (\binom{4}{3}) (\binom{4}{4}) \\ (\binom{5}{0}) (\binom{5}{1}) (\binom{5}{2}) (\binom{5}{3}) (\binom{5}{4}) (\binom{5}{5}) \\ (\binom{6}{0}) (\binom{6}{1}) (\binom{6}{2}) (\binom{6}{3}) (\binom{6}{4}) (\binom{6}{5}) (\binom{6}{6}) \\ ⋮ \end{matrix}

⟶

\begin{matrix} 1 \\ 1 1 \\ 1 2 1 \\ 1 3 3 1 \\ 1 4 6 4 1 \\ 1 5 10 10 5 1 \\ 1 6 15 20 15 6 1 \\ ⋮ \end{matrix}

Figure 23.1.2. Pascal’s triangle.

Remark 23.1.3.

Figure 23.1.2 above sure looks a lot like Figure 22.4.1.

Theorem 23.1.4. Binomial Theorem.

For every

x, y \in R

and every

n \in N,

we have

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k} = (\binom{n}{0}) x^{n} + (\binom{n}{1}) x^{n - 1} y + (\binom{n}{2}) x^{n - 2} y^{2} + \dots + (\binom{n}{n - 1}) x y^{n - 1} + (\binom{n}{n}) y^{n},

where

(\binom{n}{k}) = C_{k}^{n} = \frac{n!}{k! (n - k)!} .

Informal direct proof outline.

Write

(x + y)^{n} = (x + y) (x + y) \dots (x + y),

with

n

factors. To expand this out, we generalize the FOIL method: from each factor, choose either

x

or

y,

then multiply all your choices together. Then add the results of all possible such products. For example,

\begin{aligned} (x + y)^{2} & = x x + x y + y x + y y = x^{2} + 2 x y + y^{2}, \\ (x + y)^{3} & = x x x + x x y + x y x + x y y + y x x + y x y + y y x + y y y = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3} . \end{aligned}

When forming a specific product, if you chose

y

for

k

out of

n

choices, you must have chosen

x

for the remaining

n - k

of the

n

choices. The result will be

x^{n - k} y^{k} .

So to figure out the coefficient on

x^{n - k} y^{k},

just count how many ways there are to choose

y

for

k

of the

n

choices. This is just

C_{k}^{n},

where we choose

k

factors of

(x + y)

to give us a

y,

and the rest to give us an

x .

Induction proof outline.

Base case.

The cases of

n = 0, 1

are trivially true.

Induction step.

Use the binomial formula for

(x + y)^{n - 1}

to obtain the binomial formula for

(x + y)^{n},

by manipulating

\begin{aligned} (x + y)^{n} & = (x + y) (x + y)^{n - 1} \\ = (x + y) (C_{0}^{n - 1} x^{n - 1} + C_{1}^{n - 1} x^{n - 2} y + \dots + C_{n - 1}^{n - 1} y^{n - 1}) . \end{aligned}

Worked Example 23.1.5. Expanding a binomial.

Expand

(x - 2)^{5} .

We saw that the

n = 5

row of Pascal’s triangle is

1, 5, 10, 10, 5, 1 .

\begin{aligned} (x - 2)^{5} \\ (x + (- 2))^{5} \\ = (\binom{5}{0}) x^{5} + (\binom{5}{1}) x^{4} (- 2) + (\binom{5}{2}) x^{3} (- 2)^{2} + (\binom{5}{3}) x^{2} (- 2)^{3} + (\binom{5}{4}) x (- 2)^{4} + (\binom{5}{5}) (- 2)^{5} \\ = x^{5} - 10 x^{4} + 40 x^{3} - 80 x^{2} + 80 x - 32. \end{aligned}

Worked Example 23.1.6. Determining a specific coefficient in a binomial expansion.

What is the coefficient on the

x^{4} y^{9}

term in the expansion of

(3 x + y)^{13} ?

Considering

(3 x + y)^{13} = ((3 x) + y)^{13},

the

x^{4} y^{9}

term is

\begin{aligned} (\binom{13}{9}) (3 x)^{4} y^{9} & = \frac{13!}{9! 4!} \cdot 3^{4} x^{4} y^{9} \\ = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 27 \cdot 3}{4 \cdot 3 \cdot 2} x^{4} y^{9} \\ = (13 \cdot 3 \cdot 11 \cdot 5 \cdot 27) x^{4} y^{9} . \end{aligned}

So the desired coefficient is

57, 915 .

<Prev ^Top Next>