4
$\begingroup$

I wonder whether it is possible to calculate the folowing sum that involves the Binomial coefficients $$\sum_{k=0}^n \binom{n}{k}^2 \binom{2k}{k} .$$

$\endgroup$
6
  • 7
    $\begingroup$ This is OEIS A002893; there doesn’t seem to be a very nice closed form, but the entry has quite a bit of information. $\endgroup$ Commented Nov 9, 2016 at 14:27
  • 1
    $\begingroup$ it is a hypergeometric series $${\mbox{$_3$F$_2$}(1/2,-n,-n;\,1,1;\,4)}$$ $\endgroup$ Commented Nov 9, 2016 at 14:36
  • $\begingroup$ @BrianM.Scott. Thanks for the link ! When much younger, I have been struggling with this problem. $\endgroup$ Commented Nov 9, 2016 at 15:54
  • $\begingroup$ @Claude: You’re welcome! (OEIS has become one of my favorite resources.) $\endgroup$ Commented Nov 9, 2016 at 16:00
  • 1
    $\begingroup$ @BrianM.Scott. Me too ! But this was so long time ago ... By chance, I still keep an old piece of code in which I found my regression. I have been real glad to see that it was not totally stupid. Cheers. $\endgroup$ Commented Nov 9, 2016 at 16:05

2 Answers 2

7
$\begingroup$

Let $$ a_k=\binom{n}{k}^2\binom{2k}{k} $$ Then, with $k=\frac23n+j$, $$ \begin{align} \log\left(\frac{a_{k+1}}{a_k}\right) &=2\log\left(2\frac{n-k}{k+1}\right)+\log\left(\frac{k+1/2}{k+1}\right)\\ &=2\log\left(\frac{\frac23n-2j}{\frac23n+j+1}\right) +\log\left(\frac{\frac23n+j+\frac12}{\frac23n+j+1}\right)\\ &=-\frac{9j}n+O\!\left(\frac1n\right)\\ \end{align} $$ Therefore, $$ a_k=\color{#C00000}{a_{\frac23n}}\,\color{#009000}{e^{-\frac{9j^2}{2n}+O\left(\frac jn\right)}} $$ Thus, we can estimate $a_{\frac23n}$ using Stirling and sum the exponential using a Riemann Sum to get $$ \begin{align} \sum_{k=0}^n\binom{n}{k}^2\binom{2k}{k} &=\color{#C00000}{\frac32\left(\frac3{2\pi n}\right)^{3/2}9^n}\color{#009000}{\sqrt{n}\int_{-\infty}^\infty e^{-9x^2/2}\,\mathrm{d}x}\left(1+O\!\left(\frac1n\right)\right)\\ &=\bbox[5px,border:2px solid #C0A000]{\frac{3\sqrt3}{4\pi n}\,9^n\left(1+O\!\left(\frac1n\right)\right)} \end{align} $$


A Note About The Error Estimate

Even though the $O\!\left(\frac jn\right)$ in the exponential would normally introduce an error of $O\!\left(\frac1{\sqrt{n}}\right)$, the only terms beyond $-\frac{9j^2}{2n}$ that would contribute an error of $O\!\left(\frac1{\sqrt{n}}\right)$ are the $\frac jn$ and $\frac{j^3}{n^2}$ terms and they are odd and so get cancelled upon integration. This leaves an error of $O\!\left(\frac1n\right)$ which combines with the error for Stirling's Formula.

$\endgroup$
1
  • $\begingroup$ Very interesting approach of the asymptotics, indeed. $\endgroup$ Commented Nov 11, 2016 at 5:56
5
$\begingroup$

Too long for a comment.

If you look at the $OEIS$ link given by Brian M. Scott in his comment, you should notice a very simple and interesting asymptotics provided by Vaclav Kotesovec a few years ago; $$a_n=\sum_{k=0}^n \binom{n}{k}^2 \binom{2k}{k} \sim \frac{3^{2 n+\frac{3}{2}}}{4 \pi n}$$ What is really nice is that, as soon as $n\geq 25$, the relative error is smaller than $1$% and for $n\geq 250$ it becomes smaller than $0.1$%. It would have been very useful to me to know about it earlier.

Since I faced this problem in the past, I had an empirical correlation for the range $10\leq n \leq 1000$; it is $$\log(a_n)=2.19722 n-0.995502 \log (n)-0.906772$$ which extrapolates quite well.

Expanding this beautiful asymptotics, we should get $$\log(a_n)\sim 2.19722 n- \log (n)-0.883106$$

Thanks for having posted this question.

Edit

Later (today), I revisited my previous empirical correlation and arrived to $$\log(a_n)=2.19722 n-0.999963 \log (n)-\frac{0.245931}{n}-0.883315$$ for which all coefficients are very higly significant (as shown below). $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & +2.197220 & 1.84\times 10^{-9} & \{+2.197220,+2.197220\} \\ b & -0.999963 & 8.32\times 10^{-7} & \{-0.999964,-0.999961\} \\ c & -0.883315 &4.26 \times 10^{-6} & \{-0.883323,-0.883306\} \\ d & -0.245931 &4.06\times 10^{-5} & \{-0.246010,-0.245851\} \\ \end{array}$$ For my first old correlation the residual sum of squares was $78\times 10^{-5}$ while for the new one, it dropped to $21\times 10^{-7}$.

Notice that for three of the coefficients, their values are extremely close to those given in the asymptotics.

In other words, we could modify Vaclav Kotesovec's asymptotics to

$$a_n\sim \frac{3^{2 n+\frac{3}{2}}}{4 \pi n} e^{-\frac 1 {4n}}$$ which leads to a relative error smaller than $0.1$% as soon as $n\geq 6$ and smaller than $0.01$% as soon as $n\geq 16$

Even better $$a_n\sim \frac{3^{2 n+\frac{3}{2}} }{4 \pi n}\exp\left({-\frac{17}{67 n}}+\frac{1}{69 n \log (n)}\right)$$ leads to a relative error smaller than $0.1$% as soon as $n\gt 4$ and smaller than $0.01$% as soon as $n\geq 10$.

Update

Please notice that, in a comment, Vaclav Kotesovec kindly provided a very accurate formula $$a_n=\frac{3^{2 n+\frac{3}{2}}}{4 \pi n}\phi(x)$$ where $$\phi(x)=1-\frac{1}{4 n}+\frac{1}{16 n^2}+\frac{1}{32 n^3}+\frac{7}{256 n^4}+\frac{59}{1024 n^5}+\frac{77}{512 n^6}+\frac{437}{1024 n^7}+\frac{90847}{65536 n^8}+\cdots$$ Vaclav Kotesovec just added a new sequence at $OEIS$ (see here).

$\endgroup$
3
  • 1
    $\begingroup$ More precise asymptotic expansion is a(n) ~ 3^(2*n+3/2)/(4*Pi*n) * (1 - 1/(4*n) + 1/(16*n^2) + 1/(32*n^3) + 7/(256*n^4) + 59/(1024*n^5) + 77/(512*n^6) + 437/(1024*n^7) + 90847/(65536*n^8) + ...) $\endgroup$ Commented Nov 10, 2016 at 22:52
  • 1
    $\begingroup$ @VaclavKotesovec. Thank you so much ! $\endgroup$ Commented Nov 11, 2016 at 5:17
  • $\begingroup$ I created a new sequence A274600 in the OEIS. $\endgroup$ Commented Nov 11, 2016 at 8:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .