# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Hypergeometric function identities

In mathematics, hypergeometric identities are equalities involving sums over hypergeometric terms, i.e. the coefficients occuring 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.

 Contents

## Examples

$\sum_{i=0}^{n} {n \choose i} = 2^{n}$
$\sum_{i=0}^{n} {n \choose i}^2 = {2n \choose n}$
$\sum_{k} k {n \choose k} = n2^{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

$\frac{t_{k+1}}{t_k}$ is a rational function in k.

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

$\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

 ∑ tk. k

The indefinite sum is of the form

$\sum_{k=0}^{n} F(n,k).$

## Proofs

Although in the past one has found beautiful proofs of certain identities there exist several 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 could use to easily 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 a certificate to easily check the proof of an identity:

• Indefinite sums: Sister Celine's Method, Zeilberger's Algorithm
• Definite sums: Gosper's Algorithm

A book named A=B has been written by Marko Petkovsek, Herbert Wilf and Doron Zeilberger describing the three main approaches described above.