Pár Wilf – Zeilberger - Wilf–Zeilberger pair

vmatematika konkrétněkombinatorika, aPár Wilf – ZeilbergerneboWZ pár, je párfunkce které lze použít k certifikaci určitých kombinatorickýchidentity. Páry WZ jsou pojmenovány poHerbert S. Wilf aDoron Zeilberger a pomáhají při hodnocení mnohačástky zahrnujícíbinomické koeficienty, faktoriály a obecně jakékolihypergeometrická řada. Funkční protějšek WZ lze použít k nalezení ekvivalentního a mnohem jednoduššího součtu. Ačkoli ruční hledání dvojic WZ je ve většině případů nepraktické, Gosperův algoritmus poskytuje jistou metodu k nalezení protějšku funkce WZ a lze jej implementovat vsymbolický manipulační program.

Definice

Dvafunkce F aG vytvořte pár WZ tehdy a jen tehdy, pokud platí následující dvě podmínky:

${ Displaystyle F (n + 1, k) -F (n, k) = G (n, k + 1) -G (n, k),}$

${ displaystyle lim _ {M až pm infty} G (n, M) = 0.}$

Společně tyto podmínky zajišťují, že

${ displaystyle sum _ {k = - infty} ^ { infty} [F (n + 1, k) -F (n, k)] = 0}$

protože funkce G dalekohledy:

${ displaystyle { begin {zarovnáno} součet _ {k = - infty} ^ { infty} [F (n + 1, k) -F (n, k)] & {} = lim _ {M to infty} sum _ {k = -M} ^ {M} [F (n + 1, k) -F (n, k)] & {} = lim _ {M to infty } sum _ {k = -M} ^ {M} [G (n, k + 1) -G (n, k)] & {} = lim _ {M to infty} [G ( n, M + 1) -G (n, -M)] & {} = 0-0 & {} = 0. end {zarovnáno}}}$

Proto,

${ displaystyle sum _ {k = - infty} ^ { infty} F (n + 1, k) = sum _ {k = - infty} ^ { infty} F (n, k),}$

to je

${ displaystyle sum _ {k = - infty} ^ { infty} F (n, k) = konst.}$

Konstanta nezávisí nanJeho hodnotu lze zjistit dosazenímn = n₀pro konkrétnín₀.

LiF aG vytvoří pár WZ, pak vztah uspokojí

${ displaystyle G (n, k) = R (n, k) F (n, k-1),}$

kde ${ displaystyle R (n, k)}$ je racionální funkcí n a k a nazývá se Osvědčení o důkazu WZ.

Příklad

K ověření identity lze použít dvojici Wilf – Zeilberger

${ displaystyle sum _ {k = 0} ^ { infty} (- 1) ^ {k} {n zvolit k} {2k zvolit k} 4 ^ {n-k} = {2n zvolit n}.}$

Rozdělte identitu na pravou stranu:

${ displaystyle sum _ {k = 0} ^ { infty} { frac {(-1) ^ {k} {n zvolit k} {2k vybrat k} 4 ^ {nk}} {2n vybrat n}} = 1.}$

Použijte ověřovací certifikát

${ displaystyle R (n, k) = { frac {2k-1} {2n + 1}}}$

ověřit, že levá strana nezávisí nan,kde

${ displaystyle { begin {zarovnáno} F (n, k) & = { frac {(-1) ^ {k} {n zvolit k} {2k zvolit k} 4 ^ {nk}} {2n zvolte n}}, G (n, k) & = R (n, k) F (n, k-1). end {zarovnáno}}}$

Nyní F aG tvoří pár Wilf – Zeilberger.

Chcete-li dokázat, že konstanta na pravé straně identity je 1, nahraďte jin = 0, například.

Reference

• Marko Petkovsek; Herbert Wilf a Doron Zeilberger (1996). A = B. AK Peters. ISBN  1-56881-063-6.
• Tefera, Akalu (2010), „Co je ... pár Wilf-Zeilberger?“ (PDF), Oznámení AMS, 57 (4): 508–509.

externí odkazy

• Gosperův algoritmus poskytuje metodu generování párů WZ, pokud existují.
• Generovánífunkcionologie poskytuje podrobnosti o metodě WZ certifikace identity.