Show $\sum_{k=1}^n {k+1\choose 2}{2n+1\choose n+k+1}={n\choose 1}4^{n-1}$

Question

I've been attempting to show that: $$\sum_{k=1}^n {k+1\choose 2}{2n+1\choose n+k+1}={n\choose 1}4^{n-1}\\ \sum_{k=2}^n {k+2\choose 4}{2n+1\choose n+k+1}={n\choose 2}4^{n-2}$$

Can anyone give some direction?

Answer 1

Generalizing we seek to verify that

$$S_{n,m} = \sum_{k=m}^n {k+m\choose 2m} {2n+1\choose n+k+1} = {n\choose m} 4^{n-m}.$$

The LHS is

$$\sum_{k=0}^{n-m} {k+2m\choose 2m} {2n+1\choose n+m+k+1} \\ = \sum_{k=0}^{n-m} {k+2m\choose 2m} [z^{n-m-k}] \frac{1}{(1-z)^{n+m+k+2}} \\ = [z^{n-m}] \frac{1}{(1-z)^{n+m+2}} \sum_{k=0}^{n-m} {k+2m\choose 2m} \frac{z^k}{(1-z)^k}.$$

Now when $k\gt n-m$ there is no contribution to the coefficient extractor and we may continue with

$$[z^{n-m}] \frac{1}{(1-z)^{n+m+2}} \sum_{k\ge 0} {k+2m\choose 2m} \frac{z^k}{(1-z)^k} \\ = [z^{n-m}] \frac{1}{(1-z)^{n+m+2}} \frac{1}{(1-z/(1-z))^{2m+1}} \\ = [z^{n-m}] \frac{1}{(1-z)^{n-m+1}} \frac{1}{(1-2z)^{2m+1}}.$$

This yields

$$S_{n,m} = \mathrm{Res}_{z=0} \frac{1}{z^{n-m+1}} \frac{1}{(1-z)^{n-m+1}} \frac{1}{(1-2z)^{2m+1}}.$$

Residues sum to zero and the residue at infinity is zero by inspection. We get for the residue at $z=1$

$$\mathrm{Res}_{z=1} \frac{1}{z^{n-m+1}} \frac{1}{(1-z)^{n-m+1}} \frac{1}{(1-2z)^{2m+1}}.$$

Setting $z= 1-u$ we get

$$- \mathrm{Res}_{u=0} \frac{1}{(1-u)^{n-m+1}} \frac{1}{u^{n-m+1}} \frac{1}{(1-2(1-u))^{2m+1}} \\ = - \mathrm{Res}_{u=0} \frac{1}{(1-u)^{n-m+1}} \frac{1}{u^{n-m+1}} \frac{1}{(2u-1)^{2m+1}} \\ = \mathrm{Res}_{u=0} \frac{1}{(1-u)^{n-m+1}} \frac{1}{u^{n-m+1}} \frac{1}{(1-2u)^{2m+1}} = S_{n,m}.$$

Continuing with the residue at $z=1/2$ we find

$$-\frac{1}{2^{2m+1}} \mathrm{Res}_{z=1/2} \frac{1}{z^{n-m+1}} \frac{1}{(1-z)^{n-m+1}} \frac{1}{(z-1/2)^{2m+1}} \\ = -\frac{1}{2^{2m+1}} \mathrm{Res}_{z=1/2} \frac{1}{(1/2+(z-1/2))^{n-m+1}} \frac{1}{(1/2-(z-1/2))^{n-m+1}} \\ \times \frac{1}{(z-1/2)^{2m+1}} \\ = -\frac{1}{2^{2m+1}} \mathrm{Res}_{z=1/2} \frac{1}{(1/4-(z-1/2)^2)^{n-m+1}} \frac{1}{(z-1/2)^{2m+1}} \\ = -\frac{1}{2^{2m+1}} \mathrm{Res}_{z=1/2} \frac{4^{n-m+1}}{(1-4(z-1/2)^2)^{n-m+1}} \frac{1}{(z-1/2)^{2m+1}} \\ = -\frac{2^{2n-2m+2}}{2^{2m+1}} [(z-1/2)^{2m}] \frac{1}{(1-4(z-1/2)^2)^{n-m+1}} \\ = -\frac{2^{2n-2m+2}}{2^{2m+1}} [(z-1/2)^{m}] \frac{1}{(1-4(z-1/2))^{n-m+1}} \\ = -\frac{2^{2n-2m+2}}{2^{2m+1}} {m+n-m\choose n-m} 2^{2m}.$$

We have shown that

$$S_{n,m} + S_{n,m} - 2^{2n-2m+1} {n\choose m} = 0$$

which is at last

$$\bbox[5px,border:2px solid #00A000]{ S_{n,m} = {n\choose m} 4^{n-m}.}$$

Answer 2

Let's rearrange the sum as
$$ \eqalign{ & s(n) = \sum\limits_{k = 1}^n {\left( \matrix{ k + 1 \cr 2 \cr} \right)\left( \matrix{ 2n + 1 \cr n + k + 1 \cr} \right)} = \cr & = \sum\limits_{k = \,0}^{n - 1} {\left( \matrix{ k + 2 \cr 2 \cr} \right)\left( \matrix{ 2n + 1 \cr n + k + 2 \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\,} {\left( \matrix{ k + 2 \cr 2 \cr} \right)\left( \matrix{ 2n + 1 \cr n + k + 2 \cr} \right)} \cr} $$

The summand is equal to $$ \eqalign{ & t_{\,k} = \left( \matrix{ k + 2 \cr 2 \cr} \right) \left( \matrix{ 2n + 1 \cr n + k + 2 \cr} \right) = \cr & = {{\Gamma \left( {k + 3} \right)} \over {\Gamma \left( {k + 1} \right)\Gamma \left( {n + k + 3} \right)\Gamma \left( {n - k} \right)}} {{\Gamma \left( {2n + 2} \right)} \over {\Gamma \left( 3 \right)}} \cr} $$
so that $$ t_{\,0} = \left( \matrix{ 2n + 1 \cr n + 2 \cr} \right) = {{\Gamma \left( {2n + 2} \right)} \over {\Gamma \left( {n + 3} \right)\Gamma \left( n \right)}} $$
and the ratio is
$$ \eqalign{ & {{t_{\,k + 1} } \over {t_{\,k} }} = \cr & = {{\Gamma \left( {k + 4} \right)} \over {\Gamma \left( {k + 2} \right)\Gamma \left( {n + k + 4} \right)\Gamma \left( {n - 1 - k} \right)}} {{\Gamma \left( {k + 1} \right)\Gamma \left( {n + k + 3} \right)\Gamma \left( {n - k} \right)} \over {\Gamma \left( {k + 3} \right)}} = \cr & = {{\Gamma \left( {k + 4} \right)\Gamma \left( {k + 1} \right)\Gamma \left( {n + k + 3} \right)\Gamma \left( {n - k} \right)} \over {\Gamma \left( {k + 3} \right)\Gamma \left( {k + 2} \right)\Gamma \left( {n + k + 4} \right)\Gamma \left( {n - 1 - k} \right)}} = \cr & = {{\left( {k + 3} \right)\left( {n - 1 - k} \right)} \over {\left( {k + 1} \right)\left( {n + k + 3} \right)}} = - {{\left( {k + 3} \right)\left( {k - \left( {n - 1} \right)} \right)} \over {\left( {k + 1} \right)\left( {k + n + 3} \right)}} \cr} $$

That means that we can write $s(n))$ in terms of a Hypergeometric function
$$ s(n) = {{\Gamma \left( {2n + 2} \right)} \over {\Gamma \left( {n + 3} \right)\Gamma \left( n \right)}} {}_2F_{\,1} \left( {\left. {\matrix{ {\;3,\; - \left( {n - 1} \right)} \cr {n + 3} \cr } \;} \right|\; - 1} \right) $$

Since
$$ 1 + a - b = 1 + 3 + n - 1 = n + 3 = c $$
we can apply [Kummer's theorem](https://en.wikipedia.org/wiki/Hypergeometric_function#Kummer's_theorem_(z_=_%E2%88%921) and get $$ \eqalign{ & s(n) = {{\Gamma \left( {2n + 2} \right)} \over {\Gamma \left( {n + 3} \right)\Gamma \left( n \right)}}{}_2F_{\,1} \left( {\left. {\matrix{ {\;3,\; - \left( {n - 1} \right)} \cr {n + 3} \cr } \;} \right|\; - 1} \right) = \cr & = {{\Gamma \left( {2n + 2} \right)} \over {\Gamma \left( {n + 3} \right)\Gamma \left( n \right)}}{{\Gamma \left( {n + 3} \right)\Gamma \left( {5/2} \right)} \over {\Gamma \left( 4 \right)\Gamma \left( {3/2 + n} \right)}} = \cr & = {{\Gamma \left( {5/2} \right)} \over {\Gamma \left( 4 \right)}}{{\Gamma \left( {2n + 2} \right)} \over {\Gamma \left( n \right)\Gamma \left( {3/2 + n} \right)}} \cr} $$

Then by the duplication formula $$ \Gamma \left( {2\,n + 2} \right) = 2^{\,2\,n + 1} {{\Gamma \left( {n + 1} \right)\Gamma \left( {n + 3/2} \right)} \over {\Gamma \left( {1/2} \right)}} $$
we finally reach to $$ \eqalign{ & s(n) = {{\Gamma \left( {5/2} \right)} \over {\Gamma \left( 4 \right)\Gamma \left( {1/2} \right)}}{{\Gamma \left( {n + 1} \right)\Gamma \left( {n + 3/2} \right)} \over {\Gamma \left( n \right)\Gamma \left( {3/2 + n} \right)}}2^{\,2\,n + 1} = \cr & = {{\Gamma \left( {5/2} \right)} \over {\Gamma \left( 4 \right)\Gamma \left( {1/2} \right)}}n\,2^{\,2\,n + 1} = {1 \over 8}n\,2^{\,2\,n + 1} = n\,2^{\,2\,n - 2} \cr} $$