Encyclopedia

Egorychev method

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated August 21, 2026

The Egorychev method is a collection of techniques introduced by Georgy Egorychev for finding identities among sums of binomial coefficients, Stirling numbers, Bernoulli numbers, Harmonic numbers, Catalan numbers and other combinatorial numbers. 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. Should a series appear during summation that is not finite the contours must be chosen such as to make the series converge. Some of the integrals employed by the Egorychev method are:

First binomial coefficient integral

${n \choose k}={\underset {z}{\mathrm {res} }}\;{\frac {(1+z)^{n}}{z^{k+1}}}={\frac {1}{2\pi i}}\int _{|z|=\rho }{\frac {(1+z)^{n}}{z^{k+1}}}\;dz$

where $0<\rho <\infty$

Second binomial coefficient integral

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

where $0<\rho <1$

Exponentiation integral

$n^{k}=k!\;{\underset {z}{\mathrm {res} }}\;{\frac {\exp(nz)}{z^{k+1}}}={\frac {k!}{2\pi i}}\int _{|z|=\rho }{\frac {\exp(nz)}{z^{k+1}}}\;dz:$

where $0<\rho <\infty$

Iverson bracket

$[[k\leq n]]={\underset {z}{\mathrm {res} }}\;{\frac {z^{k}}{z^{n+1}}}{\frac {1}{1-z}}={\frac {1}{2\pi i}}\int _{|z|=\rho }{\frac {z^{k}}{z^{n+1}}}{\frac {1}{1-z}}\;dz$

where $0<\rho <1$

Stirling number of the first kind

$\left[{n \atop k}\right]={\frac {n!}{k!}}\;{\underset {z}{\mathrm {res} }}\;{\frac {1}{z^{n+1}}}\left(\log {\frac {1}{1-z}}\right)^{k}={\frac {n!}{k!}}{\frac {1}{2\pi i}}\int _{|z|=\rho }{\frac {1}{z^{n+1}}}\left(\log {\frac {1}{1-z}}\right)^{k}\;dz$

where $0<\rho <1$

Stirling number of the second kind

$\left\{{n \atop k}\right\}={\frac {n!}{k!}}\;{\underset {z}{\mathrm {res} }}\;{\frac {(\exp(z)-1)^{k}}{z^{n+1}}}={\frac {n!}{k!}}{\frac {1}{2\pi i}}\int _{|z|=\rho }{\frac {(\exp(z)-1)^{k}}{z^{n+1}}}\;dz$

where $0<\rho <\infty .$

01Example I

Suppose we seek to evaluate

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

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

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

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

This yields for the sum :

${\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

${\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 $w=0$ we get

${\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. There are no convergence issues here as the sums involved are finite and with $n+k$ and $k$ not being negative we can choose any non-zero finite value for $\varepsilon$ and $\gamma$ .

02Example II

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

Introduce

${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 $k>n$ so we may extend $k$ to infinity to obtain for the sum

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

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

and furthermore

$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

${\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)

${\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. For the conditions on $\epsilon$ and $\gamma$ we have that for the series to converge we require $|z/(1-z)|<1$ or $\epsilon /(1-\epsilon )<1$ or $\epsilon <1/2.$ The closest that the image contour of $|z|=\epsilon$ comes to the origin is $\epsilon -\epsilon ^{2}$ so we choose $\gamma <\epsilon -\epsilon ^{2}$ for example $\gamma =\epsilon ^{2}-\epsilon ^{3}.$ This also ensures that $\gamma <1/4$ so $|w|=\gamma$ does not intersect the branch cut $[1/4,\infty )$ (and is contained in the image of $|z|=\epsilon$ ). For example $\epsilon =1/3$ and $\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.

Computation using formal power series

We may use the change of variables rule 1.8 (5) from the Egorychev text (page 16) on the integral (recall that by the convergence requirement the poles at $z=1$ and $z=1/2$ are not inside the contour since $\varepsilon <1/2$ ):

${\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 $A(z)={\frac {z}{(1-2z)^{2}}}$ and $f(z)={\frac {1}{1-z}}.$ We get $h(z)=z(1-z)$ and find

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

with $g$ the inverse of $h$ .

This becomes

${\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

${\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 $(1-2z)^{2}=1-4z+4z^{2}=1-4z(1-z)=1-4w$ so this is

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

and the rest of the computation continues as before.

Watch videos about Egorychev methodExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Egorychev method”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.