The Concrete Tetrahedron

Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates

verfasst von: Manuel Kauers, Peter Paule

Verlag: Springer Vienna

Buchreihe : Texts & Monographs in Symbolic Computation

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

This is the story about four mathematical concepts which play a great role in many different areas of mathematics. It is a story about symbolic sums, recurrence (difference) equations, generating functions, and asymptotic estimates. In this book, we will study their key features in isolation or in combination, their mastery by paper and pencil or by computer programs, and their application to problems in pure mathematics or to “real world problems”. To begin with, we take a look at a particular “real world problem” and see how sums, recurrence equations, generating functions, and asymptotic estimates may naturally arise in such a context. After having introduced these four main characters of this book informally by seeing them in action, we will then prepare the stage for their detailed study.

Manuel Kauers, Peter Paule

Chapter 2. Formal Power Series

Abstract

This chapter is somewhat different from the other chapters in this book. It contains not many symbolic sums, hardly any recurrence equations, and only few asymptotic estimates. We provide here the algebraic background on which the notion of a generating function rests. The results developed here apply in full generality to all sequences, not just to some limited class of sequences as will be the case in all the following chapters.

Manuel Kauers, Peter Paule

Chapter 3. Polynomials

Abstract

In this chapter we start to study restricted classes of power series. The most simple classes are the most restricted ones, and so we will start with those. The power series considered in this chapter have in common that they all can be described by polynomials. Polynomials are not only interesting as a class in its own right, but they will also be employed as building blocks in the construction of the more elaborate classes that are considered in the following chapters.

Manuel Kauers, Peter Paule

Chapter 4. C-Finite Sequences

Abstract

Polynomial sequences obey certain linear recurrence equations with constant coefficients, as we have seen in the previous chapter. But in general, a sequence satisfying a linear recurrence equation with constant coefficients need not be a polynomial sequence. The solutions to such recurrence equations form a strictly larger class of sequences, the so-called C-finite sequences. This is the class we consider now.

Manuel Kauers, Peter Paule

Chapter 5. Hypergeometric Series

Abstract

Hypergeometric series form a particularly powerful class of series, as they appear in a great variety of different scientific contexts while at the same time allowing a rather simple definition. Popularized by the work of Gauss, hypergeometric series have been intensively studied since the 19th century, and they are still subject of ongoing research. Nowadays, they are also well understood from an algorithmic point of view, and in this chapter, we will see some of the most important algorithms for dealing with them.

Manuel Kauers, Peter Paule

Chapter 6. Algebraic Functions

Abstract

The next station in our tour through various classes of formal power series is the class of algebraic power series. These power series share the property that they can be described as solutions of a polynomial equation. A deep theory has been developed for these power series mainly because of the important role they play in the field of algebraic geometry for locally describing algebraic curves and surfaces in the neighborhood of a specific point. But the significance of algebraic power series is by no means restricted to algebraic geometry. In combinatorics, for example, they turn out to play a prominent role as well, as they do appear as generating functions for a number of important combinatorial objects.

Manuel Kauers, Peter Paule

Chapter 7. Holonomic Sequences and Power Series

Abstract

We are close to the end, but there is one more class that we want to present. This class is much wider than the classes discussed so far. It contains all the classes considered before, as well as many additional objects. It is interesting mainly for two reasons. First, because it covers a great percentage of the most widely used special functions in physics as well as many combinatorial sequences arising in applications. Secondly, because also for this large class there are algorithms for answering the most urging questions about its elements.

Manuel Kauers, Peter Paule

Backmatter

Titel: The Concrete Tetrahedron
verfasst von: Manuel Kauers
Peter Paule
Verlag: Springer Vienna
Electronic ISBN: 978-3-7091-0445-3
Print ISBN: 978-3-7091-0444-6
DOI: https://doi.org/10.1007/978-3-7091-0445-3