Método de Egorychev

El método de Egorychev es un conjunto de técnicas introducidas por Georgy Egorychev para hallar identidades entre sumas de coeficientes binomiales , números de Stirling , números de Bernoulli , números armónicos , números de Catalan y otros números combinatorios. El método se basa en dos observaciones. Primero, muchas identidades pueden demostrarse extrayendo los coeficientes de las funciones generadoras . Segundo, muchas funciones generadoras son series de potencias convergentes , y la extracción de coeficientes puede realizarse utilizando el teorema de los residuos de Cauchy (generalmente integrando sobre un pequeño contorno circular que encierra el origen). La identidad buscada puede hallarse mediante manipulaciones de integrales. Algunas de estas manipulaciones no son claras desde la perspectiva de la función generadora. Por ejemplo, el integrando suele ser una función racional , y la suma de los residuos de una función racional es cero, lo que produce una nueva expresión para la suma original. El residuo en el infinito es particularmente importante en estas consideraciones. Si durante la suma aparece una serie que no es finita, los contornos deben elegirse de manera que la serie converja. Algunas de las integrales empleadas por el método de Egorychev son:

• Primera integral del coeficiente binomial

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

dónde${\displaystyle 0<\rho <\infty }$

• Integral del segundo coeficiente binomial

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

dónde${\displaystyle 0<\rho <1}$

• Integral de exponenciación

${\displaystyle 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:}$

dónde${\displaystyle 0<\rho <\infty }$

• Soporte de Iverson

${\displaystyle [[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}$

dónde${\displaystyle 0<\rho <1}$

• Número Stirling de primera especie

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

dónde${\displaystyle 0<\rho <1}$

• Número de Stirling de segunda especie

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

dónde${\displaystyle 0<\rho <\infty .}$

Supongamos que buscamos evaluar

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

que se afirma que es  :${\displaystyle (-1)^{n}{n \choose j}{n+j \choose j}.}$

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

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

Esto da como resultado la suma  :

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

Esto es

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

Extrayendo el residuo en${\displaystyle w=0}$obtenemos

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

probando así la afirmación. No hay problemas de convergencia aquí ya que las sumas involucradas son finitas y con${\displaystyle n+k}$y${\displaystyle k}$ Al no ser negativo, podemos elegir cualquier valor finito distinto de cero para ${\displaystyle \varepsilon }$y${\displaystyle \gamma }$.

Supongamos que buscamos evaluar${\displaystyle \sum _{k=1}^{n}k{2n \choose n+k}.}$

Introducir

${\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 que esto es cero cuando${\displaystyle k>n}$para que podamos extender${\displaystyle k}$hasta el infinito para obtener la suma

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

Ahora pon${\displaystyle z(1-z)=w}$para que (observe que con${\displaystyle w=z+\cdots }$la imagen de${\displaystyle |z|=\varepsilon }$con${\displaystyle \varepsilon }$pequeño es otro contorno cerrado parecido a un círculo que hace una vuelta y que ciertamente podemos deformar para obtener otro círculo.${\displaystyle |w|=\gamma }$)

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

y además

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

para obtener la 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.}$

Esto se evalúa por inspección como (usar el binomio de Newton )

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

Aquí el mapeo de ${\displaystyle z=0}$a${\displaystyle w=0}$determina la elección de la raíz cuadrada . Para las condiciones en${\displaystyle \epsilon }$ y${\displaystyle \gamma }$ tenemos que para que la serie converja necesitamos ${\displaystyle |z/(1-z)|<1}$o ${\displaystyle \epsilon /(1-\epsilon )<1}$o ${\displaystyle \epsilon <1/2.}$ Cuanto más cerca esté el contorno de la imagen de ${\displaystyle |z|=\epsilon }$ llega al origen es ${\displaystyle \epsilon -\epsilon ^{2}}$ por eso elegimos ${\displaystyle \gamma <\epsilon -\epsilon ^{2}}$ Por ejemplo ${\displaystyle \gamma =\epsilon ^{2}-\epsilon ^{3}.}$ Esto también garantiza que ${\displaystyle \gamma <1/4}$entonces ${\displaystyle |w|=\gamma }$no intersecta el corte de la rama ${\displaystyle [1/4,\infty )}$ (y está contenido en la imagen de ${\displaystyle |z|=\epsilon }$). Por ejemplo${\displaystyle \epsilon =1/3}$ y${\displaystyle \gamma =2/27}$funcionará.

Este ejemplo también se presta a métodos más sencillos, pero se incluyó aquí para demostrar el efecto de sustituir en la variable de integración.

• Hosam Mahmoud, 2022, Historia y ejemplos del método Egorychev
• Marko Riedel, 2024, Ejemplos computacionales del uso del método de Egorychev para evaluar sumas que involucran tipos de números combinatorios (partes 1 y 2, series de potencias formales y operadores de residuos).
• Marko Riedel, 2024, Ejemplos computacionales del uso del método de Egorychev para evaluar sumas que involucran tipos de números combinatorios (parte 3, variables complejas)

• Egorychev, GP (1984). Representación integral y el cálculo de sumas combinatorias . American Mathematical Society. ISBN 9780821898093.
• Riedel, Marko; Mahmoud, Hosam (2023). "Método Egorychev: un tesoro escondido" . La Matemática . 2 (4): 893– 933. doi : 10.1007/s44007-023-00065-y .