Analytic Combinatorics/Cauchy-Hadamard theorem and Cauchy's inequality

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction[edit | edit source]

Two of the most basic means of estimating coefficients of generating functions are the Cauchy-Hadamard theorem and Cauchy's inequality.

We also include some background knowledge which will be useful for future chapters.

Cauchy-Hadamard theorem[edit | edit source]

Limit superior[edit | edit source]

One key concept in analysis is a sequence of numbers. In our case, the sequence of numbers could be the coefficients of the generating function we are interested in, written .

A point of accumulation of a sequence is a number such that, given , there are infinitely many such that[1]


For example, the sequence of coefficients of () has point of accumulation . () has point of accumulation . () has two points of accumulation, and .

One useful property of a sequence of numbers is its limit superior, written . This is the least upper bound of the set of points of accumulation of the sequence [2].

In our above examples, these would be , and respectively.

Convergence[edit | edit source]

is said to converge if its series expansion equals a finite value.

It may only do so for particular values of . There are various tests for whether or not a series converges and for which values of .

For example, has series expansion . We can test this series for convergence with the D'Alembert's ratio test[3] which states that the series converges if

In our example, the ratio is which is only less than if . Therefore, the series converges for values less than .

The radius of convergence of is the value such that for the series expansion converges.

In our example, the radius of convergence of is .

It should be noted that the radius of convergence is equal to the smallest singularity of a function.[4] We will read about singularities later.

Theorem[edit | edit source]

If and its radius of convergence then[5]:

One consequence of this theorem is[6]:

(for all and sufficiently large )

Proof[edit | edit source]

Proof due to Wilf[7] and Lang[8].

The radius of convergence of a function means that if then [9].

Take , its radius of convergence and . By definition of [10], for all but a finite number of


does not converge if (because otherwise for all and so diverges by D'Alembert's ratio test), therefore [11].

By definition of , there exist infinitely many


does not converge if , therefore [12].

If and then and [13].

Now, we prove the consequence of the theorem.

If, and, by definition of , for all but a finite number of

and there exist infinitely many


Examples[edit | edit source]

Cauchy's inequality[edit | edit source]

Complex numbers[edit | edit source]

A complex number is a number where and are both real numbers and is the imaginary unit where . is called the real component and the imaginary component (even though is itself a real number).

Contour integration[edit | edit source]

Because a complex number has two components, real and imaginary, complex integration involves integrating around a curve in the two-dimensional plane. This is called contour integration.

We denote this:

where denotes the contour.

It is not necessary to know how to compute contour integrals in order to understand the later material in this book.

Analytic functions[edit | edit source]

A function is analytic at a point if it is defined, single-valued and has a derivative at every point at and around [14].

We say a function is analytic on a set of points if it is analytic at every point of [15].

One property of an analytic function is that when performing contour integration on a closed contour we can continuously deform the contour into another closed contour without changing the value of the integral (as long as in deforming the contour we do not pass through any singularities)[16].

Cauchy's integral formula[edit | edit source]

Cauchy's integral formula states:[17]

where is a contour, is a point inside and is analytic on and inside the contour.

Proof: Because is analytic, we can replace the integral around with a contour with centre and radius

As is analytic it is also continuous. This means for any there exists a such that . We can do this by setting .


as .

Taylor series[edit | edit source]

If is analytic inside and on a contour , the Taylor series expansion of around the point inside :

Cauchy's coefficient formula[edit | edit source]

Cauchy's coefficient formula states that:

Proof: Cauchy's integral formula states:

If you differentiate both sides with respect to times, you get:

The Taylor series expansion of around :


Theorem[edit | edit source]

Theorem due to Titchmarsh[18].

If is the radius of convergence of , for all and

Proof[edit | edit source]

Proof due to Titchmarsh[19].

By Cauchy's coefficient formula:

We have[20]:



Pictorially, we are estimating the contour integral by taking always at its maximum around the entire contour, shown by the green ring below.

Notes[edit | edit source]

  1. Lang 1999, pp. 53-54.
  2. Lang 1999, pp. 54.
  3. Stroud 2001, pp. 765.
  4. Stroud 2003, pp. 916. Wilf 2006, pp. 50-51.
  5. Lang 1999, pp. 55.
  6. Wilf 2006, pp. 52.
  7. Wilf 2006, pp. 48-52.
  8. Lang 1999, pp. 55-56.
  9. Stroud 2003, pp. 914.
  10. See Wilf 2006, pp. 49.
  11. Lang 1999, pp. 55.
  12. Lang 1999, pp. 56.
  13. This does not prove the case when .
  14. Stroud 2003, pp. 863.
  15. Lang 1999, pp. 69.
  16. Lang 1999, pp. 116-117.
  17. Titchmarsh 1939, pp. 80-81.
  18. Titchmarsh 1939, pp. 84.
  19. Titchmarsh 1939, pp. 84.
  20. Titchmarsh 1939, pp. 74.

References[edit | edit source]

  • Lang, Serge (1999). Complex Analysis (4th ed.). Springer Science+Business Media, LLC.
  • Stroud, K. A. (2003). Advanced Engineering Mathematics (4th ed.). Palgrave Macmillan.
  • Stroud, K. A. (2001). Engineering Mathematics (5th ed.). Palgrave Macmillan.
  • Titchmarsh, E. C. (1939). The Theory of Functions (2nd ed.). Oxford University Press.
  • Wilf, Herbert S. (2006). Generatingfunctionology (PDF) (3rd ed.). A K Peters, Ltd.