Егорычева метод - Egorychev method

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

Основные интегралы, используемые в методе Егорычева:

• Первый биномиальный интеграл коэффициентов

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

• Второй биномиальный интеграл коэффициентов

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

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

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

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

${\displaystyle [[0\leq k\leq n]]={\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {z^{k}}{z^{n+1}}}{\frac {1}{1-z}}\;dz.}$

Пример I

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

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

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

Вводить

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

и

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

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

${\displaystyle {\begin{aligned}&{\frac {1}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z}}{\frac {1}{2\pi i}}\int _{|w|=\varepsilon }{\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|=\varepsilon }{\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|=\varepsilon }{\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|=\varepsilon }{\frac {1}{w^{j+1}}}(1+w+wz)^{n}\;dw\;dz.\end{aligned}}}$

Это

${\displaystyle {\frac {(-1)^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{\frac {1}{2\pi i}}\int _{|w|=\varepsilon }{\frac {1}{w^{j+1}}}\sum _{q=0}^{n}{n \choose q}w^{q}(1+z)^{q}\;dw\;dz.}$

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

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

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

Пример II

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

Вводить

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

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

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

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

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

и, кроме того

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

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

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

Это оценивается путем осмотра (используйте Бином Ньютона )

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

Здесь отображение из ${\displaystyle z=0}$ к ${\displaystyle w=0}$ определяет выбор квадратного корня. Этот пример также уступает место более простым методам, но был включен сюда, чтобы продемонстрировать эффект подстановки в переменную интегрирования.

внешняя ссылка

• Вычислительные примеры использования метода Егорычева для вычисления сумм с биномиальными коэффициентами

Рекомендации

• Егорычев, Г.П. (1984). Интегральное представление и вычисление комбинаторных сумм. Американское математическое общество.