Question

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.

Answer 1

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}]

Answer 2

@Steve and Igor: In view of tackling this kind of questions, would you recommend me to get a license for Maple or Mathematica?

Answer 3

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

Answer 4

I think you want to read the book A=B by Marko Petkovsek, Herbert Wilf and Doron Zeilberger:

http://www.math.upenn.edu/~wilf/AeqB.html

It explains how to do this stuff algorithmically and is very readable.