# Prove $\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$ for-

Let $n$ be a positve integer. Prove that$$\sum\limits^m_{k=0} \frac{2n-k\choose k}{2n-k\choose n}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}=\frac{n\choose m}{2n-2m\choose n-m}2^{n-2m}$$ for each non-negative integers $m\leq n$.
I know this is to be done by induction. Base case is easy. But I can't simplify expression for $(m+1)$. Please guide.
Edit: $\large P(m+1)=P(m)+\frac{2n-(m+1)\choose m+1}{2n-(m+1)\choose n}\cdot\frac{2n-4(m+1)+1}{2n-2(m+1)+1}\cdot2^{n-2(m+1)}$

$\Large=\frac{n\choose m}{2n-2m \choose n-m}.2^{n-2m}+\frac{2n-m-1\choose m+1}{2n-m-1\choose n}\cdot\frac{2n-4m-3}{2n-2m-1}.2^{n-2m-2}$

It must be equal to $\Large\frac{n\choose m+1}{2n-2m-2\choose n-m-1}.2^{n-2m-2}$

So lets try to simplify it-

$\Large=\frac{n!(n-m)!}{m!(2n-2m)!}.2^{n-2m}+\frac{n!(n-m-1)!}{(m+1)!(2n-2m-2)!}\cdot\frac{2n-4m-3}{2n-2m-1}\cdot2^{n-2m-2}$

$\Large=\frac{2^{n-2m-2}\cdot n!(n-m-1)!}{m!(2n-2m-2)!(2n-2m-1)}[\frac{2}{1}+\frac{1}{(m+1)}\cdot\frac{2n-4m-3}1]$

$\Large=\frac{2^{n-2m-2}\cdot n!(n-m-1)!}{m!(2n-2m-2)!(2n-2m-1)}[\frac{2n-2m-1}{m+1}]$

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

$\Large=\frac{\frac{n!}{(m+1)!(n-m-1)!}}{\frac{(2n-2m-2)!}{(n-m-1)!(n-m-1)!}}\cdot2^{n-2m-2}$

$\Large=\Large\frac{n\choose m+1}{2n-2m-2\choose n-m-1}.2^{n-2m-2}$

I think it is right. But is there any shorter way also?

• Looks good to me (+1). Good job on the strategic manipulations. My only recommendation would be to write your proof more clearly, but even that is not that bad. Nice. – Daniel W. Farlow Aug 13 '15 at 20:11
• Yeah, can you help, I am a newbie at Latex. :( – Aditya Agarwal Aug 14 '15 at 10:12
• Explain the downvote, downvoter – Aditya Agarwal Aug 16 '15 at 3:23

This reduces to a telescoping sum \begin{align} &\sum_{k=0}^m\frac{\binom{2n-k}{k}}{\binom{2n-k}{n}}\frac{2n-4k+1}{2n-2k+1}2^{n-2k}\\ &=\sum_{k=0}^m\frac{(2n-k)!}{k!\,(2n-2k)!}\frac{n!\,(n-k)!}{(2n-k)!}\left(1-\frac{2k}{2n-2k+1}\right)2^{n-2k}\\ &=\sum_{k=0}^m\left[\frac{n!\,(n-k)!}{k!\,(2n-2k)!}2^{n-2k} -\frac{n!\,(n-k)!}{(k-1)!\,(2n-2k+1)!}2^{n-2k+1}\right]\\ &=\sum_{k=0}^m\left[\frac{n!\,(n-k)!}{k!\,(2n-2k)!}2^{n-2k} -\frac{n!\,(n-k+1)!}{(k-1)!\,(2n-2k+2)!}2^{n-2k+2}\right]\\ &=\frac{n!\,(n-m)!}{m!\,(2n-2m)!}2^{n-2m}\\ &=\frac{\binom{n}{m}}{\binom{2n-2m}{n-m}}2^{n-2m} \end{align}