Analytic Combinatorics/Asymptotic Analysis

Introduction In this chapter, we give a more precise definition of what we mean when we say we want to find estimates of coefficients. This is the subject called asymptotic analysis. We define a few concepts which we use to define our two basic ideas: asymptotic equality and asymptotic series. Limit We say that a function has a limit equal to as approaches , in symbols if for each there exists a such that if is within of then is within of , in symbols We often express this in terms of our coefficients as approaches infinity meaning for each there exists an such that if then . Big O We make use of the "Big O" notation. which means there exists positive real numbers such that if : Alternatively, we can say that for positive integer , meaning there exists a positive real number and positive integer such that: Little o We make use of the "little o" notation. which means It also means for each there exists such thatFlajolet and Odlyzko 1990, pp. 8. a fact we will use in the proof. Asymptotic equality We will make use of the asymptotic equality which means This allows us to use as an estimate of as gets closer to . For example, we often present results of the form which means, for large , becomes a good estimate of . It is also useful to note Asymptotic series If we can express a function in terms of an infinite series of functions such that in the form then we say we have an asymptotic series or asymptotic expansion of .de Bruijn 1981, pp. 11. Notes References De Bruijn N.G. Asymptotic Methods in Analysis Dover Publications 1981 Flajolet Philippe Odlyzko Andrew Singularity analysis of generating functions 1990 SIAM Journal on Discrete Mathematics 1990 3 http://www.dtc.umn.edu/~odlyzko/doc/arch/singularity.anal.pdf