3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Where did you hear about it? Could you reference the source? $\endgroup$ – Yuriy S Feb 4 '18 at 14:47
1
$\begingroup$

We start with some general information:

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_{=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.

$\endgroup$
  • $\begingroup$ @MarkoRiedel: Thanks, Marko. I've added your answer. $\endgroup$ – Markus Scheuer Feb 4 '18 at 23:20
  • $\begingroup$ @MarkoRiedel: If it is ok for you I would like to keep the reference in my answer since it is more visible there. $\endgroup$ – Markus Scheuer Feb 4 '18 at 23:24
  • $\begingroup$ (+1). Very useful bibliography. There are some more examples of the substitution rule being referenced by ACE at the following MSE link. $\endgroup$ – Marko Riedel Feb 4 '18 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.