Prove that $\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}={2n+2m+1\choose 4m+1}2^{4m-1}$

Question

Let $n,m$ are positive integers satisfy the condition $n\ge m>0$

Prove that

$\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}={2n+2m+1\choose 4m+1}2^{4m-1}$

Answer 1

My solution

We have

$\displaystyle S(n,m)=\sum_{k=0}^m {2n\choose 2k}{n-k\choose m-k}=\sum_{k=0}^m\dfrac{(2n)!}{(2k)!(2n-2k)!}\cdot \dfrac{(n-k)!}{(m-k)!(n-m)!}$

$\displaystyle\qquad\quad =\sum_{k=0}^m\dfrac{2^nn!(2n-1)!!}{2^kk!(2k-1)!!2^{n-k}(n-k)!(2n-2k-1)!!}\cdot \dfrac{(n-k)!}{(m-k)!(n-m)!}$

$\displaystyle\qquad\quad=\dfrac{n!(2n-1)!!}{m!(n-m)!}\sum_{k=0}^m\dfrac{{m\choose k}}{(2k-1)!!(2n-2k-1)!!}$

$\displaystyle \Rightarrow S(n,m)=\dfrac{n!(2n-1)!!}{m!(n-m)!}\cdot R(m,0)\tag 1$ Here $\displaystyle R(m,p)=\sum_{k=0}^m\dfrac{{m\choose k}}{(2k+2p-1)!!(2n-2k-1)!!}$

Now, we get differences

$\Delta\left[(-1)^{k-1}{m-1\choose k-1}\right]=(-1)^k{m-1\choose k}-(-1)^{k-1}{m-1\choose k-1}=(-1)^k{m\choose k}$

and

$\Delta\left[\dfrac{(-1)^k}{(2k+2p-1)!!(2n-2k-1)!!}\right]=$

$\qquad\qquad\qquad\qquad=\dfrac{(-1)^{k+1}}{(2k+2p+1)!!(2n-2k-3)!!}-\dfrac{(-1)^k}{(2k+2p-1)!!(2n-2k-1)!!}$

$\qquad\qquad\qquad\qquad=2(n+p)\cdot\dfrac{(-1)^{k+1}}{(2k+2p+1)!!(2n-2k-1)!!}$

By the Summation by parts, we have

$\displaystyle R(m,p)=\sum_{k=0}^m \dfrac{{m\choose k}}{(2k+2p-1)!!(2n-2k-1)!!}$

$\displaystyle\qquad =\sum_{k=0}^m\dfrac{(-1)^k}{(2k+2p-1)!!(2n-2k-1)!!} \Delta\left[(-1)^{k-1}{m-1\choose k-1}\right]$

$\displaystyle\qquad =\left.\dfrac{(-1)^k}{(2k+2p-1)!!(2n-2k-1)!!}\cdot(-1)^{k-1}{m-1\choose k-1}\right|_{k=0}^{m+1}$

$\displaystyle\qquad\quad -\sum_{k=0}^m\dfrac{(-1)^k{m-1\choose k}2(n+p)(-1)^{k+1}}{(2k+2p+1)!!(2n-2k-1)!!}$

$\displaystyle\qquad =2(n+p)\sum_{k=0}^{m-1}\dfrac{{m-1\choose k}}{(2k+2p+1)!!(2n-2k-1)!!}$

$\displaystyle\qquad =2(n+p)\cdot R(m-1,p+1)$

$\Rightarrow R(m,p)=2(n+p)\cdot R(m-1,p+1)=2^2(n+p)(n+p+1)\cdot R(m-2,p+2)=...$

$\quad...=2^m(n+p)...(n+p+m-1)\cdot R(0,p+m) $

$\qquad =2^m(n+p)...(n+p+m-1)\cdot \dfrac{{0\choose 0}}{(2.0+2p+2m-1)!!(2n-2.0-1)!!}$

$\qquad =\dfrac{2^m(n+p+m-1)!}{(n+p-1)!(2p+2m-1)!!(2n-1)!!}$

Since (1), we have

$\displaystyle S(n,m)=\sum_{k=0}^m {2n\choose 2k}{n-k\choose m-k}=\dfrac{n!(2n-1)!!}{m!(n-m)!}\cdot R(m,0)$

$=\dfrac{n!(2n-1)!!}{m!(n-m)!}\cdot \dfrac{2^m(n+m-1)!}{(n-1)!(2m-1)!!(2n-1)!!}$

$=\dfrac{2^{2m}n(n+m-1)!}{(n-m)!(2m)!}$

$=\displaystyle 2^{2m-1}\left[{n+m+1\choose 2m+1}-{n+m-1\choose 2m+1}\right]$

Therefor

$\displaystyle\sum_{j=m}^n\sum_{k=0}^{2m}{4j\choose 2k}{2j-k\choose 2m-k}=\sum_{j=m}^n S(2j,2m)=\sum_{j=m}^n 2^{4m-1}\left[{2j+1+2m\choose 4m+1}-{2j-1+2m\choose 4m+1}\right] $

$\displaystyle =2^{4m-1}{2n+2m+1\choose 4m+1}$

DONE!