# Applied Combinatorics

## Section8.4An 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.
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.
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*}
\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{.}$$