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

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
### Limit superior

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_{n}\}$.
A point of accumulation of a sequence is a number $t$ such that, given $\epsilon >0$, there are infinitely many $n$ such that
    $|a_{n}-t|<\epsilon$.
For example, the sequence of coefficients of ${\frac {1}{1-z}}$ ($\{1,1,1,\cdots \}$) has point of accumulation $1$. $e^{z}$ ($\{1,{\frac {1}{2!}},{\frac {1}{3!}},\cdots \}$) has point of accumulation $0$. ${\frac {1}{1-z^{2}}}$ ($\{1,0,1,0,\cdots \}$) has two points of accumulation, $0$ and $1$.
One useful property of a sequence of numbers is its limit superior, written $\limsup a_{n}$. This is the least upper bound of the set of points of accumulation of the sequence $\{a_{n}\}$.
In our above examples, these would be $1$, $0$ and $1$ respectively.

### Convergence

$f(z)$ is said to converge if its series expansion $\sum a_{n}z^{n}$ equals a finite value.
It may only do so for particular values of $z$. There are various tests for whether or not a series converges and for which values of $z$.
For example, ${\frac {1}{1-z}}$ has series expansion $\sum z^{n}$. We can test this series for convergence with the D'Alembert's ratio test which states that the series converges if
    $\lim _{n\to \infty }{\frac {a_{n+1}}{a_{n}}}<1$
In our example, the ratio is ${\frac {z^{n+1}}{z^{n}}}$ which is only less than $1$ if $|z|<1$. Therefore, the series converges for values less than $1$.
The radius of convergence of $f(z)$ is the value $z_{0}$ such that for $|z|<z_{0}$ the series expansion converges.
In our example, the radius of convergence of ${\frac {1}{1-z}}$ is $1$.
It should be noted that the radius of convergence is equal to the smallest singularity of a function. We will read about singularities later.

### Theorem

If $f(z)=\sum a_{n}z^{n}$ and $R$ its radius of convergence then:
    ${\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}$
One consequence of this theorem is:
    $a_{n}\leq \left({\frac {1}{R}}+\epsilon \right)^{n}$ (for all $\epsilon >0$ and sufficiently large $n$)

### Proof

Proof due to Wilf and Lang.
The radius of convergence $R$ of a function $f(z)$ means that if $|z|<R$ then $f(z)\neq \infty$.
Take $f(z)=\sum a_{n}z^{n}$, $R$ its radius of convergence and $t=\limsup _{n\to \infty }|a_{n}|^{1/n}$. By definition of $\limsup$, for all but a finite number of $n$
    $|a_{n}|\leq (t+\epsilon )^{n}$.
$f(z)$ does not converge if $|z|\geq {\frac {1}{(t+\epsilon )}}$ (because otherwise ${\frac {a_{n+1}z^{n+1}}{a_{n}z^{n}}}>1$ for all $n$ and so diverges by D'Alembert's ratio test), therefore $R\geq {\frac {1}{(t+\epsilon )}}$.
By definition of $\limsup$, there exist infinitely many $n$
    $|a_{n}|\geq (t-\epsilon )^{n}$.
$f(z)$ does not converge if $|z|={\frac {1}{(t-\epsilon )}}$, therefore $R\leq {\frac {1}{(t-\epsilon )}}$.
If $R\geq {\frac {1}{(t+\epsilon )}}$ and $R\leq {\frac {1}{(t-\epsilon )}}$ then $R={\frac {1}{t}}$ and ${\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}$.
Now, we prove the consequence of the theorem.
If, ${\frac {1}{R}}=\limsup _{n\to \infty }|a_{n}|^{1/n}$ and, by definition of $\limsup$, for all but a finite number of $n$
    $|a_{n}|\leq \left({\frac {1}{R}}+\epsilon \right)^{n}$
and there exist infinitely many $n$
    $|a_{n}|\geq \left({\frac {1}{R}}-\epsilon \right)^{n}$.

## Cauchy's inequality
### Complex numbers

A complex number is a number $z=x+iy$ where $x$ and $y$ are both real numbers and $i$ is the imaginary unit where $i^{2}=-1$. $x$ is called the real component and $y$ the imaginary component (even though $y$ is itself a real number).

### Contour integration

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:
    $\int _{C}f(z)dz$
where $C$ 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

A function $f(z)$ is analytic at a point $z_{0}$ if it is defined, single-valued and has a derivative at every point at and around $z_{0}$.
We say a function $f(z)$ is analytic on a set of points $U$ if it is analytic at every point of $U$.
One property of an analytic function is that when performing contour integration on a closed contour $C$ we can continuously deform the contour $C$ into another closed contour $C^{'}$ without changing the value of the integral (as long as in deforming the contour we do not pass through any singularities).

### Cauchy's integral formula

Cauchy's integral formula states:
    $f(z_{0})={\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{z-z_{0}}}$
where $C$ is a contour, $z_{0}$ is a point inside $C$ and $f(z)$ is analytic on and inside the contour.
Proof: Because $f(z)$ is analytic, we can replace the integral around $C$ with a contour $\gamma$ with centre $z_{0}$ and radius $\rho$
    ${\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{z-z_{0}}}={\frac {1}{2\pi i}}\int _{\gamma }f(z){\frac {dz}{z-z_{0}}}$
As $f(z)$ is analytic it is also continuous. This means for any $\epsilon >0$ there exists a $\delta >0$ such that $|z-z_{0}|<\delta \implies |f(z)-f(z_{0})|<\epsilon$. We can do this by setting $\rho \leq \delta$.
    $\int _{\gamma }f(z){\frac {dz}{z-z_{0}}}=f(z_{0})\int _{\gamma }{\frac {dz}{z-z_{0}}}+\int _{\gamma }{\frac {f(z)-f(z_{0})}{z-z_{0}}}dz$
    $f(z_{0})\int _{\gamma }{\frac {dz}{z-z_{0}}}=2\pi if(z_{0})$
    $\int _{\gamma }{\frac {f(z)-f(z_{0})}{z-z_{0}}}dz\leq {\frac {\epsilon }{\rho }}2\pi \rho =2\pi \epsilon$
Finally,
    ${\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{z-z_{0}}}={\frac {1}{2\pi i}}\int _{\gamma }f(z){\frac {dz}{z-z_{0}}}={\frac {1}{2\pi i}}(2\pi if(z_{0})+2\pi \epsilon )=f(z_{0})$ as $\epsilon \to 0$.

### Taylor series

If $f(z)$ is analytic inside and on a contour $C$, the Taylor series expansion of $f(z)$ around the point $z_{0}$ inside $C$:
    $f(z)=f(z_{0})+f'(z_{0})(z-z_{0})+{\frac {f''(z_{0})(z-z_{0})^{2}}{2!}}+\cdots$

### Cauchy's coefficient formula

Cauchy's coefficient formula states that:
    $a_{n}={\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{z^{n+1}}}$
Proof: Cauchy's integral formula states:
    $f(z_{0})={\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{z-z_{0}}}$
If you differentiate both sides with respect to $z_{0}$ $n$ times, you get:
    ${\frac {f^{(n)}(z_{0})}{n!}}={\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{(z-z_{0})^{n+1}}}$
The Taylor series expansion of $f(z)$ around $0$:
    $f(z)=f(0)+f'(0)z+{\frac {f''(0)z^{2}}{2!}}+\cdots$
Therefore:
    $a_{n}={\frac {f^{(n)}(0)}{n!}}={\frac {1}{2\pi i}}\int _{C}f(z){\frac {dz}{z^{n+1}}}$

### Theorem

Theorem due to Titchmarsh.
If $R$ is the radius of convergence of $f(z)$, for all $n\geq 0$ and $0<r<R$
    $|a_{n}|\leq {\frac {\max _{|z|=r}|f(z)|}{r^{n}}}$

### Proof

Proof due to Titchmarsh.
By Cauchy's coefficient formula:
    $a_{n}={\frac {1}{2\pi i}}\int _{|z|=r}f(z){\frac {dz}{z^{n+1}}}$
We have:
    $|a_{n}|=\left|{\frac {1}{2\pi i}}\int _{|z|=r}f(z){\frac {dz}{z^{n+1}}}\right|={\frac {1}{2\pi i}}\int _{|z|=r}|f(z)|{\frac {dz}{z^{n+1}}}$
and
    $\int _{|z|=r}|f(z)|dz\leq \max _{|z|=r}|f(z)|2\pi r$
Therefore:
    $|a_{n}|={\frac {1}{2\pi i}}\int _{|z|=r}|f(z)|{\frac {dz}{z^{n+1}}}\leq {\frac {1}{2\pi }}\max _{|z|=r}|f(z)|{\frac {2\pi r}{r^{n+1}}}={\frac {\max _{|z|=r}|f(z)|}{r^{n}}}$
Pictorially, we are estimating the contour integral by taking $|f(z)|$ always at its maximum around the entire contour, shown by the green ring below.

## Notes

* ↑ 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 $t=0,\infty$.
* ↑ 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

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