annihilated coefficient extractor (ACE) Please, someone can explain me how works the annihilated coefficient extractor
technique (ACE). I have seen some examples but i can't understand.
Is there some text to read about this specific argument?
Thank in advance.
 A: We start with some general information:

*

*The coefficient of operator is thoroughly described in Bracket notation for the ‘coefficient of’ operator by  D.E. Knuth.


*There are instructive examples in section 5.4 Generating Functions in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik.


*A lot of nice material can be found in Generatingfunctionology by H.S. Wilf which is a great starter for problems of this kind.

The ACE also called substitution rule is demonstrated in the example below. The key is the representation mentioned in (3).
We obtain
\begin{align*}
\color{blue}{\sum_{j=0}^k}&\color{blue}{\binom{j+r-1}{j}\binom{k-j+s-1}{k-j}}\\
&=\sum_{j=0}^k\binom{-r}{j}(-1)^j\binom{-s}{k-j}(-1)^{k-j}\\
&=(-1)^k\sum_{j=0}^\infty[z^j](1+z)^{-r}[u^{k-j}](1+u)^{-s}\tag{1}\\
&=(-1)^k[u^k](1+u)^{-s}\sum_{j=0}^\infty u^j[z^j](1+z)^{-r}\tag{2}\\
&=(-1)^k[u^k](1+u)^{-s}(1+u)^{-r}\tag{3}\\
&=(-1)^k[u^k](1+u)^{-r-s}\\
&=(-1)^k\binom{-r-s}{k}\\
&\color{blue}{=\binom{k+r+s-1}{k}}
\end{align*}
and the Chu-Vandermonde identity follows.

Comment:

*

*In (1) we apply the coefficient of operator twice and set the upper limit of the series to $\infty$ without changing anything since we are adding zeros only.


*In (2) we use the linearity of the coefficient of operator and apply the rule $[z^{p}]z^qA(z)=[z^{p-q}]A(z)$.


*In (3) we apply the substitution rule of the coefficient of operator with $u=z$
\begin{align*}
A(u)=\sum_{j=0}^\infty a_j u^j=\sum_{j=0}^\infty u^j [z^j]A(z)
\end{align*}

Here are some more examples using the substitution rule:

*

*Ex. 1: Is there an explicit expression for $\sum_{j= k+1}^{2n}{j\choose k}{n\choose j-n}$?.

*Ex. 2: A strange combinatorial identity: $\sum\limits_{j=1}^k(-1)^{k-j}j^k\binom{k}{j}=k!$.

*Ex. 3: Sum Involving Bernoulli Numbers : $\sum_{r=1}^n \binom{2n}{2r-1}\frac{B_{2r}}{r}=\frac{2n-1}{2n+1}$ by Marko Riedel


Note: The substitution rule stated as formula 1.6 and a lot of other powerful techniques were introduced by G.P. Egorychev in Integral Representation and the Computation of Combinatorial Sums.
