EF Binomial coefficients

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\)
\(\displaystyle \binom{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{equation*} (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 + \dotsb + \binom{n}{n-1}\,xy^{n-1} + \binom{n}{n}\,y^n, \end{equation*}

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, \\ (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 = x^3 + 3 x^2y + 3 x y^2 + y^3. \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 = \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\\ \amp = x^5 - 10 x^4 + 40 x^3 - 80 x^2 + 80 x - 32. \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*} \binom{13}{9} (3x)^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{.}\)

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: