Editing Hypergeometric identity

{{short description|Equalities involving sums over the coefficients occurring in hypergeometric series}}
{{For|identities satisfied by the hypergeometric function|List of hypergeometric identities}}
{{more sources|date=May 2024}}

In [[mathematics]], '''hypergeometric identities''' are equalities involving sums over hypergeometric terms, i.e. the coefficients occurring in [[hypergeometric series]]. These [[Identity (mathematics)|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 ==
: <math> \sum_{i=0}^{n} {n \choose i} = 2^{n} </math>

: <math> \sum_{i=0}^{n} {n \choose i}^2 = {2n \choose n} </math>

: <math> \sum_{k=0}^{n} k {n \choose k} = n2^{n-1} </math>

: <math> \sum_{i=n}^{N} i{i \choose n} = (n+1){N+2\choose n+2}-{N+1\choose n+1}       </math>

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

A term ''t<sub>k</sub>'' is a hypergeometric term if
: <math>\frac{t_{k+1}}{t_k} </math>

is a [[rational function]] in ''k''.

A term ''F(n,k)'' is a hypergeometric term if
: <math>\frac{F(n,k+1)}{F(n,k)} </math>

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
: <math> \sum_{k} t_k.</math>

The indefinite sum is of the form
: <math> \sum_{k=0}^{n} F(n,k).</math>

== 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:
* ''Definite sums'': [[Mary Celine Fasenmyer|Sister Celine]]'s Method, [[Doron Zeilberger|Zeilberger]]'s algorithm
* ''Indefinite sums'': [[Gosper's algorithm]]

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

==See also==
* [[Table of Newtonian series]]

== External links ==
* [http://www.math.upenn.edu/~wilf/AeqB.html The book "A = B"], this book is freely downloadable from the internet.
* [https://web.archive.org/web/20161002083601/http://www.exampleproblems.com/wiki/index.php?title=Special_Functions Special-functions examples] at exampleproblems.com

[[Category:Factorial and binomial topics]]
[[Category:Hypergeometric functions]]
[[Category:Mathematical identities]]
[[fr:Identités hypergéométriques]]