# Analyzing the Coefficient of a generating function and its asymptotic

The formula you refer to
$$frac{left(3+2 sqrt{2}right)^n}{2 sqrt{npileft(3 sqrt{2}-4right) } }$$ 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{npileft(3 sqrt{2}-4right) } }times$$
$$Bigg[1-frac{23}{19 left(8+3 sqrt{2}right) n}+frac{2401}{1024 left(113+72 sqrt{2}right) n^2}+Oleft(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)$$

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)^ntag{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}^nbinom{n}{k}[x^k](1+x)^{n+k}tag{2}\ &=[x^0](1+x)^nsum_{k=0}^nbinom{n}{k}left(frac{1+x}{x}right)^ktag{3}\ &=[x^0](1+x)^nleft(1+frac{1+x}{x}right)^ntag{4}\ &=[x^{-1}](1+x)^n(1+2x)^nfrac{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)}cdotfrac{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)qquadqquad 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)^ncdot frac{1}{x^{n+1}}=[y^{-1}]left.frac{1}{left(f(x)cdot y^{prime}(x)right)}right|_{x=g(y)}cdotfrac{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.

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+2sqrt{2}))(z-(3-2sqrt{2}))}} \ = frac{1}{(3-2sqrt{2})^n} (3-2sqrt{2})^n [z^n] frac{1}{sqrt{(z-(3+2sqrt{2}))(z-(3-2sqrt{2}))}} \ = (3+2sqrt{2})^n [z^n] frac{1}{sqrt{((3-2sqrt{2})z-(3+2sqrt{2})) ((3-2sqrt{2})z-(3-2sqrt{2}))}} \ = (3+2sqrt{2})^n [z^n] frac{1}{sqrt{((17-12sqrt{2})z-1) (z-1)}} \ = (3+2sqrt{2})^n [z^n] frac{1}{sqrt{(1-(17-12sqrt{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-12sqrt{2})times 1}} = frac{1}{sqrt{12sqrt{2}-16}} = frac{1}{2sqrt{3sqrt{2}-4}}.$$

This gives the asymptotic

$$bbox[5px,border:2px solid #00A000]{ frac{1}{2sqrt{3sqrt{2}-4}} (3+2sqrt{2})^n {n-1/2choose 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-1choose 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}{2sqrt{pi(3sqrt{2}-4)}} frac{1}{sqrt{n}} (3+2sqrt{2})^n.}$$