A_equals_B-Petksovsek-Wilf-Zeilburger.pdf

This page intentionally left blank

[50] Develop computer programs for simplifying sums

that involve binomial coe±cients.

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

Herbert S. Wilf

University of Pennsylvania

Philadelphia, PA, USA

Doron Zeilberger

Temple University

Philadelphia, PA, USA

April 27, 1997

Marko Petkovsek

University of Ljubljana

Ljubljana, Slovenia

Contents

Foreword

vii

A Quick Start :::

IB kg ound

1 Proof Machines 3

1.1 Evolutionoftheprovinceofhumanthought .............. 3

1.2 Canonicalandnormalforms....................... 7

1.3 Polynomialidentities ........................... 8

1.4 Proofsbyexample?............................ 9

1.5 Trigonometricidentities ......................... 11

1.6 Fibonacciidentities............................ 12

1.7 Symmetricfunctionidentities ...................... 12

1.8 Ellipticfunctionidentities ........................ 13

2 Tightening the Target 17

2.1 Introduction................................ 17

2.2 Identities.................................. 21

2.3 Humanandcomputerproofs;anexample................ 23

2.4 AMathematicasession.......................... 27

2.5 AMaplesession.............................. 29

2.6 Whereweareandwhathappensnext.................. 30

2.7 Exercises.................................. 31

3 The Hypergeometric Database 33

3.1 Introduction................................ 33

3.2 Hypergeometricseries........................... 34

3.3 Howtoidentifyaseriesashypergeometric ............... 35

3.4 Softwarethatidenti¯eshypergeometricseries.............. 39