Proving Hypergeometric Identities By Numerical Verifications

The stupefying idea of proving hypergeometric identities by checking a finite number of its special cases, say for n₀≤n≤n₁, was first realized by Doron Zeilberger in 1981, and then implemented by Lily Yen in 1993. Since then, seeking a small upper bound for n₁ so that the numerical verification is practical has attracted researchers' interests. This thesis mainly studies the problem of estimating n₁ and involved numerical computation issues.In general, estimating n₁ consists of estimating three numbers: the order L of the recurrence that the summation in the identity satisfies, the largest non-negative zero n_a of the leading coefficient of the recurrence, and the highest degree n_f of any of the coefficient polynomials of the recurrence. n₁ can be formulated as a simple function of these three numbers. In this thesis, we propose a new approach to estimate n_a and n_f, which, as examples indicate, are considerably smaller in comparison with previous results. Our approach relies largely on the study of the numerical aspects of the concrete symbolic linear systems produced by the classic Sister Celine's method and Zeilberger's algorithm.As previous work, we estimate n_a and n_f by evaluating upper bounds of the degree and height of polynomial solution of the symbolic linear system also, while our approach is distinguished by the exploration of the concrete systems. To this end, we first introduce some basic properties of the degree and height of polynomials, and derive upper bounds formulas for the degree and height of the determinant of a polynomial matrix. Computing issues of these two formulas are also discussed, where, especially, we attack the computation of the degree bound by interpreting it into a classical combinatorial optimization problem, the assignment problem. Then we present an algorithm for estimating the upper bounds of the degree and height of the polynomial solution of a symbolic linear system of equations. As a byproduct, we offer a method for numerically solving symbolic linear systems.Combining the above degree and height bound estimating algorithm with Sister Celine's method or Zeilberger's algorithm, we finally propose a new approach to derive sharper bounds for n_a and n_f, and consequently smaller n₁. Our approach is also applicable to q-hypergeometric identities. We test our method with plenty of examples. In comparison with previous results, our estimations of n₁ are greatly reduced. In addition, for the q case, our algorithm not only produces practical bounds for n₁, but also runs quickly, which implies that the idea of proving hypergeometric identities by numerical verifications has really been feasible.