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

  • 2
    $\begingroup$ Perhaps you can use Stirling's Formula: $n! \sim {\sqrt {2 \pi n}}\left({\frac ne}\right)^{n}$ for large $n$. $\endgroup$ – Tim de Laat Feb 25 '14 at 20:56
  • 4
    $\begingroup$ 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. $\endgroup$ – The Masked Avenger Feb 25 '14 at 21:15
  • 5
    $\begingroup$ 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. $\endgroup$ – Douglas Zare Feb 26 '14 at 5:11
  • $\begingroup$ Your refined version has different ranges for q in S and sigma. Please resolve. $\endgroup$ – The Masked Avenger Feb 27 '14 at 16:39
  • $\begingroup$ 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. $\endgroup$ – W-t-P Feb 27 '14 at 16:47

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.

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

  • $\begingroup$ Taking another look, it seems many of the terms of the sum are less than 1, so it might be worth exploring. $\endgroup$ – The Masked Avenger Feb 27 '14 at 5:40
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Feb 27 '14 at 5:56
  • $\begingroup$ You mean, an upper bound for the original sum, or for your sum (to be multiplied by $(m+1)!/((m-q)!(q!)^2)$? $\endgroup$ – W-t-P Feb 27 '14 at 10:15
  • $\begingroup$ 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. $\endgroup$ – The Masked Avenger Feb 27 '14 at 15:06
  • $\begingroup$ 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. $\endgroup$ – 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}). $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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