# Egorychev method

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Egorychev_method
> Markdown URL: https://mediated.wiki/source/Egorychev_method.md
> Source: https://en.wikipedia.org/wiki/Egorychev_method
> Source revision: 1313257644
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

The '''Egorychev method''' is a collection of techniques introduced by [Georgy Egorychev](/source/Georgy_Egorychev) for finding [identities](/source/identity_(mathematics)) among sums of [binomial coefficient](/source/binomial_coefficient)s, [Stirling numbers](/source/Stirling_numbers), [Bernoulli numbers](/source/Bernoulli_numbers), [Harmonic numbers](/source/Harmonic_numbers), [Catalan numbers](/source/Catalan_numbers) and other combinatorial numbers.  The method relies on two observations.  First, many identities can be proved by extracting coefficients of [generating function](/source/generating_function)s.  Second, many generating functions are convergent [power series](/source/power_series), and coefficient extraction can be done using the [Cauchy residue theorem](/source/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](/source/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](/source/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
:: <math>{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</math>
where <math> 0 < \rho < \infty</math>
* Second binomial coefficient integral
:: <math> {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</math>
where <math>0 < \rho < 1</math>
* [Exponentiation integral](/source/Exponential_integral)
:: <math>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:</math>
where <math>0 < \rho < \infty</math>
* [Iverson bracket](/source/Iverson_bracket)
:: <math>[k \le n](/source/k_%5Cle_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</math>
where <math>0 < \rho < 1</math>
* [Stirling number of the first kind](/source/Stirling_number_of_the_first_kind)
:: <math> \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</math>
where <math>0 < \rho < 1</math>
* [Stirling number of the second kind](/source/Stirling_number_of_the_second_kind)
:: <math> \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</math>
where <math>0 < \rho < \infty.</math>

== Example I ==

Suppose we seek to evaluate

:<math>S_j(n) = \sum_{k=0}^n (-1)^k {n\choose k} {n+k\choose k}
{k\choose j}</math>

which is claimed to be :<math>(-1)^n {n\choose j}{n+j\choose
j}.</math>

Introduce :<math>{n+k\choose k} = \frac{1}{2\pi i}
\int_{|z|=\varepsilon} \frac{(1+z)^{n+k}}{z^{k+1}} \; dz</math>

and :<math>{k\choose j} = \frac{1}{2\pi i} \int_{|w|=\gamma}
\frac{(1+w)^k}{w^{j+1}} \; dw.</math>

This yields for the sum : 

<math> \begin{align} & \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{align} </math>

This is 

:<math>\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.</math>

Extracting the residue at <math>w=0</math> we get 
: <math>
\begin{align} & \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{align} </math>

thus proving the claim. There are no convergence issues here as the 
sums involved are finite and with <math>n+k</math> and <math>k</math>
not being negative we can choose any non-zero finite value for 
<math>\varepsilon</math> and <math>\gamma</math>.

== Example II ==

Suppose we seek to evaluate <math>\sum_{k=1}^n k {2n\choose n+k}.</math>

Introduce
:<math>{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.</math>

Observe that this is zero when <math>k> n</math> so we may extend <math>k</math> to
infinity to obtain for the sum

: <math>
\begin{align}
& \frac{1}{2\pi i}
\int_{|z|=\varepsilon}
\frac{1}{z^{n+1}}
\frac{1}{(1-z)^{n+1}}
\sum_{k\ge 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{align}
</math>

Now put <math>z(1-z)=w</math> so that (observe that with <math> w=z+\cdots</math> the image of <math>|z|=\varepsilon</math> with <math>\varepsilon</math> small is another closed circle-like contour which makes one turn and which we may certainly deform to obtain another circle <math>|w|=\gamma</math>)
:<math>z = \frac{1-\sqrt{1-4w}}{2}
\quad\text{and}\quad
(1-2z)^2 = 1-4w</math>

and furthermore
:<math>dz = -\frac{1}{2}
\times \frac{1}{2} \times (-4) \times (1-4w)^{-1/2} \; dw
=  (1-4w)^{-1/2} \; dw</math>

to get for the integral
:<math>\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.</math>

This evaluates by inspection to (use the [Newton binomial](/source/Newton_binomial))

: <math>
\begin{align}
& 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{align}
</math>

Here the mapping from  <math>z=0</math> to <math>w=0</math> determines
the choice of [square root](/source/square_root). For the conditions on <math>\epsilon</math>
and <math>\gamma</math>  we have  that for the  series to  converge we
require  <math>|z/(1-z)|<  1</math> or  <math>\epsilon/(1-\epsilon)  <
1</math> or  <math>\epsilon < 1/2.</math>  The closest that  the image
contour   of  <math>|z|=\epsilon</math>   comes  to   the  origin   is
<math>\epsilon-\epsilon^2</math>   so   we   choose   <math>\gamma   <
\epsilon-\epsilon^2</math>     for      example     <math>\gamma     =
\epsilon^2-\epsilon^3.</math>  This also  ensures that  <math>\gamma <
1/4</math> so  <math>|w|=\gamma</math> does  not intersect  the branch
cut  <math>[1/4,\infty)</math>  (and  is  contained in  the  image  of
<math>|z|=\epsilon</math>).  For  example <math>\epsilon  = 1/3</math>
and <math>\gamma = 2/27</math> 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 <math>z=1</math> and <math>z=1/2</math> are not inside the
contour since <math>\varepsilon < 1/2</math>):

:<math> 
\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}
</math>

with <math>A(z) = \frac{z}{(1-2z)^2}</math> and <math>f(z) = \frac{1}{1-z}.</math> We
get <math>h(z) = z (1-z)</math> and find

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

with <math>g</math> the inverse of <math>h</math>. 

This becomes

:<math>
\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)}
</math>

or alternatively

:<math>\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).}
</math>

Observe that <math>(1-2z)^2 = 1 - 4z + 4z^2 = 1-4z(1-z) = 1-4w</math>
so this is

:<math>\underset{w}{\mathrm{res}} \frac{1}{w^{n}}
\frac{1}{(1-4w)^{3/2}}</math>

and the rest of the computation continues as before.

== External links ==

* [https://combinatorialsums.risc.jku.at/papers/EgorychevHistory.pdf Hosam Mahmoud, 2022, History and examples of Egorychev method]
* [https://combinatorialsums.risc.jku.at/papers/egorychev12.pdf 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]
* [https://combinatorialsums.risc.jku.at/papers/egorychev3.pdf Marko Riedel, 2024, Computational examples of using the Egorychev method to evaluate sums involving types of combinatorial numbers (part 3, complex variables]

== References ==
* {{cite book | last1= Egorychev| first1= G. P. | authorlink=Georgy Petrovich Egorychev  | title= Integral representation and the Computation of Combinatorial sums | publisher= American Mathematical Society| year= 1984 | isbn= 9780821898093 | ref= Ego84 | url=https://books.google.com/books?id=QTfxn_gEbVYC}}
* {{cite journal | last1= Riedel| first1= Marko | last2=Mahmoud | first2=Hosam  | title= Egorychev Method: A Hidden Treasure | journal= La Matematica | date= 2023 | volume= 2 | issue= 4 | pages= 893–933 | doi= 10.1007/s44007-023-00065-y| doi-access= free }}

Category:Factorial and binomial topics
*

---
Adapted from the Wikipedia article [Egorychev method](https://en.wikipedia.org/wiki/Egorychev_method) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Egorychev_method?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.