Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
Check out A=B by Petkovsek, Wilf, and Zeilberger. –  Steve Huntsman Aug 30 '11 at 13:32
    
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. –  user20657 Jan 17 '12 at 4:53
    
Exact value of this sum is n*2^(2*n-3) + n/4*binomial(2*n,n) –  Vaclav Kotesovec Dec 4 '13 at 22:58

2 Answers 2

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

share|improve this answer

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

share|improve this answer
    
Igor: In view of tackling this kind of questions, would you recommend me to get a license for Maple or Mathematica? –  user17504 Aug 31 '11 at 8:11
    
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. –  Brendan McKay Aug 31 '11 at 9:52

protected by Community Dec 4 '13 at 23:14

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.