Skip to main content
2 of 3
added 676 characters in body; edited title
W-t-P
  • 550
  • 2
  • 9

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<q<m/2$, 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)$)?

W-t-P
  • 550
  • 2
  • 9