Yuriy  Choliy


Rutgers University



Automated Proofs of Combinatorial Identities

Research Advisor:

professor Andrew Sills, Rutgers University

Background information.

Identities that involve hypergeometric series play an important role in various branches of modern mathematics. It turns out, that one can discover new identities of this type and prove existing identities in a completely algorithmic fashion. First complete algorithm for doing this was developed early in 1990 by professor Herbert Wilf (University of Pennsylvania) and professor Doron Zeilberger (Rutgers University). They called it WZ method in honor of two famous complex variables. A great introduction toWZ theory can be downloaded here free of charge. A crucial step in WZ-type proof of a given identity is one that involves finding a certain rational function R which is unique for every identiity. To find this function, WZ method uses algorithm developed by R.J. Gosper. Because use of Gosper's algorithm can be very time- and memory-consuming, many important identities still cannot be proven using WZ method. The goal of my REU research project was to develop new, faster and more efficient method  for finding function R. Final presentation of our results can be found here. We implemented our method as  Maple package; it can be downloaded from here.