1.9 Binomial Theorem

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\ffrac }[2]{\frac {\text {\footnotesize $#1$}}{\text {\footnotesize $#2$}}} \newcommand {\newrobustcmd }[0]{} \newcommand {\csshow }[1]{\begingroup \expandafter \endgroup \expandafter \show \csname #1\endcsname } \newcommand {\csmeaning }[1]{\ifcsname #1\endcsname \expandafter \meaning \csname #1\endcsname \else \detokenize {undefined}\fi } \newcommand {\ifdefmacro }[0]{} \newcommand {\ifdefparam }[0]{} \newcommand {\ifdefprotected }[0]{} \newcommand {\ifnumequal }[1]{\ifnumcomp {#1}=} \newcommand {\ifnumgreater }[1]{\ifnumcomp {#1}>} \newcommand {\ifnumless }[1]{\ifnumcomp {#1}<} \newcommand {\ifdimequal }[1]{\ifdimcomp {#1}=} \newcommand {\ifdimgreater }[1]{\ifdimcomp {#1}>} \newcommand {\ifdimless }[1]{\ifdimcomp {#1}<} \newcommand {\expandonce }[1]{\unexpanded \expandafter {#1}} \newcommand {\csexpandonce }[1]{\expandafter \expandonce \csname #1\endcsname } \newcommand {\protecting }[0]{} \newcommand {\csdef }[1]{\expandafter \def \csname #1\endcsname } \newcommand {\csedef }[1]{\expandafter \edef \csname #1\endcsname } \newcommand {\csgdef }[1]{\expandafter \gdef \csname #1\endcsname } \newcommand {\csxdef }[1]{\expandafter \xdef \csname #1\endcsname } \newcommand {\cslet }[2]{\expandafter \let \csname #1\endcsname #2} \newcommand {\letcs }[2]{\ifcsdef {#2} {\expandafter \let \expandafter #1\csname #2\endcsname } {\undef #1}} \newcommand {\csletcs }[2]{\ifcsdef {#2} {\expandafter \let \csname #1\expandafter \endcsname \csname #2\endcsname } {\csundef {#1}}} \newcommand {\csuse }[1]{\ifcsname #1\endcsname \csname #1\expandafter \endcsname \fi } \newcommand {\appto }[2]{\ifundef {#1} {\edef #1{\unexpanded {#2}}} {\edef #1{\expandonce #1\unexpanded {#2}}}} \newcommand {\eappto }[2]{\ifundef {#1} {\edef #1{#2}} {\edef #1{\expandonce #1#2}}} \newcommand {\gappto }[2]{\ifundef {#1} {\xdef #1{\unexpanded {#2}}} {\xdef #1{\expandonce #1\unexpanded {#2}}}} \newcommand {\xappto }[2]{\ifundef {#1} {\xdef #1{#2}} {\xdef #1{\expandonce #1#2}}} \newcommand {\preto }[2]{\ifundef {#1} {\edef #1{\unexpanded {#2}}} {\edef #1{\unexpanded {#2}\expandonce #1}}} \newcommand {\epreto }[2]{\ifundef {#1} {\edef #1{#2}} {\edef #1{#2\expandonce #1}}} \newcommand {\gpreto }[2]{\ifundef {#1} {\xdef #1{\unexpanded {#2}}} {\xdef #1{\unexpanded {#2}\expandonce #1}}} \newcommand {\xpreto }[2]{\ifundef {#1} {\xdef #1{#2}} {\xdef #1{#2\expandonce #1}}} \newcommand {\csappto }[1]{\expandafter \appto \csname #1\endcsname } \newcommand {\cseappto }[1]{\expandafter \eappto \csname #1\endcsname } \newcommand {\csgappto }[1]{\expandafter \gappto \csname #1\endcsname } \newcommand {\csxappto }[1]{\expandafter \xappto \csname #1\endcsname } \newcommand {\cspreto }[1]{\expandafter \preto \csname #1\endcsname } \newcommand {\csepreto }[1]{\expandafter \epreto \csname #1\endcsname } \newcommand {\csgpreto }[1]{\expandafter \gpreto \csname #1\endcsname } \newcommand {\csxpreto }[1]{\expandafter \xpreto \csname #1\endcsname } \newcommand {\csnumdef }[1]{\expandafter \numdef \csname #1\endcsname } \newcommand {\csnumgdef }[1]{\expandafter \numgdef \csname #1\endcsname } \newcommand {\csdimdef }[1]{\expandafter \dimdef \csname #1\endcsname } \newcommand {\csdimgdef }[1]{\expandafter \dimgdef \csname #1\endcsname } \newcommand {\csgluedef }[1]{\expandafter \gluedef \csname #1\endcsname } \newcommand {\csgluegdef }[1]{\expandafter \gluegdef \csname #1\endcsname } \newcommand {\mudef }[2]{\ifundef #1{\def #1{0mu}}{}\edef #1{\the \muexpr #2}} \newcommand {\csmudef }[1]{\expandafter \mudef \csname #1\endcsname } \newcommand {\csmugdef }[1]{\expandafter \mugdef \csname #1\endcsname } \newcommand {\listbreak }[0]{} \newcommand {\listadd }[2]{\ifblank {#2}{}{\appto #1{#2|}}} \newcommand {\listgadd }[2]{\ifblank {#2}{}{\gappto #1{#2|}}} \newcommand {\listcsadd }[1]{\expandafter \listadd \csname #1\endcsname } \newcommand {\listcseadd }[1]{\expandafter \listeadd \csname #1\endcsname } \newcommand {\listcsgadd }[1]{\expandafter \listgadd \csname #1\endcsname } \newcommand {\listcsxadd }[1]{\expandafter \listxadd \csname #1\endcsname } \newcommand {\dolistloop }[0]{\forlistloop \do } \newcommand {\dolistcsloop }[0]{\forlistcsloop \do } \newcommand {\AfterPreamble }[0]{\AtBeginDocument } \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\RR }[0]{\mathbb R} \newcommand {\R }[0]{\mathbb R} \newcommand {\C }[0]{\mathbb C} \newcommand {\N }[0]{\mathbb N} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\dis }[0]{\displaystyle } \newcommand {\d }[0]{\mathop {}\!d} \newcommand {\l }[0]{\ell } \newcommand {\ddx }[0]{\frac {d}{\d x}} \newcommand {\zeroOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {0}{0}}}} \newcommand {\inftyOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {\infty }{\infty }}}} \newcommand {\zeroOverInfty }[0]{\ensuremath {\boldsymbol {\tfrac {0}{\infty }}}} \newcommand {\zeroTimesInfty }[0]{\ensuremath {\small \boldsymbol {0\cdot \infty }}} \newcommand {\inftyMinusInfty }[0]{\ensuremath {\small \boldsymbol {\infty -\infty }}} \newcommand {\oneToInfty }[0]{\ensuremath {\boldsymbol {1^\infty }}} \newcommand {\zeroToZero }[0]{\ensuremath {\boldsymbol {0^0}}} \newcommand {\inftyToZero }[0]{\ensuremath {\boldsymbol {\infty ^0}}} \newcommand {\numOverZero }[0]{\ensuremath {\boldsymbol {\tfrac {\#}{0}}}} \newcommand {\dfn }[0]{\textbf } \newcommand {\unit }[0]{\mathop {}\!\mathrm } \newcommand {\eval }[1]{ #1 \bigg |} \newcommand {\seq }[1]{\left ( #1 \right )} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\iff }[0]{\Leftrightarrow } \DeclareMathOperator {\arccot }{arccot} \DeclareMathOperator {\arcsec }{arcsec} \DeclareMathOperator {\arccsc }{arccsc} \DeclareMathOperator {\si }{Si} \DeclareMathOperator {\proj }{proj} \DeclareMathOperator {\scal }{scal} \DeclareMathOperator {\cis }{cis} \DeclareMathOperator {\Arg }{Arg} \DeclareMathOperator {\Rep }{Re} \DeclareMathOperator {\Imp }{Im} \DeclareMathOperator {\sech }{sech} \DeclareMathOperator {\csch }{csch} \DeclareMathOperator {\Log }{Log} \newcommand {\tightoverset }[2]{\mathop {#2}\limits ^{\vbox to -.5ex{\kern -0.75ex\hbox {$#1$}\vss }}} \newcommand {\arrowvec }[0]{\overrightarrow } \newcommand {\vec }[0]{\mathbf } \newcommand {\veci }[0]{{\boldsymbol {\hat {\imath }}}} \newcommand {\vecj }[0]{{\boldsymbol {\hat {\jmath }}}} \newcommand {\veck }[0]{{\boldsymbol {\hat {k}}}} \newcommand {\vecl }[0]{\boldsymbol {\l }} \newcommand {\utan }[0]{\vec {\hat {t}}} \newcommand {\unormal }[0]{\vec {\hat {n}}} \newcommand {\ubinormal }[0]{\vec {\hat {b}}} \newcommand {\dotp }[0]{\bullet } \newcommand {\cross }[0]{\boldsymbol \times } \newcommand {\grad }[0]{\boldsymbol \nabla } \newcommand {\divergence }[0]{\grad \dotp } \newcommand {\curl }[0]{\grad \cross } \newcommand {\vector }[1]{\left \langle #1\right \rangle } \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

We explore the Binomial Theorem.

Binomial Theorem Let $n$ be a non-negative integer and $x, y \in \mathbb {R}$ . Then $(x+y)^n = \sum _{k=0}^n \binom {n}{k} x^ky^{n-k}$

Proof: Let $0 \leq k \leq n$ and consider the coefficient of the term $x^ky^{n-k}$ in the expansion of $(x+y)^n$ . $\underbrace {(x+y) (x+y) (x+y) \cdots (x+y) (x+y)}_{\mbox {n factors}}$ According to the distributive property, both terms in each factor multiply both of the terms in each of the other factors. Hence, the coefficient sought is the number of ways to select $k$ of the $x's$ (and hence simultaneously $n-k$ of the $y's$ ) from the $n$ factors. Since the order of the selection is not important, we seek the number of combinations of $n$ objects, taken $k$ at a time, i.e., $C(n, k)$ . $\blacksquare$

The numbers $C(n,k) = \binom {n}{k}$ are sometimes referred to as binomial coefficients.

Pascal’s Triangle contains the binomial coefficients arranged in a triangular array.

$\mbox {Pascal's Triangle}$ $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$ From Pascal’s Identity, $\binom {n}{k} + \binom {n}{k+1} = \binom {n+1}{k+1},$ each number in the interior of the triangle is the sum of the two numbers above it. Try to write the next 3 rows of Pascal’s Triangle for yourself. Pascal’s Triangle can be used to expand a binomial expression.

example 1 Use Pascal’s Triangle to expand $(x+y)^4$ .
The fourth row of the triangle gives the coefficients: $(x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$

(problem 1) Use Pascal’s triangle to expand $(x+y)^6$ and $(a+b)^8$

example 2 Find the coefficient of $x^2y^3$ in the expansion of $(3x-2y)^5$ .
The term involving $x^2y^3$ will have the form $\binom {5}{2}(3x)^2(-2y)^3$ Thus, the coefficient of $x^2y^3$ is $\binom {5}{2}\cdot 3^2 \cdot (-2)^3 = 10\cdot 9 \cdot (-8) = -720$

(problem 2) a) Find the coefficient of $x^2y^3$ in the expansion of $(x-y)^5 \quad \answer {-10}$
b) Find the coefficient of $x^3y^3$ in the expansion of $(2x-3y)^6 \quad \answer {-4320}$
c) Find the coefficient of $x^4y^3$ in the expansion of $(2x-y)^7 \quad \answer {560}$

example 3 Use the Binomial Theorem to establish the identity: $\sum _{k=0}^n \binom {n}{k} = 2^n$

If we substitute $x=1$ and $y=1$ , the Binomial Theorem gives, $(1+1)^n = \sum _{k=0}^n \binom {n}{k} 1^k 1^{n-k}$ which simplifies to the identity in question.

(problem 3a) Use the Binomial Theorem to establish the identity: $\sum _{k=0}^n (-1)^k\binom {n}{k} = 0$

Substitute appropriate values for $x$ and $y$ in the Binomial Theorem.

(problem 3b) Use the Binomial Theorem to establish the identity: $\sum _{k=0}^n (-1)^k\binom {n}{k}2^{n-k} = 1$

Substitute appropriate values for $x$ and $y$ in the Binomial Theorem.

example 4 Use the Binomial Theorem to compute: $\sum _{k=0}^n (-1)^k\binom {n}{k}4^k$

If we substitute $x=-4$ and $y=1$ , the Binomial Theorem gives, $(-4+1)^n = \sum _{k=0}^n \binom {n}{k} (-4)^k 1^{n-k}$ Rewriting $(-4)^k$ as $(-1)^k \cdot 4^k$ we arrive at $\sum _{k=0}^n (-1)^k\binom {n}{k}4^k = (-3)^n$

(problem 4a) Use the Binomial Theorem to compute: $\sum _{k=0}^n (-1)^k\binom {n}{k}10^k = \answer {(-9)^n}$

Substitute appropriate values for $x$ and $y$ in the Binomial Theorem.

(problem 4b) Use the Binomial Theorem to compute: $\sum _{k=0}^n \left (-\frac 12\right )^k\binom {n}{k} = \answer {(1/2)^n}$

Substitute appropriate values for $x$ and $y$ in the Binomial Theorem.

example 5 Use the Binomial Theorem to evaluate the sum: $\sum _{k=1}^{n} k\binom {n}{k}$ Consider the function $f(x) = (1+x)^n =\sum _{k=0}^n \binom {n}{k} x^k$

and it’s derivative, $f'(x) = n(1+x)^{n-1}= \sum _{k=0}^n k\binom {n}{k} x^{k-1} = \sum _{k=1}^n k\binom {n}{k} x^{k-1}$ Evaluating $f'(1)$ we have $f'(1) = n2^{n-1} = \sum _{k=1}^n k\binom {n}{k} 1^{k-1} = \sum _{k=1}^n k\binom {n}{k}$ Hence, $\sum _{k=1}^n k\binom {n}{k} = n2^{n-1}$

(problem 5) Use the Binomial Theorem to evaluate the sum: $\sum _{k=1}^n k^2 \binom {n}{k} = \answer {(n^+n)2^{n-2}}$

Consider the second derivative of the function $f(x) = (1+x)^n$ and the result of the preceding example.

Alternatively, compute the derivative of $xf'(x)$ where $f(x)$ is as in the preceding example.

We close this section by examining the function $f(x) = (1+x)^n$ . According to the Binomial Theorem, $f(x) = \sum _{k=0}^n \binom {n}{k} x^k = \binom {n}{0} + \binom {n}{1}x + \binom {n}{2}x^2 + \cdots + \binom {n}{n-1}x^{n-1} + \binom {n}{n}x^n$ Observe that the coefficient of $x^k$ in $f(x)$ is the binomial coefficient $\dis \binom {n}{k}$ . Polynomial functions (and power series functions) whose coefficients contain combinatorial information are known as generating functions. We will study generating functions in chapter 4.