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

Having some work done, here is a refined version of my initial question. For integer $m>0$ and $0\le q\le m$, consider the sum $$ S(m,q) = \sum_{i=0}^{m-q} \binom{m}{i} \binom{m-i}{q}^2. $$ I want to understand the behavior (as $m$ grows) of the quantity $$ \sigma(m) = \max_{0\le q\le m} \binom{m}{q}^{-1} S(m,q). $$

One can get pretty good estimates simply observing that \begin{align*} \sum_{q=0}^m \binom{m}{q}^{-1} S(m,q) &= \sum_{q=0}^m \sum_{i=0}^{m-q} \frac{(m-i)!(m-q)!}{i!q!((m-i-q)!)^2} \\ &= \sum_{i+j\le m} \frac{(m-i)!(m-j)!}{i!j!((m-i-j)!)^2}. \end{align*} The right-hand side turns out to be a well-known sequence (OEIS A001906), asymptotically equal to $C\phi^{2m}$, with $\phi=(1+\sqrt5)/2$ and $C=\phi^2/\sqrt 5$. As a result, $$ \frac{(C+o(1))}m \phi^{2m}\le \sigma(m) \le (C+o(1))\,\phi^{2m}. $$ So, ultimately, my question is: What is the largest exponent, say $\tau$, such that $$ \sigma(m) < \frac{K}{m^\tau} \phi^{2m} $$ (with $K=K(\tau)$)?

share|improve this question
2  
Perhaps you can use Stirling's Formula: $n! \sim {\sqrt {2 \pi n}}\left({\frac ne}\right)^{n}$ for large $n$. –  Tim de Laat Feb 25 at 20:56
4  
It feels like I've seen the title "Estimating a sum involving binomial coefficients" on six other questions on this forum alone. In any case, break the trend! You are allowed to add things like ${\binom{n-k}{k}}^2$ to the title. –  The Masked Avenger Feb 25 at 21:15
5  
I think you should be able to use Laplace's method. Find the maximum term as something like $3/4 m - 1/2 q - 1/4 \sqrt{m^2+4mq-4q^2}$. Use Stirling's formula and estimate the second derivative of the logarithm of the terms there. Approximate the sum as a Gaussian whose logarithm has the same max and second derivative. –  Douglas Zare Feb 26 at 5:11
    
Your refined version has different ranges for q in S and sigma. Please resolve. –  The Masked Avenger Feb 27 at 16:39
    
Resolved - but this was a formal problem only, for the values of $S(m,q)$ for $q=0$ and also for $q>m/2$ are small, anyway. –  W-t-P Feb 27 at 16:47

3 Answers 3

The "saddlepoint" method works in general for this kind of sums: Using Stirling's formula, compute the value of $i$ giving maximal contributions and approximate contributions around the maximum with a suitably rescaled Gaussian (in order to have the correct maximum and the correct "second derivative" at the maximum). Replacing the summation by integration (over $\mathbb R$) of the Gaussian approximation gives the correct asymptotics under mild hypotheses.

Variation: Sometimes the maximum occurs at the "boundary". The method can then be adapted (but the integral is then essentially over a halfline).

Probably a good reference for this is "Analytic combinatorics" by Flajolet and Sedgewick.

share|improve this answer
    
Sorry, I did overlook Douglas Zares comment: Laplace and saddlepoint are of course the same thing. –  Roland Bacher Feb 26 at 20:17
    
Thank you (and sorry for being unable to up-vote your reply, not having enough reputation). This should work, but somehow I hoped, and still hope, that there should be some magic trick to avoid heavy computations. –  W-t-P Feb 26 at 20:38

You can rewrite it as $$\frac{(m+q)!}{(m-q)!(q!)^2} \sum_{0\leq i \leq m-q} \frac{\binom{m}{i+q}\binom{m-q}{i}}{\binom{m+q}{i+q}}$$, but if W-Z gives a hypergeometric result as in Dima Pasechnik's answer, I doubt this will give you a better basis for estimation.

share|improve this answer
    
Taking another look, it seems many of the terms of the sum are less than 1, so it might be worth exploring. –  The Masked Avenger Feb 27 at 5:40
    
Preliminary (and likely error-prone) fiddling gives $\frac{(2m-q)^q(4m)^{m-q}}{(2m+q)^m}$ as an upper bound for the sum. I suspect the lower bound won't be too different. –  The Masked Avenger Feb 27 at 5:56
    
You mean, an upper bound for the original sum, or for your sum (to be multiplied by $(m+1)!/((m-q)!(q!)^2)$? –  W-t-P Feb 27 at 10:15
    
In both comments I mean the sum I wrote. I am hoping the factor in front is (up to a small multiplicative adjustment) an estimate for your sum. –  The Masked Avenger Feb 27 at 15:06
    
Your sum is certainly hypergeometric too, but it is the ordinary, aka Gaussian, one, i.e. $ _2F_1(q-m, q-m; -m; -1)$, (if I got it right), and there is a lot of stuff known about them, e.g. explicit integral representations. Should be routine to compute an asymptotic using the latter. –  Dima Pasechnik Mar 6 at 11:10

$S(m,q)$ is a hypergeometric function (you have take the upper limit of the sum $\infty$, as terms for $i$ bigger than $m-q$ will all vanish); a "standard" method would be to find it explicitly, and then to use a representation of it by an integral, which can be estimated by methods from asymptotic analysis.

EDIT: I am referring to the standard technique to identify a hypergeometric series explained in e.g. Chapter 3 of the book "A=B" by Petkovsek, Wilf, and Zeilberger.

Using it you will be able to write $$ S(m,q)=\binom{m}{q}^2 \ _3F_0(-m,q-m,q-m;-;\frac{-1}{(q+1)^2}). $$

share|improve this answer
    
Thanks for replying, but I guess if I knew how to compute $S(m,q)$ explicitly, I would not be asking this question... –  W-t-P Feb 26 at 6:29
    
see my edit in the answer –  Dima Pasechnik Feb 26 at 19:56
    
Thank you for the explanation (and please, see also my comment to Roland Bacher's answer). –  W-t-P Feb 26 at 20:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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