Hypergeometrická identita - Hypergeometric identity

v matematika, hypergeometrické identity jsou rovnosti zahrnující součty nad hypergeometrickými členy, tj. koeficienty vyskytující se v hypergeometrická řada. Tyto identity se často vyskytují v řešeních kombinační problémy, a také v analýza algoritmů.

Tyto identity se tradičně nacházely „ručně“. Nyní existuje několik algoritmů, které lze najít a dokázat všechny hypergeometrické identity.

Příklady

${ displaystyle sum _ {i = 0} ^ {n} {n zvolit i} = 2 ^ {n}}$

${ displaystyle sum _ {i = 0} ^ {n} {n zvolit i} ^ {2} = {2n zvolit n}}$

${ displaystyle sum _ {k = 0} ^ {n} k {n zvolit k} = n2 ^ {n-1}}$

${ displaystyle sum _ {i = n} ^ {N} i {i zvolit n} = (n + 1) {N + 2 zvolit n + 2} - {N + 1 zvolit n + 1}}$

Definice

Existují dvě definice hypergeometrických výrazů, které se používají v různých případech, jak je vysvětleno níže. Viz také hypergeometrická řada.

Termín t_k je hypergeometrický výraz, pokud

${ displaystyle { frac {t_ {k + 1}} {t_ {k}}}}$

je racionální funkce v k.

Termín F (n, k) je hypergeometrický výraz, pokud

${ displaystyle { frac {F (n, k + 1)} {F (n, k)}}}$

je racionální funkce v k.

Nad hypergeometrickými výrazy existují dva typy součtů, určité a neurčité součty. Určitý součet má formu

${ displaystyle sum _ {k} t_ {k}.}$

Neomezená částka má formu

${ displaystyle sum _ {k = 0} ^ {n} F (n, k).}$

Důkazy

I když v minulosti^{[SZO? ]} našel důkazy o určitých totožnostech^{[vágní ]} existuje několik algoritmů^{[vágní ]} najít a prokázat totožnost. Tyto algoritmy nejprve najdou a jednoduchý výraz za částku nad hypergeometrickými termíny a poté poskytněte certifikát, který by kdokoli mohl použít ke snadné kontrole a prokázání správnosti identity.

Pro každý z typů hypergeometrických součtů existuje jedna nebo více metod k nalezení a jednoduchý výraz. Tyto metody také poskytují certifikát pro snadnou kontrolu dokladu totožnosti:

• Určité částky: Metoda sestry Celine, Zeilbergerův algoritmus
• Neomezené částky: Gosperův algoritmus

Kniha s názvem A = B napsal autor Marko Petkovšek, Herbert Wilf a Doron Zeilberger popisující tři hlavní přístupy popsané výše.

Viz také

• Tabulka newtonovské řady

externí odkazy

• Kniha "A = B", tato kniha je volně ke stažení z internetu.
• Příklady speciálních funkcí na exampleproblems.com