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

## 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 .

Finally,

- 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 :

Therefore:

### 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]}:

and

Therefore:

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]

- ↑ Lang 1999, pp. 53-54.
- ↑ Lang 1999, pp. 54.
- ↑ Stroud 2001, pp. 765.
- ↑ Stroud 2003, pp. 916. Wilf 2006, pp. 50-51.
- ↑ Lang 1999, pp. 55.
- ↑ Wilf 2006, pp. 52.
- ↑ Wilf 2006, pp. 48-52.
- ↑ Lang 1999, pp. 55-56.
- ↑ Stroud 2003, pp. 914.
- ↑ See Wilf 2006, pp. 49.
- ↑ Lang 1999, pp. 55.
- ↑ Lang 1999, pp. 56.
- ↑ This does not prove the case when .
- ↑ Stroud 2003, pp. 863.
- ↑ Lang 1999, pp. 69.
- ↑ Lang 1999, pp. 116-117.
- ↑ Titchmarsh 1939, pp. 80-81.
- ↑ Titchmarsh 1939, pp. 84.
- ↑ Titchmarsh 1939, pp. 84.
- ↑ 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.