http://debianws.lexgopc.com/wiki143/api.php?action=feedcontributions&feedformat=atom&user=80.71.142.78wiki143 - User contributions [en]2026-05-15T07:54:55ZUser contributionsMediaWiki 1.43.1http://debianws.lexgopc.com/wiki143/index.php?title=Hypergeometric_identity&diff=412690Hypergeometric identity2024-09-01T15:22:35Z<p>80.71.142.78: /* Proofs */ linkify Celine, Zeilberger</p>
<hr />
<div>{{short description|Equalities involving sums over the coefficients occurring in hypergeometric series}}<br />
{{For|identities satisfied by the hypergeometric function|List of hypergeometric identities}}<br />
{{more sources|date=May 2024}}<br />
<br />
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]]. <br />
<br />
These identities were traditionally found 'by hand'. There exist now several algorithms which can find and ''prove'' all hypergeometric identities.<br />
<br />
== Examples ==<br />
: <math> \sum_{i=0}^{n} {n \choose i} = 2^{n} </math><br />
<br />
: <math> \sum_{i=0}^{n} {n \choose i}^2 = {2n \choose n} </math><br />
<br />
: <math> \sum_{k=0}^{n} k {n \choose k} = n2^{n-1} </math><br />
<br />
: <math> \sum_{i=n}^{N} i{i \choose n} = (n+1){N+2\choose n+2}-{N+1\choose n+1} </math><br />
<br />
== Definition ==<br />
There are two definitions of hypergeometric terms, both used in different cases as explained below. See also [[hypergeometric series]].<br />
<br />
A term ''t<sub>k</sub>'' is a hypergeometric term if<br />
: <math>\frac{t_{k+1}}{t_k} </math><br />
<br />
is a [[rational function]] in ''k''.<br />
<br />
A term ''F(n,k)'' is a hypergeometric term if<br />
: <math>\frac{F(n,k+1)}{F(n,k)} </math><br />
<br />
is a rational function in ''k''.<br />
<br />
There exist two types of sums over hypergeometric terms, the definite and indefinite sums. A definite sum is of the form<br />
: <math> \sum_{k} t_k.</math><br />
<br />
The indefinite sum is of the form<br />
: <math> \sum_{k=0}^{n} F(n,k).</math><br />
<br />
== Proofs ==<br />
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.<br />
<br />
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:<br />
* ''Definite sums'': [[Mary Celine Fasenmyer|Sister Celine]]'s Method, [[Doron Zeilberger|Zeilberger]]'s algorithm<br />
* ''Indefinite sums'': [[Gosper's algorithm]]<br />
<br />
The book '''A = B''' by [[Marko Petkovšek]], [[Herbert Wilf]] and [[Doron Zeilberger]] describes the three main approaches mentioned above.<br />
<br />
==See also==<br />
* [[Table of Newtonian series]]<br />
<br />
== External links ==<br />
* [http://www.math.upenn.edu/~wilf/AeqB.html The book "A = B"], this book is freely downloadable from the internet.<br />
* [https://web.archive.org/web/20161002083601/http://www.exampleproblems.com/wiki/index.php?title=Special_Functions Special-functions examples] at exampleproblems.com<br />
<br />
[[Category:Factorial and binomial topics]]<br />
[[Category:Hypergeometric functions]]<br />
[[Category:Mathematical identities]]<br />
[[fr:Identités hypergéométriques]]</div>80.71.142.78http://debianws.lexgopc.com/wiki143/index.php?title=Revolutions_per_second&diff=6305146Revolutions per second2017-11-19T21:21:56Z<p>80.71.142.78: change redir. destination to cycle per second</p>
<hr />
<div>#REDIRECT [[Cycle per second]]</div>80.71.142.78