Metoda Jegoryczewa

Metoda Egorycheva to zbiór technik wprowadzonych przez Georgy'ego Egorycheva do znajdowania tożsamości wśród sum współczynników dwumianowych , liczb Stirlinga , liczb Bernoulliego , liczb harmonicznych , liczb katalońskich i innych liczb kombinatorycznych. Metoda opiera się na dwóch obserwacjach. Po pierwsze, wiele tożsamości można udowodnić, wyodrębniając współczynniki funkcji generujących . Po drugie, wiele funkcji generujących to zbieżne szeregi potęgowe, a ekstrakcję współczynników można przeprowadzić za pomocą twierdzenia o resztach Cauchy'ego (zwykle odbywa się to poprzez całkowanie po małym okrągłym konturze obejmującym początek). Poszukiwaną tożsamość można teraz znaleźć za pomocą manipulacji całekami. Niektóre z tych manipulacji nie są jasne z punktu widzenia funkcji generującej. Na przykład całka jest zwykle funkcją wymierną , a suma reszt funkcji wymiernej wynosi zero, co daje nowe wyrażenie na pierwotną sumę. Reszta w nieskończoności jest szczególnie ważna w tych rozważaniach. Niektóre całki stosowane w metodzie Jegoryczewa to:

Pierwsza całka po współczynniku dwumianowym

{\ Displaystyle {n \ wybierz k} = {\ underset {z} {\ operatorname {res}}} \; {\ Frac {(1 + z) ^ {n}}{z^{k+1}}}={\frac {1}{2\pi i}}\int _{|z|=\rho }{\frac {(1+z)^{ n}}{z^{k+1}}}\;dz}

gdzie ${\ Displaystyle 0 <\ rho <\ infty}$

Druga całka ze współczynnikiem dwumianowym

{\ Displaystyle {n \ wybierz k} = {\ underset {z} {\ operatorname {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}

gdzie ${\ Displaystyle 0 <\ rho <1}$

Całka potęgująca

{\ Displaystyle n ^ {k} = k! \; {\ underset {z} {\ operatorname {res}}} \; {\ Frac {\ exp (nz)}{z^{k+1}}}={\frac {k!}{2\pi i}}\int _{|z|=\rho }{\frac {\exp(nz)} {z^{k+1}}}\;dz:}

gdzie ${\ Displaystyle 0 <\ rho <\ infty}$

Nawias Iversona

{\ Displaystyle [[k \ równoważnik n]] = {\ underset {z} {\ operatorname {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}

gdzie ${\ Displaystyle 0 <\ rho <1}$

Liczba Stirlinga pierwszego rodzaju

{\ Displaystyle \ lewo [{n \ na szczycie k} \ prawej] = {\ 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}

gdzie ${\ Displaystyle 0 <\ rho <1}$

Liczba Stirlinga drugiego rodzaju

{\ Displaystyle \ lewo \ {{n \ na szczycie k} \ prawo \} = {\ 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}

gdzie ${\ Displaystyle 0 <\ rho <\ infty.}$

Przykład I

Załóżmy, że chcemy ocenić

{\ Displaystyle S_ {j} (n) = \ suma _ {k = 0} ^ { n}(-1)^{k}{n \wybierz k}{n+k \wybierz k}{k \wybierz j}}

który jest uważany za : ${\ Displaystyle (-1) ^ {n} {n \ wybierz j} {n + j \ wybierz j}.}$

Wprowadź : ${\ Displaystyle {n + k \ wybrać k} = {\ Frac {1} {2 \ pi i}} \ int _ {| z | = \ varepsilon }{\frac {(1+z)^{n+k}}{z^{k+1}}}\;dz}$

oraz : ${\ Displaystyle {k \ wybierz j} = {\ Frac {1} {2 \ pi i}} \ int _ {| w | = \ gamma}} {\ Frac {(1 + w) ^ {k}} {w ^{j+1}}}\;dw.}$

Daje to sumę:

${\ Displaystyle {\ rozpocząć {wyrównane} i {\ 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{wyrównane}}}$

To jest

{\ 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 \wybierz q}w^{q}(1+z)^{q}\;dw\;dz.}

Wyodrębniając pozostałość w otrzymujemy ${\ displaystyle w = 0}$

{\ Displaystyle {\ rozpocząć {wyrównane} i {\ Frac {(-1) ^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{n \ wybierz j}(1+z)^{j}\;dz\\[6pt]={}&{n \wybierz j}{\frac {(-1)^{n}}{2\pi i}} \int _{|z|=\varepsilon }{\frac {(1+z)^{n+j}}{z^{n+1}}}\;dz\\[6pt]={}&( -1)^{n}{n \wybierz j}{n+j \wybierz n}\end{wyrównane}}}

udowadniając w ten sposób twierdzenie.

Przykład II

Załóżmy, że chcemy obliczyć ${\ Displaystyle \ suma _ {k = 1} ^ {n} k {2n \ wybierz n + k}.}$

Wprowadzić

{\ Displaystyle {2n \ wybierz n + k} = {\ Frac {1} {2 \ pi i}} \ int _ {| z | = \ varepsilon} {\ frac {1} {z ^ {nk + 1}}}{\frac {1}{(1-z)^{n+k+1}}}\;dz.}

Zauważ, że jest to zero, gdy ${\ displaystyle k> n}$ , więc możemy rozszerzyć do nieskończoności, aby uzyskać sumę ${\ displaystyle k> n}$

{\ Displaystyle {\ rozpocząć {wyrównane} i {\ 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{wyrównane}} }

Teraz umieść ${\ Displaystyle z (1-z) = w}$ tak, że (zauważ, że z ${\ Displaystyle w = z + \ cdots}$ | ${\ Displaystyle | z | = \ varepsilon}$ $z$ małym kolejnym konturem przypominającym zamknięty okrąg, który wykonuje jeden obrót i który z pewnością możemy zdeformować, aby uzyskać kolejny okrąg ${\ displaystyle | w |=\gamma }$ )

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

a ponadto

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

dostać dla całki

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

To ocenia się przez inspekcję do (użyj dwumianu Newtona )

{\ Displaystyle {\ rozpocząć {wyrównane} i 4 ^ {n-1} {n-1 + 1/2 \ wybierz n-1} = 4 ^ {n-1} {n-1/2 \ wybierz 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}}}

Tutaj mapowanie od ${\ displaystyle z = 0}$ do ${\ displaystyle w = 0}$ określa wybór pierwiastka kwadratowego. Dla warunków na $,$ mamy $potrzebujemy$ że aby szereg był zbieżny, ${\ Displaystyle | z / (1-z) | <1}$ lub ${\ Displaystyle \ epsilon / (1- \ epsilon) <1}$ lub $\epsilon <1/2.$ Najbliższy kontur obrazu ${\ Displaystyle | z | = \ epsilon}$ dochodzi do pochodzenia to ${\ Displaystyle \ epsilon - \ epsilon ^ {2}}$ , więc wybieramy ${\ Displaystyle \ gamma <\ epsilon -\epsilon ^{2}}$ na przykład $^ {3}.}$ $epsilon$ również tak $}$ $i$ ${\ displaystyle | z | = \ epsilon}$ nie przecina cięcia gałęzi zawarte w obrazie ). $\ epsilon = 1/3$ przykład ${\$ i działać

Ten przykład również prowadzi do prostszych metod, ale został tutaj uwzględniony, aby zademonstrować efekt podstawienia do zmiennej integracji.

Obliczenia z wykorzystaniem formalnych szeregów potęgowych

Możemy zastosować regułę zamiany zmiennych 1.8 (5) z tekstu Jegoryczewa (str. 16) na całce

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

z ${\ Displaystyle A (z) = {\ Frac {z} {(1-2z) ^ {2}}}}$ i ${\ Displaystyle f (z) = {\ Frac {1} {1-z}}.}$ Otrzymujemy ${\ Displaystyle h (z) = z (1-z)}$ i znajdź