The Egorychev method is a collection of techniques introduced by
Georgy Egorychev
Georgy Petrovich Egorychev (or Yegorychev) (Георгий Петрович Егорычев, born 1938) is a Russian mathematician, known for the Egorychev method.
Biography
He graduated in mathematics from Ural State University and in 1960 be ...
for finding
identities among sums of
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
s,
Stirling numbers
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book ''Methodus differentialis'' (1730). They were rediscove ...
,
Bernoulli numbers
In mathematics, the Bernoulli numbers are a sequence of rational numbers which occur frequently in analysis. The Bernoulli numbers appear in (and can be defined by) the Taylor series expansions of the tangent and hyperbolic tangent functions, ...
,
Harmonic numbers
In mathematics, the -th harmonic number is the sum of the reciprocals of the first natural numbers:
H_n= 1+\frac+\frac+\cdots+\frac =\sum_^n \frac.
Starting from , the sequence of harmonic numbers begins:
1, \frac, \frac, \frac, \frac, \do ...
,
Catalan numbers
In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
and other combinatorial numbers. The method relies on two observations. First, many identities can be proved by extracting coefficients of
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary seri ...
s. Second, many generating functions are convergent power series, and coefficient extraction can be done using the
Cauchy residue theorem
In complex analysis, the residue theorem, sometimes called Cauchy's residue theorem, is a powerful tool to evaluate line integrals of analytic functions over closed curves; it can often be used to compute real integrals and infinite series as well ...
(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
In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...
, and the sum of the residues of a rational function is zero, yielding a new expression for the original sum. The
residue at infinity In complex analysis, a branch of mathematics, the residue at infinity is a Residue (complex analysis), residue of a holomorphic function on an Annulus (mathematics), annulus having an infinite external radius. The ''infinity'' \infty is a point add ...
is particularly important in these considerations.
Some of the integrals employed by the Egorychev method are:
* First binomial coefficient integral
::
where
* Second binomial coefficient integral
::
where
*
Exponentiation integral
::
where
*
Iverson bracket
In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that generalises the Kronecker delta, which is the Iverson bracket of the statement . It maps any statement to a function of the free variables in that statement. ...
::
where
*
Stirling number of the first kind
::
where
*
Stirling number of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) or \textstyle \lef ...
::
where
Example I
Suppose we seek to evaluate
:
which is claimed to be :
Introduce :
and :
This yields for the sum :
This is
:
Extracting the residue at
we get
:
thus proving the claim.
Example II
Suppose we seek to evaluate
Introduce
:
Observe that this is zero when
so we may extend
to
infinity to obtain for the sum
:
Now put
so that (observe that with
the image of
with
small is another closed circle-like contour which makes one turn and which we may certainly deform to obtain another circle
)
:
and furthermore
:
to get for the integral
:
This evaluates by inspection to (use the
Newton binomial
In mathematics, the binomial series is a generalization of the polynomial that comes from a binomial formula expression like (1+x)^n for a nonnegative integer n. Specifically, the binomial series is the Taylor series for the function f(x)=(1+x ...
)
:
Here the mapping from
to
determines
the choice of square root. For the conditions on
and
we have that for the series to converge we
require
or
or
The closest that the image
contour of
comes to the origin is
so we choose
for example
This also ensures that
so
does not intersect the branch
cut
(and is contained in the image of
). For example
and
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
:
with
and
We
get
and find
:
with
the inverse of
.
This becomes
:
or alternatively
:
Observe that
so this is
:
and the rest of the computation continues as before.
External links
Computational examples of using the Egorychev method to evaluate sums involving types of combinatorial numbers
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 , ref= Ego84 , url=https://books.google.com/books/about/Integral_Representation_and_the_Computat.html?id=QTfxn_gEbVYC
Factorial and binomial topics
*