3
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ Perhaps you can use Stirling's Formula: $n! \sim {\sqrt {2 \pi n}}\left({\frac ne}\right)^{n}$ for large $n$. $\endgroup$ Feb 25, 2014 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$ Feb 25, 2014 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$ Feb 26, 2014 at 5:11
  • $\begingroup$ Your refined version has different ranges for q in S and sigma. Please resolve. $\endgroup$ Feb 27, 2014 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, 2014 at 16:47

3 Answers 3

3
$\begingroup$

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.

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

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.

$\endgroup$
5
  • $\begingroup$ Taking another look, it seems many of the terms of the sum are less than 1, so it might be worth exploring. $\endgroup$ Feb 27, 2014 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$ Feb 27, 2014 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, 2014 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$ Feb 27, 2014 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$ Mar 6, 2014 at 11:10
1
$\begingroup$

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

$\endgroup$
3
  • $\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, 2014 at 6:29
  • $\begingroup$ see my edit in the answer $\endgroup$ Feb 26, 2014 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, 2014 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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