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
0 Your Comments:
Post a Comment