A=b (symbolic Summation Algorithms)

This page intentionally left blank [50] Develop computer programs for simplifying sums that involve binomial coefficients. Exercise 1.2.6.63 in The Art of Computer Programming, Volume 1: Fundamental Algorithms by Donald E. Knuth, Addison Wesley, Reading, Massachusetts, 1968. A=B Marko Petkovˇ sek Herbert S. Wilf University of Ljubljana Ljubljana, Slovenia University of Pennsylvania Philadelphia, PA, USA Doron Zeilberger Temple University Philadelphia, PA, USA April 27, 1997 ii Contents Foreword vii A Quick Start . . . ix I 1 Background 1 Proof Machines 1.1 Evolution of the province of human thought 1.2 Canonical and normal forms . . . . . . . . . 1.3 Polynomial identities . . . . . . . . . . . . . 1.4 Proofs by example? . . . . . . . . . . . . . . 1.5 Trigonometric identities . . . . . . . . . . . 1.6 Fibonacci identities . . . . . . . . . . . . . . 1.7 Symmetric function identities . . . . . . . . 1.8 Elliptic function identities . . . . . . . . . . 2 Tightening the Target 2.1 Introduction . . . . . . . . . . . . . . . . 2.2 Identities . . . . . . . . . . . . . . . . . . 2.3 Human and computer proofs; an example 2.4 A Mathematica session . . . . . . . . . . 2.5 A Maple session . . . . . . . . . . . . . . 2.6 Where we are and what happens next . . 2.7 Exercises . . . . . . . . . . . . . . . . . . 3 The 3.1 3.2 3.3 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hypergeometric Database Introduction . . . . . . . . . . . . . . . . . . . Hypergeometric series . . . . . . . . . . . . . . How to identify a series as hypergeometric . . Software that identifies hypergeometric series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .