Analyzing the Coefficient of a generating function and its asymptotic

The generating function $\sum_{n\geq 0} D(n) x^n = \frac{1}{\sqrt{1-6x+x^2}}$ is the gf of the Delannoy number.

See last paragraph in https://en.wikipedia.org/wiki/Delannoy_number

In this link, they mentioned that the coefficient of this gf is $D(n) = \sum_{k=0}^{n} {n \choose k} { n+k \choose k}$.

My question is how can this coefficient be calculated/extracted from its gf.And how they conclude that it behaves asymptotically as

${\displaystyle D(n)={\frac {c\,\alpha ^{n}}{\sqrt {n}}}\,(1+O(n^{-1}))}$

where $\alpha =3+2{\sqrt {2}}\approx 5.828$

and

$c=(4\pi (3{\sqrt {2}}-4))^{-1/2}\approx 0.5727$.

How to calculate/extract $D(n)$ from its gf and how to analyze it asymptotically then? Is that possible to do that with a direct calculations?

Edit I tried to find the asymptotic of the codfficidnt in the above gf this way:

The gf has two poles: $r_1=3+\sqrt{8}$, $r_2=3-\sqrt{8}$. So the smallest/dominant pole is $r_2=3-\sqrt{8}$. We can write the gf as: $A(x)=1/ \sqrt{r_2-x} * 1/ \sqrt{r_1-x}$ Then A(x) behaves as:

$1/ \sqrt {r_1-r_2} * 1/ \sqrt{r_2-x}= 1/ \sqrt {2 * 8^{1/4}} * \sum_{n\geq 0} {-1/2 \choose n} (-1)^n (r_1)^{n+1}x^n$ Here I used the expansion's formula of $(1+x)^a$ for $a=-1/2$ and $x=-x/r_2$. So the coefficient behaves asymptotically as: $1/ \sqrt 2 * 1/ 8^{1/4} * (3+\sqrt 8)^{n+1/2} {-1/2 \choose n} (-1)^n$.

We can simplify it more, by using the asymptotic of ${-1/2 \choose n}$.

Is that approach fine?

Solution 1:

For the asymptotics we use the Wilf text, Theorem 5.3.1 (page 179) (Darboux) as suggested in the comments. We seek the asymptotics of

$$[z^n] \frac{1}{\sqrt{1-6z+z^2}} = [z^n] \frac{1}{\sqrt{(z-(3+2\sqrt{2}))(z-(3-2\sqrt{2}))}} \\ = \frac{1}{(3-2\sqrt{2})^n} (3-2\sqrt{2})^n [z^n] \frac{1}{\sqrt{(z-(3+2\sqrt{2}))(z-(3-2\sqrt{2}))}} \\ = (3+2\sqrt{2})^n [z^n] \frac{1}{\sqrt{((3-2\sqrt{2})z-(3+2\sqrt{2})) ((3-2\sqrt{2})z-(3-2\sqrt{2}))}} \\ = (3+2\sqrt{2})^n [z^n] \frac{1}{\sqrt{((17-12\sqrt{2})z-1) (z-1)}} \\ = (3+2\sqrt{2})^n [z^n] \frac{1}{\sqrt{(1-(17-12\sqrt{2})z) (1-z)}}.$$

Now here we have one as the dominant singularity on the circle of convergence and the theorem applies, taking the parameter $\beta = -1/2.$ Expanding the term containing the subdominant singularity around one we get for the first (constant) term

$$\frac{1}{\sqrt{1-(17-12\sqrt{2})\times 1}} = \frac{1}{\sqrt{12\sqrt{2}-16}} = \frac{1}{2\sqrt{3\sqrt{2}-4}}.$$

This gives the asymptotic

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2\sqrt{3\sqrt{2}-4}} (3+2\sqrt{2})^n {n-1/2\choose n}.}$$

The Wilf text gives $O(n^{-3/2})$ for the error in this approximation, in sync with Wikipedia.

Wilf quotes on the same page an asymptotic for the remaining binomial coefficient namely

$${n-\alpha-1\choose n} \sim \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}$$

with $\alpha$ not a nonnegative integer. In the present case we have $\alpha = -1/2$ so we obtain

$$\frac{1}{\sqrt{n}} \frac{1}{\Gamma(1/2)} = \frac{1}{\sqrt{n}} \frac{1}{\sqrt{\pi}}.$$

This gives the form from the Wikipedia entry which is

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2\sqrt{\pi(3\sqrt{2}-4)}} \frac{1}{\sqrt{n}} (3+2\sqrt{2})^n.}$$

Solution 2:

The formula you refer to $$\frac{\left(3+2 \sqrt{2}\right)^n}{2 \sqrt{n\pi\left(3 \sqrt{2}-4\right) } }$$ is an asymptotics.

Let $n=10^k$ and computing the logarithms of these monstrous numbers $$\left( \begin{array}{ccc} k & \text{approximation} & \text{exact} \\ 1 & 15.91875383 & 15.90706013 \\ 2 & 173.4147070 & 173.4135332 \\ 3 & 1758.735871 & 1758.735754 \\ 4 & 17622.30914 & 17622.30913 \\ 5 & 176268.4035 & 176268.4035 \end{array} \right)$$ However, even for small values of $n$, it does not seems too bad $$\left( \begin{array}{ccc} k & \text{approximation} & \text{exact} \\ 1 & 3 & 3 \\ 2 & 14 & 13 \\ 3 & 65 & 63 \\ 4 & 330 & 321 \\ 5 & 1723 & 1683 \\ 6 & 9165 & 8989 \\ 7 & 49457 & 48639 \\ 8 & 269637 & 265729 \\ 9 & 1481680 & 1462563 \\ 10 & 8192698 & 8097453 \end{array} \right)$$

In fact, you could find here a much better approximation for the central Delannoy numbers

$$\frac{\left(3+2 \sqrt{2}\right)^n}{2 \sqrt{n\pi\left(3 \sqrt{2}-4\right) } }\times $$ $$\Bigg[1-\frac{23}{19 \left(8+3 \sqrt{2}\right) n}+\frac{2401}{1024 \left(113+72 \sqrt{2}\right) n^2}+O\left(\frac{1}{n^3}\right) \Bigg]$$

For $n=10$, this would give $8112585$

Edit

In fact, there several definitions and in particular $P_n(3)$ (Legendre polynomials). I suggest that you have look at @Zurab Silagadze's anwer to this question (make $x=\cosh ^{-1}(3)$).

Another definition of $D_n$ is $$D(n) = \sum_{k=0}^{n} {n \choose k} { n+k \choose k}=\, _2F_1(-n,n+1;1;-1)=P_n(3)$$

Have a look here for more information.

Solution 3:

We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series. This way we can write for instance \begin{align*} \binom{n}{k}=[x^k](1+x)^n\tag{1} \end{align*}

We obtain \begin{align*} \color{blue}{\sum_{k=0}^n}&\color{blue}{\binom{n}{k}\binom{n+k}{k}}\\ &=\sum_{k=0}^n\binom{n}{k}[x^k](1+x)^{n+k}\tag{2}\\ &=[x^0](1+x)^n\sum_{k=0}^n\binom{n}{k}\left(\frac{1+x}{x}\right)^k\tag{3}\\ &=[x^0](1+x)^n\left(1+\frac{1+x}{x}\right)^n\tag{4}\\ &=[x^{-1}](1+x)^n(1+2x)^n\frac{1}{x^{n+1}}\tag{5}\\ &=[y^{-1}]\left.\frac{1}{(1+x)(1+2x)\,\frac{1-2x^2}{(1+x)^2(1+2x)^2}}\right|_{x=g(y)}\cdot\frac{1}{y^{n+1}}\tag{6}\\ &=[y^n]\left.\frac{(1+x)(1+2x)}{1-2x^2}\right|_{x=g(y)}\tag{7}\\ &\,\,\color{blue}{=[y^n]\frac{1}{\sqrt{1-6y+y^2}}}\tag{8}\\ \end{align*} and the claim follows.

Comment:

• In (2) we use the coefficient of operator according to (1).

• In (3) we use the linearity of the coefficient of operator and apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.

• In (4) we apply the binomial theorem.

• In (5) we prepare for the substitution rule which is the essence of this derivation.

• In (6) we use the substitution rule (Rule 5, one-dimensional case) from section 1.2.2 of G. P. Egorychev's Classic: Integral Representation and the Computation of Combinatorial Sums. Here we have \begin{align*} f(x)=(1+x)(1+2x)\qquad\qquad y(x)&=\frac{x}{f(x)}=\frac{x}{(1+x)(1+2x)}\tag{9}\\ y^{\prime}(x)&=\frac{1-2x^2}{(1+x)^2(1+2x)^2} \end{align*} and apply the substitution rule: \begin{align*} [x^{-1}]f(x)^n\cdot \frac{1}{x^{n+1}}=[y^{-1}]\left.\frac{1}{\left(f(x)\cdot y^{\prime}(x)\right)}\right|_{x=g(y)}\cdot\frac{1}{y^{n+1}} \end{align*} where $x=g(y)$ is the inverted function given by (9).

• In (7) we do a simplification and apply the rule as we did in (3).

• In (8) we note that with $y(x)=\frac{x}{(1+x)(1+2x)}$ we obtain: \begin{align*} 1-6y+y^2&=1-\frac{6x}{(1+x)(1+2x)}+\frac{x^2}{(1+x)^2(1+2x)^2}\\ &=\frac{(1+x)^2(1+2x)^2-6x(1+x)(1+2x)+x^2}{(1+x)^2(1+2x)^2}\\ &=\frac{(2x^2-1)^2}{(1+x)^2(1+2x)^2}\\ \frac{1}{\sqrt{1-6y+y^2}}&=\frac{(1+x)(1+2x)}{1-2x^2} \end{align*}

Notes:

• Another approach of the asymptotic coefficient expansion of $\frac{1}{\sqrt{1-6x+x^2}}$ can be found in this answer.

• A somewhat more demanding application of the substitution rule (two-dimensional case) is given in this answer.