Estimating a sum involving binomial coefficients [refined]

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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