These identities occur frequently in solutions to combinatorial problems, and also in the analysis of algorithms.
A definite sum is of the form The indefinite sum is of the form 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.