8.4: An Application of the Binomial Theorem

Last updated
Save as PDF

Page ID: 97910

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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 \geq 0, P(p,k+1)=P(p,k)(p−k)\).

Proof

When \(k=0\), both sides evaluate to \(p\). Now assume validity when \(k=m\) for some non-negative integer \(m\). Then

\(P(p,m+2) = pP(p-1,m+1)\)

\(=p[P(p-1,m)(p-1-m)]\)

\(=[pP(p-1,m)](p-1-m)\)

\(=P(p,m+1)[p-(m+1)]\).

Our goal in this section will be to invoke Newton's Binomial Theorem with the exponent \(p=−1/2\). To do so in a meaningful manner, we need a simplified expression for \(C(−1/2,k)\), which the next lemma provides.

Lemma 8.12.

For each \(k \geq 0\), \(\dbinom{-1/2}{k} = (-1)^k \dfrac{\binom{2k}{k}}{2^{2k}}\).

Proof

We proceed by induction on \(k\). Both sides reduce to 1 when \(k=0\). Now assume validity when \(k=m\) for some non-negative integer \(m\). Then

\(\dbinom{-1/2}{m+1} = \dfrac{P(-1/2,m+1)}{(m+1)!} = \dfrac{P(-1/2,m)(-1/2-m)}{(m+1)m!}\)

\(= \dfrac{-1/2-m}{m+1} \dbinom{-1/2}{m} = (-1)\dfrac{2m+1}{2(m+1)}(-1)^m \dfrac{\binom{2m}{m}}{2^{2m}}\)

\(=(-1)^{m+1} \dfrac{1}{2^{2m}} \dfrac{(2m+2)(2m+1)}{(2m+2)2(m+1)} \dbinom{2m}{m} = (-1)^{m+1} \dfrac{\binom{2m+2}{m+2}}{2^{2m+2}}\)

Theorem 8.13

The function \(f(x)=(1−4x)^{−1/2}\) is the generating function of the sequence \(\{\binom{2n}{n}: n \geq 0\}\).

Proof

By Newton's Binomial Theorem and Lemma 8.12, we know that

\((1-4x)^{-1/2} = \displaystyle \sum_{n=0}^{\infty} \dbinom{-1/2}{n}(-4x)^n\)

\(= \displaystyle \sum_{n=0}^{\infty}(-1)^n 2^{2n} \dbinom{-1/2}{n}x^n\)

\(= \displaystyle \sum_{n=0}^{\infty} \dbinom{2n}{n} x^n\).

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}\).

Corollary 8.14

For all \(n \geq 0\),

\(2^{2n} = \displaystyle \sum_{k=0}^n \dbinom{2k}{k} \dbinom{2n-2k}{n-k}\).