Misplaced Pages

Hypergeometric identity

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Hypergeometric identities) Equalities involving sums over the coefficients occurring in hypergeometric series For identities satisfied by the hypergeometric function, see List of hypergeometric identities.
This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Hypergeometric identity" – news · newspapers · books · scholar · JSTOR (May 2024) (Learn how and when to remove this message)

In mathematics, hypergeometric identities are equalities involving sums over hypergeometric terms, i.e. the coefficients occurring in hypergeometric series. These identities occur frequently in solutions to combinatorial problems, and also in the analysis of algorithms.

These identities were traditionally found 'by hand'. There exist now several algorithms which can find and prove all hypergeometric identities.

Examples

∑ i = 0 n ( n i ) = 2 n {\displaystyle \sum _{i=0}^{n}{n \choose i}=2^{n}}
∑ i = 0 n ( n i ) 2 = ( 2 n n ) {\displaystyle \sum _{i=0}^{n}{n \choose i}^{2}={2n \choose n}}
∑ k = 0 n k ( n k ) = n 2 n − 1 {\displaystyle \sum _{k=0}^{n}k{n \choose k}=n2^{n-1}}
∑ i = n N i ( i n ) = ( n + 1 ) ( N + 2 n + 2 ) − ( N + 1 n + 1 ) {\displaystyle \sum _{i=n}^{N}i{i \choose n}=(n+1){N+2 \choose n+2}-{N+1 \choose n+1}}

Definition

There are two definitions of hypergeometric terms, both used in different cases as explained below. See also hypergeometric series.

A term tk is a hypergeometric term if

t k + 1 t k {\displaystyle {\frac {t_{k+1}}{t_{k}}}}

is a rational function in k.

A term F(n,k) is a hypergeometric term if

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

is a rational function in k.

There exist two types of sums over hypergeometric terms, the definite and indefinite sums. A definite sum is of the form

∑ k t k . {\displaystyle \sum _{k}t_{k}.}

The indefinite sum is of the form

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

Proofs

Although in the past proofs have been found for many specific identities, there exist several general algorithms to find and prove identities. These algorithms first find a simple expression for a sum over hypergeometric terms and then provide a certificate which anyone can use to check and prove the correctness of the identity.

For each of the hypergeometric sum types there exist one or more methods to find a simple expression. These methods also provide the certificate to check the identity's proof:

The book A = B by Marko Petkovšek, Herbert Wilf and Doron Zeilberger describes the three main approaches mentioned above.

See also

External links

Categories: