tailieunhanh - Develop computer programs for simplifying sums that involve binomial coefficients: The Art of Computer Programming, Volume 1: Fundamental Algorithms

Science is what we understand well enough to explain to a computer. Art is everything else we do. During the past several years an important part of mathematics has been transformed from an Art to a Science: No longer do we need to get a brilliant insight in order to evaluate sums of binomial coefficients, and many similar formulas that arise frequently in practice; we can now follow a mechanical procedure and discover the answers quite systematically. | This page intentionally left blank [50] Develop computer programs for simplifying sums that involve binomial coefficients. Exercise 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 University of Pennsylvania Ljubljana, Slovenia Philadelphia, PA, USA Doron Zeilberger Temple University Philadelphia, PA, USA April 27, 1997 ii Contents Foreword vii A Quick Start . ix I Background 1 1 Proof Machines 3 Evolution of the province of human thought . . . . . . . . . . . . . . 3 Canonical and normal forms . . . . . . . . . . . . . . . . . . . . . . . 7 . 8 9 Trigonometric identities . . . . . . . . . . . . . . . . . . . . . . . . . 11 12 Symmetric function identities . . . . . . . . . . . . . . . . . . . . . . 12 Elliptic function identities . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Tightening the Target 17 17 21 Human and computer proofs; an example . . . . . . . . . . . . . . . . 24 27 29 Where we are and what happens next . . . . . . . . . . . . . . . . . . 30 31 3 The Hypergeometric Database 33 33 . 34 How to identify a series as hypergeometric . . . . . . . . . . . . . . . 35 Software that identifies hypergeometric series . . . . . . . . . . . . . . 39 iv CONTENTS Some entries in the hypergeometric database . . . . . . . . . . . . . . 42 44 Is