In the book "Mathematics for the Analysis of Algorithms" by Daniel H. Greene and Donald E. Knuth, they cover the example, $$S=\sum_{k}\binom{m}{k}\left(-\frac{1}{2}\right)^k\binom{2k}{k}$$ After expressing portions of the sum with generating functions, they make the transformation,
$$\begin{align*} S &= \left(-\frac{1}{2}\right)^m\sum_k[x^k] (1-2x)^m [y^{m-k}] (1+y)^{2m-2k} \\ &= \left(-\frac{1}{2}\right)^m [y^m] (1+y)^{2m}\sum_k [x^k] (1-2x)^m \left(\frac{y}{(1+y)^2}\right)^k\end{align*}$$
after noticing that $[y^{m-k}]=[y^m]y^k$, where $[x^n]f(x)$ is the coefficient of $x^n$ in $f(x)$. Then, the solution follows immediately as, $$\sum_{k}[x^k]f(x)g(y)^k=f(g(y))$$ when $f$ is analytic. $$S = (-2)^{-m} [y^m] (1+y)^{2m}\left(1-\frac{2y}{(1+y)^2}\right)^m=(-2)^{-m} [y^m] (1+y^2)^m$$ $$S= \begin{cases} 2^{-m}\binom{m}{m/2},& m\ \text{even} \\ 0,& m\ \text{odd}. \end{cases}$$
I do not understand the formula, $$\sum_{k}[x^k]f(x)g(y)^k=f(g(y))$$ and can't seem to find any explanation for it in the book. Can someone explain? Thanks in advance.
If $f$ is analytic in a neighbourhood of zero with: $$f(x)=\sum_{n\in\Bbb N_0}a_nx^n$$ And $g(y)$ is sufficiently close to zero then: $$\sum_{k\in\Bbb N_0}[x^k]f(x)g(y)^k=\sum_{k\in\Bbb N_0}a_kg(y)^k=f(g(y))$$
Follows quickly. Here: $$f(x):=(1-2x)^m$$Is analytic with infinite radius of convergence (if $m\ge0$ is an integer) so $g(y)=\frac{y}{(1+y)^2}$ is always sufficiently close to zero as to make $\sum_k a_kg(y)^k$ make sense.