Egorychev method

Метод Егорычева — это набор методов, введенных Георгием Егорычевым для нахождения тождеств между суммами биномиальных коэффициентов , чисел Стирлинга , чисел Бернулли , гармонических чисел , чисел Каталана и других комбинаторных чисел. Метод основан на двух наблюдениях. Во-первых, многие тождества можно доказать, извлекая коэффициенты производящих функций . Во-вторых, многие производящие функции представляют собой сходящиеся степенные ряды, и извлечение коэффициентов можно выполнить с помощью теоремы о вычетах Коши (обычно это делается путем интегрирования по небольшому круговому контуру, охватывающему начало координат). Искомое тождество теперь можно найти с помощью манипуляций с интегралами. Некоторые из этих манипуляций непонятны с точки зрения производящей функции. Например, подынтегральная функция обычно является рациональной функцией , а сумма остатков рациональной функции равна нулю, что дает новое выражение для исходной суммы. Остаток на бесконечности особенно важен в этих соображениях.Некоторые из интегралов, используемых в методе Егорычева:

Интеграл первого биномиального коэффициента

{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

где $0<\rho <\infty$

Интеграл второго биномиального коэффициента

{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

где $0<\rho <1$

Интеграл возведения в степень

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:

где $0<\rho <\infty$

Кронштейн Айверсона

[[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

где $0<\rho <1$

Число Стирлинга первого рода

\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

где $0<\rho <1$

Число Стирлинга второго рода

\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

где $0<\rho <\infty .$

Пример I

Предположим, мы хотим оценить

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

который, как утверждается, является: $(-1)^{n}{n \choose j}{n+j \choose j}.$

Представлять : ${n+k \choose k}={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n+k}}{z^{k+1}}}\;dz$

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

Это дает сумму:

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

Это

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

Извлечение остатка в $w=0$ мы получаем

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

тем самым доказывая утверждение.

Пример II

Предположим, мы хотим оценить $\sum _{k=1}^{n}k{2n \choose n+k}.$

Представлять

{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.

Обратите внимание, что это значение равно нулю, когда $k>n$ поэтому мы можем продлить $k$ кбесконечность, чтобы получить сумму

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

Теперь поставь $z(1-z)=w$ так что (заметьте это с помощью $w=z+\cdots$ образ $|z|=\varepsilon$ с $\varepsilon$ маленький — это еще один замкнутый контур, похожий на круг, который делает один оборот и который мы, безусловно, можем деформировать, чтобы получить другой круг. $|w|=\gamma$ )

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

и более того

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

получить интеграл

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

При проверке это оценивается как (используйте бином Ньютона )

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

Здесь отображение из $z=0$ к $w=0$ определяетвыбор квадратного корня. Для условий на $\epsilon$ и $\gamma$ у нас есть то, что для того, чтобы ряд сходился, мытребовать $|z/(1-z)|<1$ или $\epsilon /(1-\epsilon )<1$ или $\epsilon <1/2.$ Самое близкое, что изображениеконтур $|z|=\epsilon$ приходит к началу $\epsilon -\epsilon ^{2}$ поэтому мы выбираем $\gamma <\epsilon -\epsilon ^{2}$ например $\gamma =\epsilon ^{2}-\epsilon ^{3}.$ Это также гарантирует, что $\gamma <1/4$ так $|w|=\gamma$ не пересекает ветвьрезать $[1/4,\infty )$ (и содержится в образе $|z|=\epsilon$ ). Например $\epsilon =1/3$ и $\gamma =2/27$ будет работать.