Analytic Combinatorics/Tauberian Theorem


'Tauberian' refers to a class of theorems with many applications. The full scope of Tauberian theorems is too large to cover here.

We prove here only a particular Tauberian theorem due to Hardy, Littlewood and Karamata, which is useful in analytic combinatorics.


Theorem due to Hardy[1].

If   as  , where   and   is a slowly varying function, then   when  .

Bear in mind that if   we can convert it to a General Dirichlet series (without changing the value of the coefficients we are interested in) by the substitution   such that


as  [2].

This gives us


which is the form it is given in Flajolet and Sedgewick 2009, pp. 435.


Proof due to Hardy[3].

If   then this method actually finds the asymptotic estimate of   after which we can find   by   or by finding   in  .

Let   be a step function where  ,   and  [4].


Using integration by parts[5]:


Because  .

If   then


Because when   then   ranges from   to   so   and when   then  .

Lemma 1Edit


as  .

To prove this we need two further lemmas.

Lemma 2Edit


where   is any polynomial and as  .


as   by assumption in the theorem.


by definition of slowly varying function.


Lemma 3Edit

If   is real-valued and Riemann integrable in the open interval   and   then there exist polynomials   and   such that   and


Assume there are continuous functions   and   such that






By the Weierstrass approximation theorem there are polynomials   and   such that   and  . If   and   then   as required by the lemma and


If we can find finite step functions   and   such that   and


Then, we have proven above there are polynomials   and   such that   and


Combining these we can complete the proof of lemma 3:


Going back to the proof of lemma 1


by lemma 2.

Lemma 3 implies that


so that




and finally


By a similar argument, one can prove


Combining both these results we conclude the proof of lemma 1


Putting it all together:




As  . Then, if  



  1. Hardy 1949, pp. 166.
  2. Because   as   which is equivalent to   as  . See De Bruijn 1981, pp. 10 and Hardy 1949, pp. 155.
  3. Hardy 1949, pp. 166-168.
  4. Hardy 1949, pp. 158.
  5. w:Riemann–Stieltjes_integral#Properties
  6. Hardy 1949, pp. 158.
  7. Hardy 1949, pp. 166.
  8. Hardy 1949, pp. 168.
  9. a b Due to the sum rule of integration?
  10. Hardy 1949, pp. 166.
  11. w:Gamma_function#Integral_representations


  • Hardy, G.H. (1949). Divergent Series (1st ed.). Oxford University Press.
  • Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics (PDF). Cambridge University Press.
  • De Bruijn, N.G. (1981). Asymptotic Methods in Analysis. Dover Publications.