# Estimating a sum involving binomial coefficients [refined]

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)$)?

• 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 '14 at 20:56
• 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 '14 at 21:15
• 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 '14 at 5:11
• Your refined version has different ranges for q in S and sigma. Please resolve. – The Masked Avenger Feb 27 '14 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 '14 at 16:47

## 3 Answers

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.

• Sorry, I did overlook Douglas Zares comment: Laplace and saddlepoint are of course the same thing. – Roland Bacher Feb 26 '14 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 '14 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.

• 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 '14 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 '14 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 '14 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 '14 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 '14 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}).$$

• 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 '14 at 6:29
• see my edit in the answer – Dima Pasechnik Feb 26 '14 at 19:56
• Thank you for the explanation (and please, see also my comment to Roland Bacher's answer). – W-t-P Feb 26 '14 at 20:40