I am looking for a closed form for the following sum: $$\sum_{p=0}^{k} \left( \begin{matrix} n \\ p+1 \end{matrix} \right) \left( \begin{matrix} k \\ p \end{matrix} \right) 4^p = \;\;???$$ I have tried to expand: $$(1+2x)^n \cdot \left( 2+\frac{1}{x}\right)^k$$ without success. Any ideas are welcome!
Thank you
Please allow me to reserve the use of $k$ as an index and rewrite your sum as $$ \eqalign{ &S = \sum\limits_{k = 0}^m {\left( \matrix{ n \cr k + 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = \sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {\left( \matrix{ n \cr k + 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {\left( \matrix{ n \cr n - k - 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } \cr} $$
A first approach is to consider that the double sum of the binomial correlation is $$ \eqalign{ & S = \sum\limits_{k = 0}^m {\left( \matrix{ n \cr k + 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = \sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {\left( \matrix{ n \cr k + 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {\left( \matrix{ n \cr n - k - 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } \cr} $$
So that S is the coefficient of $x^{n-1}$ in the binomial $$ S = \left[ {x^{n - 1} } \right]\left( {\left( {1 + 4x} \right)^{\,m} \left( {1 + x} \right)^{\,n} } \right) $$
We can also express the sum directly in terms of the Hypergeometric function as $$ \eqalign{ & S = \sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {\left( \matrix{ n \cr k + 1 \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = \cr & = n\sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {{1 \over {k + 1}}\left( \matrix{ n - 1 \cr k \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = \cr & = n\sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {{1 \over {k + 1}}\left( \matrix{ n - 1 \cr k \cr} \right)\left( \matrix{ m \cr k \cr} \right)4^{\,k} } = n\sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {{{\left( {n - 1} \right)^{\,\underline {\,k\,} } m^{\,\underline {\,k\,} } } \over {\left( {k + 1} \right)!k!}}4^{\,k} } = \cr & = n\sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {{{\left( { - 1} \right)^{\,k} \left( { - n + 1} \right)^{\,\overline {\,k\,} } \left( { - 1} \right)^{\,k} \left( { - m} \right)^{\,\overline {\,k\,} } } \over {1^{\,\overline {\,k + 1\,} } 1^{\,\overline {\,k\,} } }}4^{\,k} } = \cr & = n\sum\limits_{0\, \le \,k\,\left( { \le \,m,n - 1} \right)} {{{\left( { - n + 1} \right)^{\,\overline {\,k\,} } \left( { - m} \right)^{\,\overline {\,k\,} } } \over {2^{\,\overline {\,k\,} } }}{{4^{\,k} } \over {1^{\,\overline {\,k\,} } }}} = \cr & = n\;{}_2F_{\,1} \left( {\left. {\matrix{ { - n + 1, - m} \cr 2 \cr } \;} \right|\;4} \right) \cr} $$
