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)$$

Have a look here for more information.

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.}$$

Leave a Comment