TAOCP 1.2.9 Exercise 25

Section 1.2.9: Generating Functions

Exercise 25. [M23] Evaluate the sum

$$ \sum_k \binom{n}{k} 2^{n-2k}(-2)^k $$

by simplifying the equivalent formula

$$ \sum_k w^k^n z^{n-k}^{2n-2k}. $$

Verified: no
Solve time: 4m29s

---

Solution

Let

$$ S=\sum_k w^k^n,z^{,n-k}^{2n-2k}. $$

We simplify this coefficient-extraction formula directly.

First observe that

$$ z^{,n-k}^{2n-2k} =z^{,n-k}^{2(n-k)} =\binom{2(n-k)}{,n-k,}. $$

Hence

$$ S=\sum_k \binom{n}{k}(-2)^k \binom{2(n-k)}{,n-k,}, $$

since

$$ w^k^n=\binom{n}{k}(-2)^k. $$

To evaluate this sum, convert it back into a single coefficient.

Using

$$ z^{,n-k}^{2n-2k} =[z^n],z^k(1+z)^{2n-2k}, $$

we obtain

$$ S =\sum_k w^k^n, [z^n],z^k(1+z)^{2n-2k}. $$

Since coefficient extraction is linear,

$$ S =[z^n]\sum_k w^k^n z^k(1+z)^{2n-2k}. $$

Factor out $(1+z)^{2n}$:

$$ S =z^n^{2n} \sum_k w^k^n \left(\frac{z}{(1+z)^2}\right)^k . $$

Now use the generating-function identity

$$ \sum_k [w^k]F(w),x^k = F(x). $$

With $F(w)=(1-2w)^n$ and $x=\dfrac{z}{(1+z)^2}$, this gives

$$ S =z^n^{2n} \left(1-\frac{2z}{(1+z)^2}\right)^n. $$

Simplifying,

$$ 1-\frac{2z}{(1+z)^2} =\frac{(1+z)^2-2z}{(1+z)^2} =\frac{1+z^2}{(1+z)^2}. $$

Therefore

$$ S =z^n^{2n} \left(\frac{1+z^2}{(1+z)^2}\right)^n =z^n^n. $$

But

$$ (1+z^2)^n=\sum_{j=0}^{n}\binom{n}{j}z^{2j}, $$

which contains only even powers of $z$. Hence

$$ z^n^n= \begin{cases} \binom{n}{n/2}, & n \text{ even},\[6pt] 0, & n \text{ odd}. \end{cases} $$

Consequently,

$$ \boxed{ \sum_k \binom{n}{k}(-2)^k \binom{2(n-k)}{,n-k,} = z^n^n = \begin{cases} \binom{n}{n/2}, & n \text{ even},\[6pt] 0, & n \text{ odd}. \end{cases} } $$

Thus the given coefficient-extraction formula simplifies to $z^n^n$, and its value is the central binomial coefficient $\binom{n}{n/2}$ when $n$ is even and $0$ when $n$ is odd. ∎