6
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Check out A=B by Petkovsek, Wilf, and Zeilberger. $\endgroup$ Aug 30, 2011 at 13:32
  • $\begingroup$ I think you want to read the book A=B by Marko Petkovsek, Herbert Wilf and Doron Zeilberger: math.upenn.edu/~wilf/AeqB.html It explains how to do this stuff algorithmically and is very readable. $\endgroup$
    – user20657
    Jan 17, 2012 at 4:53
  • $\begingroup$ Exact value of this sum is n*2^(2*n-3) + n/4*binomial(2*n,n) $\endgroup$ Dec 4, 2013 at 22:58

2 Answers 2

4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Igor: In view of tackling this kind of questions, would you recommend me to get a license for Maple or Mathematica? $\endgroup$
    – user17504
    Aug 31, 2011 at 8:11
  • $\begingroup$ Without an exact expression for the sum, the usual approach is to find the place where the terms are largest, then approximate the nearby terms by a simple function. The maximum point can be identified by taking the ratio of adjacent terms; in this case it is given by the root of a higher degree polynomial, which is unfortunate. If the maximum occurs not close to the boundary of the region, usually the nearby terms have a shape like a two-dimensional gaussian and you can estimate their sum by replacing it by an integral. If the maximum is on the boundary, it could be easier but maybe not. $\endgroup$ Aug 31, 2011 at 9:52