The Art Of Computer Programming Fundamental Algorithms - Donald E Knuth - 1995

The Art Of Computer Programming Fundamental Algorithms - Donald E Knuth - 1995

Contents
Foreword vii
A Quick Start . . . ix
I   Background 1
1  Proof Machines 3
1.1   Evolution of the province of human thought  . . . . . . . . . . . . . .      3
1.2   Canonical and normal forms  . . . . . . . . . . . . . . . . . . . . . . .      7
1.3   Polynomial identities  . . . . . . . . . . . . . . . . . . . . . . . . . . .      8
1.4   Proofs by example? . . . . . . . . . . . . . . . . . . . . . . . . . . . .      9
1.5   Trigonometric identities   . . . . . . . . . . . . . . . . . . . . . . . . .    11
1.6   Fibonacci identities . . . . . . . . . . . . . . . . . . . . . . . . . . . .    12
1.7   Symmetric function identities  . . . . . . . . . . . . . . . . . . . . . .    12
1.8   Elliptic function identities  . . . . . . . . . . . . . . . . . . . . . . . .    13
2  Tightening the Target 172.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    17
2.2   Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    21
2.3   Human and computer proofs; an example . . . . . . . . . . . . . . . .    23
2.4   A Mathematica session . . . . . . . . . . . . . . . . . . . . . . . . . .    27
2.5   A Maple session . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    29
2.6   Where we are and what happens next . . . . . . . . . . . . . . . . . .    30
2.7   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    31
3  The Hypergeometric Database 33
3.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    33
3.2   Hypergeometric series . . . . . . . . . . . . . . . . . . . . . . . . . . .    34
3.3   How to identify a series as hypergeometric  . . . . . . . . . . . . . . .    35
3.4   Software that identifies hypergeometric series . . . . . . . . . . . . . .    39
3.5   Some entries in the hypergeometric database . . . . . . . . . . . . . .    42
3.6   Using the database  . . . . . . . . . . . . . . . . . . . . . . . . . . . .    44
3.7   Is there really a hypergeometric database?  . . . . . . . . . . . . . . .    48
3.8   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    50
II   The Five Basic Algorithms 53
4  Sister Celine’s Method 55
4.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    55
4.2   Sister Mary Celine Fasenmyer  . . . . . . . . . . . . . . . . . . . . . .    57
4.3   Sister Celine’s general algorithm . . . . . . . . . . . . . . . . . . . . .    58
4.4   The Fundamental Theorem   . . . . . . . . . . . . . . . . . . . . . . .    64
4.5   Multivariate and “q” generalizations   . . . . . . . . . . . . . . . . . .    70
4.6   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    72
5  Gosper’s Algorithm 73
5.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    73
5.2   Hypergeometrics to rationals to polynomials  . . . . . . . . . . . . . .    75
5.3   The full algorithm: Step 2  . . . . . . . . . . . . . . . . . . . . . . . .    79
5.4   The full algorithm: Step 3  . . . . . . . . . . . . . . . . . . . . . . . .    84
5.5   More examples   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    86
5.6   Similarity among hypergeometric terms . . . . . . . . . . . . . . . . .    91
5.7   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    95
6  Zeilberger’s Algorithm 101
6.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   101
6.2   Existence of the telescoped recurrence . . . . . . . . . . . . . . . . . .   104
6.3   How the algorithm works . . . . . . . . . . . . . . . . . . . . . . . . .   106
6.4   Examples  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   109
6.5   Use of the programs   . . . . . . . . . . . . . . . . . . . . . . . . . . .   112
6.6   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   118
7  The WZ Phenomenon 121
7.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   121
7.2   WZ proofs of the hypergeometric database  . . . . . . . . . . . . . . .   126
7.3   Spinoffs from the WZ method  . . . . . . . . . . . . . . . . . . . . . .   127
7.4   Discovering new hypergeometric identities  . . . . . . . . . . . . . . .   135
7.5   Software for the WZ method . . . . . . . . . . . . . . . . . . . . . . .   137
7.6   Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   140
8  Algorithm Hyper 141
8.1   Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   141
8.2   The ring of sequences . . . . . . . . . . . . . . . . . . . . . . . . . . .   144
8.3   Polynomial solutions  . . . . . . . . . . . . . . . . . . . . . . . . . . .   148
8.4   Hypergeometric solutions . . . . . . . . . . . . . . . . . . . . . . . . .   151
8.5   A Mathematica session . . . . . . . . . . . . . . . . . . . . . . . . . .   156
8.6   Finding all hypergeometric solutions   . . . . . . . . . . . . . . . . . .   157
8.7   Finding all closed form solutions . . . . . . . . . . . . . . . . . . . . .   158
8.8   Some famous sequences that do not have closed form  . . . . . . . . .   159
8.9   Inhomogeneous recurrences . . . . . . . . . . . . . . . . . . . . . . . .   161
8.10 Factorization of operators   . . . . . . . . . . . . . . . . . . . . . . . .   162
8.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   164
III   Epilogue 169
9  An Operator Algebra Viewpoint 171
9.1   Early history   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   171
9.2   Linear difference operators . . . . . . . . . . . . . . . . . . . . . . . .   172
9.3   Elimination in two variables  . . . . . . . . . . . . . . . . . . . . . . .   177
9.4   Modified elimination problem  . . . . . . . . . . . . . . . . . . . . . .   180
9.5   Discrete holonomic functions . . . . . . . . . . . . . . . . . . . . . . .   184
9.6   Elimination in the ring of operators . . . . . . . . . . . . . . . . . . .   185
9.7   Beyond the holonomic paradigm . . . . . . . . . . . . . . . . . . . . .   185
9.8   Bi-basic equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   187
9.9   Creative anti-symmetrizing . . . . . . . . . . . . . . . . . . . . . . . .   188
9.10 Wavelets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   190
9.11 Abel-type identities . . . . . . . . . . . . . . . . . . . . . . . . . . . .   191
9.12 Another semi-holonomic identity   . . . . . . . . . . . . . . . . . . . .   193
9.13 The art   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   193
9.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   195
A The WWW sites and the software 197
A.1  The Maple packages EKHAD and qEKHAD . . . . . . . . . . . . . . . . .   198
A.2  Mathematica programs . . . . . . . . . . . . . . . . . . . . . . . . . .   199
Bibliography 201
Index 208