Manuel Kauers & Peter Paule 
The Concrete Tetrahedron [PDF ebook] 
Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates

The book treats four mathematical concepts which play a fundamental role in many different areas of mathematics: symbolic sums, recurrence (difference) equations, generating functions, and asymptotic estimates.Their key features, in isolation or in combination, their mastery by paper and pencil or by computer programs, and their applications to problems in pure mathematics or to ‘real world problems’ (e.g. the analysis of algorithms) are studied. The book is intended as an algorithmic supplement to the bestselling ‘Concrete Mathematics’ by Graham, Knuth and Patashnik.

Mục lục

1 Introduction1.1 Selection Sort and Quicksort1.2 Recurrence Equations1.3 Symbolic Sums1.4 Generating Functions1.5 Asymptotic Estimates1.6 The Concrete Tetrahedron1.7 Problems2 Formal Power Series 2.1 Basic Facts and Definitions2.2 Differentiation and Division2.3 Sequences of Power Series2.4 The Transfer Principle2.5 Multivariate Power Series2.6 Truncated Power Series2.7 Problems3 Polynomials3.1 Polynomials as Power Series3.2 Polynomials as Sequences3.3 The Tetrahedron for Polynomials3.4 Polynomials as Solutions3.5 Polynomials as Coefficients3.6 Applications3.7 Problems4 C-Finite Sequences4.1 Fibonacci Numbers4.2 Recurrences with Constant Coefficients4.3 Closure Properties4.4 The Tetrahedron for C-finite Sequences4.5 Systems of C-finite Recurrences4.6 Applications4.7 Problems5 Hypergeometric Series5.1 The Binomial Theorem5.2 Basic Facts and Definitions5.3 The Tetrahedron for Hypergeometric Sequences5.4 Indefinite Summation5.5 Definite Summation5.6 Applications5.7 Problems6 Algebraic Functions6.1 Catalan Numbers6.2 Basic Facts and Definitions6.3 Puiseux Series and the Newton Polygon6.4 Closure Properties6.5 The Tetrahedron for Algebraic Functions6.6 Applications6.7 Problems7 Holonomic Sequences and Power Series7.1 Harmonic Numbers7.2 Equations with Polynomial Coefficients7.3 Generalized Series Solutions7.4 Closed Form Solutions7.5 The Tetrahedron for Holonomic Functions7.6 Applications7.7 Problems Appendix A.1 Basic Notions and Notations A.2 Basic Facts from Computer Algebra A.3 A Collection of Formal Power Series Identities A.4 Closure Properties at One Glance A.5 Software A.6 Solutions to Selected Problems A.7 Bibliographic Remarks