Egorychev metod

Egorychev -metoden är en samling tekniker som introducerats av Georgy Egorychev för att hitta identiteter bland summor av binomialkoefficienter , Stirlingtal , Bernoullital , Harmoniska tal , katalanska tal och andra kombinatoriska tal. Metoden bygger på två observationer. För det första kan många identiteter bevisas genom att extrahera koefficienter för genererande funktioner . För det andra är många genererande funktioner konvergerande effektserier, och koefficientextraktion kan göras med hjälp av Cauchy-restsatsen (vanligtvis görs detta genom att integrera över en liten cirkulär kontur som omsluter origo). Den eftersökta identiteten kan nu hittas med hjälp av manipulationer av integraler. Vissa av dessa manipulationer är inte tydliga ur genereringsfunktionsperspektivet. Till exempel är integranden vanligtvis en rationell funktion och summan av resterna av en rationell funktion är noll, vilket ger ett nytt uttryck för den ursprungliga summan. Återstoden i oändligheten är särskilt viktig i dessa överväganden. Några av de integraler som används av Egorychev-metoden är:

Första binomialkoefficientintegralen

{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är $0<\rho <\infty$

Andra binomialkoefficientintegralen

{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är $0<\rho <1$

Exponentieringsintegral

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är $0<\rho <\infty$

Iverson-parentes

[[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är $0<\rho <1$

Stirlingtal av det första slaget

\left[{n \atop k}\right]={\frac {n!}{k!}}\;{\ underställ {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är $0<\rho <1$

Stirlingtal av det andra slaget

\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är $0<\rho <\infty .$

Exempel I

Antag att vi försöker utvärdera

S_{j}(n)=\summa _{k=0}^{ n}(-1)^{k}{n \välj k}{n+k \välj k}{k \välj j}

$(-1)^{n}{n \choose j}{n+j \choose j}.$ påstås

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

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

Detta ger för summan:

${\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}}}\summa _{k=0} ^{n}(-1)^{k}{n \välj 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}}$

Detta är

{\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}}}\summa _{q=0}^{n}{n \choose q}w^{q}(1+z)^{q}\;dw\;dz.

extraherar resten vid $w=0$ får vi

{\begin{aligned}&{\frac {(-1) ^{n}}{2\pi i}}\int _{|z|=\varepsilon }{\frac {(1+z)^{n}}{z^{n+1}}}{n \ välj j}(1+z)^{j}\;dz\\[6pt]={}&{n \välj 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}}

bevisar därmed påståendet.

Exempel II

Antag att vi försöker utvärdera $\sum _{k=1}^{n}k{2n \choose n+k}.$

Införa

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

Observera att detta är noll när $k>n$ så vi kan förlänga $k$ till oändligt för att erhålla summan

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

Sätt nu $z(1-z)=w$ så att (observera att med $w=z+\cdots$ bilden av $=\varepsilon }$ $|w |=\gamma$ med $\varepsilon$ small är ytterligare en sluten cirkelliknande kontur som gör ett varv och som vi säkert kan deformera för att få en annan cirkel | )

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

och dessutom

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

att få för integralen

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

Detta utvärderas genom inspektion till (använd Newton-binomial )

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

Här avgör mappningen från $z=0$ till $w=0$ valet av kvadratrot. För villkoren på $\epsilon$ och $\gamma$ har vi att för att serien ska konvergera kräver vi $1-z)|<1}$ $. { \displaystyle \epsilon <1/2.}$ eller $displaystyle \epsilon /(1-\epsilon )<1}$ eller Det närmaste bildkonturen av $|z|=\epsilon$ kommer till ursprunget är $\epsilon -\epsilon ^{2}$ så vi väljer $\gamma <\ epsilon -\epsilon ^{2}$ till exempel $\gamma =\epsilon ^{2}-\epsilon ^{3}.$ Detta säkerställer också att $\gamma <1/4$ så $|w|=\gamma$ skär inte grensnittet $[1/4,\infty )$ (och finns i bilden av $|z|=\epsilon$ ). Till exempel $\epsilon =1/3$ och $\gamma =2/27$ att fungera.