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.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Check out A=B by Petkovsek, Wilf, and Zeilberger. $\endgroup$ Commented 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$ Commented 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$ Commented Dec 4, 2013 at 22:58

2 Answers 2

Reset to default
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).

Improve this answer
$\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}]

Improve this answer
$\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$ Commented 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$ Commented Aug 31, 2011 at 9:52

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.