Section 23.1 Binomial coefficients

binomial: an expression of the form \({(x + y)}^n \text{,}\) 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{align*} {(x + y)}^2 \amp = x^2 + 2 x y + y^2 \\ {(x + y)}^3 \amp = (x + y) (x^2 + 2 x y + y^2) = x^3 + 3 x^2 y + 3 x y^2 + y^3 \\ {(x + y)}^4 \amp = (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 \amp = (x + y) (x^4 + 4 x^3 y + 6 x^2 y^2 + 4 x y^3 + y^4) \\ \amp = x^5 + 5 x^4 y + 10 x^3 y^2 + 10 x^2 y^3 + 5 x y^4 + y^5 \\ \amp \vdots \end{align*}

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 \text{,}\) since \({(x + y)}^n = {(y + x)}^n \text{.}\)

binomial coefficient: a number appearing as a coefficient in the expansion of \({(x + y)}^n \)
\(\dbinom{n}{k} \): the \(\nth[k] \) coefficient in the expansion of \({(x + y)}^n \) (\(0 \le k \le 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{gather*} \tbinom{0}{0} \\ \tbinom{1}{0} \quad \tbinom{1}{1} \\ \tbinom{2}{0} \quad \tbinom{2}{1} \quad \tbinom{2}{2} \\ \tbinom{3}{0} \quad \tbinom{3}{1} \quad \tbinom{3}{2} \quad \tbinom{3}{3} \\ \tbinom{4}{0} \quad \tbinom{4}{1} \quad \tbinom{4}{2} \quad \tbinom{4}{3} \quad \tbinom{4}{4}\\ \tbinom{5}{0} \quad \tbinom{5}{1} \quad \tbinom{5}{2} \quad \tbinom{5}{3} \quad \tbinom{5}{4} \quad \tbinom{5}{5}\\ \tbinom{6}{0} \quad \tbinom{6}{1} \quad \tbinom{6}{2} \quad \tbinom{6}{3} \quad \tbinom{6}{4} \quad \tbinom{6}{5} \quad \tbinom{6}{6}\\ \vdots \end{gather*}

\begin{equation*} \longrightarrow \end{equation*}

\begin{gather*} \;1\; \\ \;1\; \quad \;1\; \\ \;1\; \quad \;2\; \quad \;1\; \\ \;1\; \quad \;3\; \quad \;3\; \quad \;1\;\\ \;1\; \quad \;4\; \quad \;6\; \quad \;4\; \quad \;1\;\\ \;1\; \quad \;5\; \quad \;10\; \quad 10\; \quad \;5\; \quad \;1\;\\ \;1\; \quad \;6\; \quad \;15\; \quad 20 \quad \;15\; \quad \;6\; \quad \;1\;\\ \vdots \end{gather*}

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 \text{,}\) we have

\begin{align*} {(x + y)}^n \amp = \sum_{k=0}^n \binom{n}{k} \, x^{n - k} y^k\\ \amp = \tbinom{n}{0} \, x^n + \tbinom{n}{1} \, x^{n-1} y + \tbinom{n}{2} \, x^{n-2} y^2 + \dotsb + \tbinom{n}{n-1} \, x y^{n-1} + \tbinom{n}{n} \, y^n \end{align*}

where

\begin{equation*} \binom{n}{k} = \combinationalt{n}{k} = \choosefuncformula{n}{k}{(n-k)} \text{.} \end{equation*}

Informal direct proof outline.

Write \({(x + y)}^n = (x+y)(x+y)\dotsm(x+y) \text{,}\) with \(n \) factors. To expand this out, we generalize the FOIL method: from each factor, choose either \(x \) or \(y \text{,}\) then multiply all your choices together. Then add the results of all possible such products. For example:

\begin{align*} {(x + y)}^2 \amp = x x + x y + y x + y y = x^2 + 2 x y + y^2 \text{,} \\ {(x + y)}^3 \amp = x x x + x x y + x y x + x y y + y x x + y x y + y y x + y y y \\ \amp = x^3 + 3 x^2y + 3 x y^2 + y^3 \text{.} \end{align*}

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 \text{.}\) So to figure out the coefficient on \(x^{n - k} y^k \text{,}\) just count how many ways there are to choose \(y \) for \(k \) of the \(n \) choices. This is just \(\combinationalt{n}{k} \text{,}\) where we choose \(k \) factors of \((x+y) \) to give us a \(y \text{,}\) and the rest to give us an \(x \text{.}\)

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 \text{,}\) by manipulating

\begin{align*} {(x + y)}^n \amp = (x + y) {(x + y)}^{n - 1} \\ \amp = (x + y) \bbrac{ \combinationalt{n-1}{0} \, x^{n - 1} + \combinationalt{n - 1}{1} \, x^{n - 2} y + \dotsb + \combinationalt{n - 1}{n - 1} \, y^{n - 1} }\text{.} \end{align*}

Worked Example 23.1.5. Expanding a binomial.

Expand \({(x - 2)}^5 \text{.}\)

Solution.

We saw that the \(n = 5 \) row of Pascal’s triangle is \(1,5,10,10,5,1 \text{.}\)

\begin{align*} \amp {(x - 2)}^5 \\ \amp = \bbrac{x + (- 2)}^5 \\ \amp = \tbinom{5}{0} x^5 + \tbinom{5}{1} x^4 (-2) + \tbinom{5}{2} x^3 {(-2)}^2 \\ \amp \phantom{=} \quad + \tbinom{5}{3} x^2 {(-2)}^3 + \tbinom{5}{4} x {(-2)}^4 + \tbinom{5}{5} {(-2)}^5 \\ \amp = x^5 - 10 x^4 + 40 x^3 - 80 x^2 + 80 x - 32 \text{.} \end{align*}

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} \text{?}\)

Solution.

Considering

\begin{equation*} {(3 x + y)}^{13} = {\bbrac{(3 x) + y}}^{13} \text{,} \end{equation*}

the \(x^4 y^9 \) term is

\begin{align*} \tbinom{13}{9} {(3 x)}^4 y^9 \amp = \choosefuncformula{13}{9}{4} \cdot 3^4 x^4 y^9\\ \amp = \frac{13 \cdot 12 \cdot 11 \cdot 10 \cdot 27 \cdot 3}{4\cdot 3 \cdot 2} x^4 y^9 \\ \amp = (13 \cdot 3 \cdot 11 \cdot 5 \cdot 27) x^4 y^9 \text{.} \end{align*}

So the desired coefficient is \(57,915 \text{.}\)

Prev Top Next