Let $m>n$ be positive integers. Consider the following sum: \begin{equation} S(m,n)=\sum_{k=0}^n F_{k+1} \frac{{m-1\choose{k}} {n-1\choose{k}}}{ {m+n-1\choose{2k+1}} {2k\choose{k}}}, \end{equation} where $F_k$ denotes the $k$th Fibonacci number. I would like to understand how $S(m,n)$ varies as a function of $m$ and $n$, and possibly upper/lower bound $S(m,n)$ in terms of an explicit function of $m,n$ (as opposed to a series sum).

## 1 Answer

First notice that $$\frac{{m-1\choose{k}} {n-1\choose{k}}}{ {m+n-1\choose{2k+1}} {2k\choose{k}}} = \frac{(m-1)!(n-1)!(m+n-2-2k)!}{(2k+1)(n-1-k)!(m-1-k)!(m+n-1)!} = \frac{(2k+1)\binom{m+n-2-2k}{n-1-k}}{(m+n-1)\binom{m+n-2}{n-1}}.$$ Then $\binom{m+n-2-2k}{n-1-k}$ can be expressed as $$\binom{m+n-2-2k}{n-1-k}=[x^{n-1-k}]\ \frac{1}{\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^{m-n},$$ where $[x^d]$ is the operator taking the coefficient of $x^d$.

Similarly we can express $(2k+1)F_{k+1}$ as $$(2k+1)F_{k+1}=[x^{2k}]\ \frac{\partial}{\partial x}\frac{x}{1-x^2-x^4} = [x^{2k}]\ \frac{1+x^2+3x^4}{(1-x^2-x^4)^2} = [x^k]\ \frac{1+x+3x^2}{(1-x-x^2)^2}.$$ Hence, $$S(m,n) = \frac{1}{(m+n-1)\binom{m+n-2}{n-1}}\cdot [x^{n-1}]\ \frac{1+x+3x^2}{(1-x-x^2)^2\sqrt{1-4x}}\left(\frac{1-\sqrt{1-4x}}{2x}\right)^{m-n}$$ $$=\frac{1}{(m+n-1)\binom{m+n-2}{n-1}}\cdot [y^{n-1}]\ \frac{1+y+2y^2-6y^3+3y^4}{(1-y+2y^3-y^4)^2(1-y)^m},$$ where the latter expression is obtained with Lagrange inversion. The asymptotic of the coefficients of this generating function can now be obtained with the standard methods.