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{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=\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?

  • $\begingroup$ 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. $\endgroup$ – Daniel W. Farlow Aug 13 '15 at 20:11
  • $\begingroup$ Yeah, can you help, I am a newbie at Latex. :( $\endgroup$ – Aditya Agarwal Aug 14 '15 at 10:12
  • $\begingroup$ Explain the downvote, downvoter $\endgroup$ – 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} $$

  • $\begingroup$ Nice manipulation. However, OP wrote "I know this is to be done by induction.", so I will deduct .01 point. $\endgroup$ – marty cohen Aug 14 '15 at 20:58
  • 4
    $\begingroup$ To me, that doesn't mean that induction is required; it sounds as if the OP is assuming it is to be done by induction. $\endgroup$ – robjohn Aug 14 '15 at 21:43
  • $\begingroup$ It's always nice when there are multiple different proofs of a result. $\endgroup$ – marty cohen Aug 15 '15 at 0:16
  • $\begingroup$ Yes, sorry for the confusion, its good. (y) @robjohn $\endgroup$ – Aditya Agarwal Aug 15 '15 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.