Egorychev method

Suppose we seek to evaluate

${\displaystyle S_{j}(n)=\sum _{k=0}^{n}(-1)^{k}{n \choose k}{n+k \choose k}{k \choose j}}$ 

which is claimed to be :${\displaystyle (-1)^{n}{n \choose j}{n+j \choose j}.}$ 

Introduce :${\displaystyle {n+k \choose k}={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n+k}}{z^{k+1}}}\;dz}$ 

and :${\displaystyle {k \choose j}={\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {(1+w)^{k}}{w^{j+1}}}\;dw.}$ 

This yields for the sum :

${\displaystyle {\begin{aligned}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z}}{\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{j+1}}}\sum _{k=0}^{n}(-1)^{k}{n \choose k}{\frac {(1+z)^{k}(1+w)^{k}}{z^{k}}}\;dw\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z}}{\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{j+1}}}\left(1-{\frac {(1+w)(1+z)}{z}}\right)^{n}\;dw\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{j+1}}}(-1-w-wz)^{n}\;dw\;dz\\[6pt]={}&{\frac {(-1)^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{j+1}}}(1+w+wz)^{n}\;dw\;dz.\end{aligned}}}$ 

This is

${\displaystyle {\frac {(-1)^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{j+1}}}\sum _{q=0}^{n}{n \choose q}w^{q}(1+z)^{q}\;dw\;dz.}$ 

Extracting the residue at ${\displaystyle w=0}$  we get

${\displaystyle {\begin{aligned}&{\frac {(-1)^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{n \choose j}(1+z)^{j}\;dz\\[6pt]={}&{n \choose j}{\frac {(-1)^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n+j}}{z^{n+1}}}\;dz\\[6pt]={}&(-1)^{n}{n \choose j}{n+j \choose n}\end{aligned}}}$ 

thus proving the claim.

Suppose we seek to evaluate ${\displaystyle \sum _{k=1}^{n}k{2n \choose n+k}.}$ 

Introduce

${\displaystyle {2n \choose n+k}={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {1}{z^{n-k+1}}}{\frac {1}{(1-z)^{n+k+1}}}\;dz.}$ 

Observe that this is zero when ${\displaystyle k>n}$  so we may extend ${\displaystyle k}$  to infinity to obtain for the sum

${\displaystyle {\begin{aligned}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {1}{z^{n+1}}}{\frac {1}{(1-z)^{n+1}}}\sum _{k\geq 1}k{\frac {z^{k}}{(1-z)^{k}}}\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {1}{z^{n+1}}}{\frac {1}{(1-z)^{n+1}}}{\frac {z/(1-z)}{(1-z/(1-z))^{2}}}\;dz\\[6pt]={}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {1}{z^{n}}}{\frac {1}{(1-z)^{n}}}{\frac {1}{(1-2z)^{2}}}\;dz.\end{aligned}}}$ 

Now put ${\displaystyle z(1-z)=w}$  so that (observe that with ${\displaystyle w=z+\cdots }$  the image of ${\displaystyle |z|=\varepsilon }$  with ${\displaystyle \varepsilon }$  small is another closed circle-like contour which makes one turn and which we may certainly deform to obtain another circle ${\displaystyle |w|=\gamma }$ )

${\displaystyle z={\frac {1-{\sqrt {1-4w}}}{2}}\quad {\text{and}}\quad (1-2z)^{2}=1-4w}$ 

and furthermore

${\displaystyle dz=-{\frac {1}{2}}\times {\frac {1}{2}}\times (-4)\times (1-4w)^{-1/2}\;dw=(1-4w)^{-1/2}\;dw}$ 

to get for the integral

${\displaystyle {\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{n}}}{\frac {1}{1-4w}}(1-4w)^{-1/2}\;dw={\frac {1}{2\pi i}}\int _{|w|=\gamma }{\frac {1}{w^{n}}}{\frac {1}{(1-4w)^{3/2}}}\;dw.}$ 

This evaluates by inspection to (use the Newton binomial)

${\displaystyle {\begin{aligned}&4^{n-1}{n-1+1/2 \choose n-1}=4^{n-1}{n-1/2 \choose n-1}={\frac {4^{n-1}}{(n-1)!}}\prod _{q=0}^{n-2}(n-1/2-q)\\={}&{\frac {2^{n-1}}{(n-1)!}}\prod _{q=0}^{n-2}(2n-2q-1)={\frac {2^{n-1}}{(n-1)!}}{\frac {(2n-1)!}{2^{n-1}(n-1)!}}\\[6pt]={}&{\frac {n^{2}}{2n}}{2n \choose n}={\frac {1}{2}}n{2n \choose n}.\end{aligned}}}$ 

Here the mapping from ${\displaystyle z=0}$  to ${\displaystyle w=0}$  determines the choice of square root. For the conditions on ${\displaystyle \epsilon }$  and ${\displaystyle \gamma }$  we have that for the series to converge we require ${\displaystyle |z/(1-z)|<1}$  or ${\displaystyle \epsilon /(1-\epsilon )<1}$  or ${\displaystyle \epsilon <1/2.}$  The closest that the image contour of ${\displaystyle |z|=\epsilon }$  comes to the origin is ${\displaystyle \epsilon -\epsilon ^{2}}$  so we choose ${\displaystyle \gamma <\epsilon -\epsilon ^{2}}$  for example ${\displaystyle \gamma =\epsilon ^{2}-\epsilon ^{3}.}$  This also ensures that ${\displaystyle \gamma <1/4}$  so ${\displaystyle |w|=\gamma }$  does not intersect the branch cut ${\displaystyle [1/4,\infty )}$  (and is contained in the image of ${\displaystyle |z|=\epsilon }$ ). For example ${\displaystyle \epsilon =1/3}$  and ${\displaystyle \gamma =2/27}$  will work.

This example also yields to simpler methods but was included here to demonstrate the effect of substituting into the variable of integration.

We may use the change of variables rule 1.8 (5) from the Egorychev text (page 16) on the integral

${\displaystyle {\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {1}{z^{n}}}{\frac {1}{(1-z)^{n}}}{\frac {1}{(1-2z)^{2}}}\;dz={\underset {z}{\mathrm {res} }}{\frac {1}{z^{n}}}{\frac {1}{(1-z)^{n}}}{\frac {1}{(1-2z)^{2}}}}$ 

with ${\displaystyle A(z)={\frac {z}{(1-2z)^{2}}}}$  and ${\displaystyle f(z)={\frac {1}{1-z}}.}$  We get ${\displaystyle h(z)=z(1-z)}$  and find

${\displaystyle {\underset {w}{\mathrm {res} }}{\frac {1}{w^{n+1}}}\left.\left[{\frac {A(z)}{f(z)h'(z)}}\right]\right|_{z=g(w).}}$ 

with ${\displaystyle g}$  the inverse of ${\displaystyle h}$ .

This becomes

${\displaystyle {\underset {w}{\mathrm {res} }}{\frac {1}{w^{n+1}}}\left.\left[{\frac {z/(1-2z)^{2}}{(1-2z)/(1-z)}}\right]\right|_{z=g(w)}}$ 

or alternatively

${\displaystyle {\underset {w}{\mathrm {res} }}{\frac {1}{w^{n+1}}}\left.\left[{\frac {z(1-z)}{(1-2z)^{3}}}\right]\right|_{z=g(w)}={\underset {w}{\mathrm {res} }}{\frac {1}{w^{n}}}\left.\left[{\frac {1}{(1-2z)^{3}}}\right]\right|_{z=g(w).}}$ 

Observe that ${\displaystyle (1-2z)^{2}=1-4z+4z^{2}=1-4z(1-z)=1-4w}$  so this is

${\displaystyle {\underset {w}{\mathrm {res} }}{\frac {1}{w^{n}}}{\frac {1}{(1-4w)^{3/2}}}}$ 

and the rest of the computation continues as before.

• Hosam Mahmoud, 2022, History and examples of Egorychev method
• Marko Riedel, 2024, Computational examples of using the Egorychev method to evaluate sums involving types of combinatorial numbers (parts 1 and 2, formal power series and residue operators
• Marko Riedel, 2024, Computational examples of using the Egorychev method to evaluate sums involving types of combinatorial numbers (part 3, complex variables

• Egorychev, G. P. (1984). Integral representation and the Computation of Combinatorial sums. American Mathematical Society. ISBN 9780821898093.
• Riedel, Marko; Mahmoud, Hosam (2023). "Egorychev Method: A Hidden Treasure". La Matematica. 2 (4): 893–933. doi:10.1007/s44007-023-00065-y.