Skip to main content Contents Index Prev Up Next You! \(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 8.4 An Application of the Binomial Theorem
In this section, we see how
Newton’s Binomial Theorem can be used to derive another useful identity. We begin by establishing a different recursive formula for
\(P(p,k)\) than was used in our definition of it.
Lemma 8.11 .
For each \(k\ge0\text{,}\) \(P(p,k+1)=P(p,k)(p-k)\text{.}\)
Proof.
When \(k=0\text{,}\) both sides evaluate to \(p\text{.}\) Now assume validity when \(k=m\) for some non-negative integer \(m\text{.}\) Then
\begin{align*}
P(p,m+2)\amp =pP(p-1,m+1)\\
\amp = p[P(p-1,m)(p-1-m)]\\
\amp =[pP(p-1,m)](p-1-m)\\
\amp =P(p,m+1)[p-(m+1)].
\end{align*}
Our goal in this section will be to invoke
Newton’s Binomial Theorem with the exponent
\(p=-1/2\text{.}\) To do so in a meaningful manner, we need a simplified expression for
\(C(-1/2,k)\text{,}\) which the next lemma provides.
Lemma 8.12 .
For each \(k\ge0\text{,}\) \(\displaystyle\binom{-1/2}{k}=(-1)^k\frac{\binom{2k}{k}}{2^{2k}}\text{.}\)
Proof.
We proceed by induction on \(k\text{.}\) Both sides reduce to \(1\) when \(k=0\text{.}\) Now assume validity when \(k=m\) for some non-negative integer \(m\text{.}\) Then
\begin{align*}
\binom{-1/2}{m+1} \amp =\frac{P(-1/2,m+1)}{(m+1)!}
=\frac{P(-1/2,m)(-1/2-m)}{(m+1)m!}\\
\amp =\frac{-1/2-m}{m+1}\binom{-1/2}{m}
=(-1)\frac{2m+1}{2(m+1)}(-1)^m\frac{\binom{2m}{m}}{2^{2m}}\\
\amp =(-1)^{m+1}\frac{1}{2^{2m}}
\frac{(2m+2)(2m+1)}{(2m+2)2(m+1)}\binom{2m}{m}=
(-1)^{m+1}\frac{\binom{2m+2}{m+2}}{2^{2m+2}}.
\end{align*}
Theorem 8.13 .
The function \(f(x)=(1-4x)^{-1/2}\) is the generating function of the sequence \(\{\binom{2n}{n}:n\ge0\}\text{.}\)
Proof.
\begin{align*}
(1-4x)^{-1/2}\amp =\sum_{n=0}^\infty\binom{-1/2}{n}(-4x)^n\\
\amp =\sum_{n=0}^\infty(-1)^n2^{2n}\binom{-1/2}{n}x^n\\
\amp =\sum_{n=0}^\infty \binom{2n}{n}x^n.
\end{align*}
We will return to this generating function in
Section 9.7 , where it will play a role in a seemingly new counting problem that actually is a problem we’ve already studied in disguise.
Now recalling
Proposition 8.3 about the coefficients in the product of two generating functions, we are able to deduce the following corollary of
Theorem 8.13 by squaring the function
\(f(x) = (1-4x)^{-1/2}\text{.}\)
Corollary 8.14 .
For all \(n\ge0\text{,}\)
\begin{equation*}
2^{2n}=\sum_{k=0}^n\binom{2k}{k}\binom{2n-2k}{n-k}.
\end{equation*}
