The Egorychev method is a collection of techniques for finding identities among sums of binomial coefficients. The method relies on two observations. First, many identities can be proved by extracting coefficients of generating functions. Second, many generating functions are convergent power series, and coefficient extraction can be done using the Cauchy residue theorem (usually this is done by integrating over a small circular contour enclosing the origin). The sought-for identity can now be found using manipulations of integrals. Some of these manipulations are not clear from the generating function perspective. For instance, the integrand is usually a rational function, and the sum of the residues of a rational function is zero, yielding a new expression for the original sum. The residue at infinity is particularly important in these considerations.
The main integrals employed by the Egorychev method are:
First binomial coefficient integral
\( {\displaystyle {n \choose k}={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{k+1}}}\;dz.} \)
Second binomial coefficient integral
\( {\displaystyle {n \choose k}={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {1}{(1-z)^{k+1}z^{n-k+1}}}\;dz.} \)
Exponentiation integral
\( {\displaystyle n^{k}={\frac {k!}{2\pi i}}\int _{|z|=\varepsilon }{\frac {\exp(nz)}{z^{k+1}}}\;dz:} \)
Iverson bracket
\( {\displaystyle [[0\leq k\leq n]]={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {z^{k}}{z^{n+1}}}{\frac {1}{1-z}}\;dz.} \)
Example I
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|=\varepsilon }{\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|=\varepsilon }{\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|=\varepsilon }{\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|=\varepsilon }{\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|=\varepsilon }{\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|=\varepsilon }{\frac {1}{w^{j+1}}}\sum _{q=0}^{n}{n \choose q}w^{q}(1+z)^{q}\;dw\;dz.} \)
Extracting the residue at w = 0 {\displaystyle w=0} 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.
Example II
Suppose we seek to evaluate \( {\displaystyle \sum _{k=0}^{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 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 0}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 the image of \( {\displaystyle |z|=\varepsilon } \) with \( \varepsilon \) small is another closed circle-like contour 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 z=0 to w=0 determines the choice of square root. This example also yields to simpler methods but was included here to demonstrate the effect of substituting into the variable of integration.
External links
Computational examples of using the Egorychev method to evaluate sums involving binomial coefficients
References
Egorychev, G. P. (1984). Integral representation and the Computation of Combinatorial sums. American Mathematical Society.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
