Closed form or/and asymptotics of a hypergeometric sum Dear mathematicians,
I am a computer scientist wandering in the deep sea of combinatorics and asymptotics to pursue a recent interest in average case analysis of algorithms. In doing so, I designed the following double summation:
$$
\sum_{h = 1}^{n}\sum_{j=0}^{n-h}h{2j+h-1\choose j}{2n - 2j - h\choose n-j},
$$
which, divided by the $n$th Catalan number, yields the statistics I want. Since the variable $j$ occurs in many places, I thought that I could exchange the summations without worrying about the bounds and then work on $h$ instead:
$$
\sum_{j\geq 0}\sum_{h>0}h{(2j-1)+h\choose j}{2(n-j)-h\choose n -j}.
$$
Does anyone know if there is a closed form for
$$
\sum_{h>0}{h}{p+h\choose q}{2r - h \choose r}?
$$
I read the relevant chapter in Concrete Mathematics, to no avail. Perhaps generating functions would help? Anyhow, I would be interested in the main term of the asymptotic expansion of the original double summation.
Thanks for reading me.
 A: For your sequence
s:=[0, 1, 7, 39, 198, 955, 4458, 20342, 91276, 404307, 1772610, 7707106, 33278292, 142853854, 610170148, 2594956620, 10994256152, 46425048451, 195456931506, 820725032042, 3438011713540]

I use with(gfun) in Maple and then guessgf(s, x) to find out that the generating function for your sequence is
$$
\frac{x(1+\sqrt{1-4x})}{2(1-4x)^2}.
$$
This isn't now hard to establish rigorously by verifying that your double sum satisfies a polynomial recurrence (a multivariate version of the Gosper-Zeilberger creative telescoping).
A: Your final sum (according to Mathematica) is:
Binomial[1 + p, q] Binomial[-1 + 2 r,  r] HypergeometricPFQ[{2, 2 + p, 1 - r}, {2 + p - q, 1 - 2 r}, 1]
The original double summation returns a fairly disgusting expression which might, nevertheless, be asymptotically amenable (since "DifferenceRoot" is the solution of a difference equation).
um[h*DifferenceRoot[Function[{[FormalY], [FormalN]}, 
     {-((2*[FormalN] + h)(1 + 2[FormalN] + h)([FormalN] + h - n)(-[FormalN] + n)[FormalY][[FormalN]]) + 
        (-2[FormalN]^2 - 8*[FormalN]^3 - 8*[FormalN]^4 - 3*[FormalN]h - 14[FormalN]^2*h - 16*[FormalN]^3*h - h^2 - 
          7*[FormalN]h^2 - 10[FormalN]^2*h^2 - h^3 - 2*[FormalN]h^3 + 2[FormalN]n + 14[FormalN]^2*n + 
          16*[FormalN]^3*n + 2*h*n + 18*[FormalN]*h*n + 24*[FormalN]^2*h*n + 5*h^2*n + 10*[FormalN]*h^2*n + 
          h^3*n - 6*[FormalN]n^2 - 8[FormalN]^2*n^2 - 5*h*n^2 - 8*[FormalN]*h*n^2 - h^2*n^2)*
         [FormalY][1 + [FormalN]] + (1 + [FormalN])([FormalN] + h)(2*[FormalN] + h - 2*n)(1 + 2[FormalN] + h - 2*n)*
         [FormalY][2 + [FormalN]] == 0, [FormalY][0] == 0, [FormalY][1] == Binomial[-h + 2*n, n]}]][
   1 - h + n], {h, 1, n}]
