While working on a problem I came across the following similar combinatorial identities valid by numerical evidence $(n\ge m)$:
$$\begin{align}
A(n,m)&\equiv\sum_{k\ge1}\binom km\binom{n-1}{k-1}=2^{n-m-1}\binom nm\frac{n+m}{n},\\
B(n,m)&\equiv\sum_{k\ge1}\left[\binom{\left\lfloor\frac k2\right\rfloor}m
+\binom{\left\lceil\frac k2\right\rceil}m\right]\binom{n-1}{k-1}=2^{n-2m}\binom {n-m}{m-1}\frac{n+1}{m}.
\end{align}$$
I am looking for an algebraic proof of these identities.
Is there a smart way to prove:
$$
B(n,m)=A(n-m+1,m)
$$
without explicit evaluation of the sums?
Best Answer
Using a coefficient extractor Eg \begin{eqnarray*} \binom{k}{m} = [x^m]:(1+x)^k. \end{eqnarray*} We have \begin{eqnarray*} \sum_{k\ge1}\binom km\binom{n-1}{k-1} &=& [x^m]: \sum_{k=1}^{n} \binom{n-1}{k-1} (1+x)^k \\ &=& [x^m]: (1+x) (2+x)^{n-1} \\ &=& 2^{n-1-m} \binom{n-1}{m} +2^{n-m} \binom{n-1}{m-1} \\ &=& 2^{n-1-m}\left( \binom{n-1}{m} +2 \binom{n-1}{m-1} \right)\\ &=& 2^{n-1-m} \frac{(n-1)!}{m!(n-m)!} \left( n-m+2m \right)\\ &=& 2^{n-1-m} \frac{(n-1)!}{m!(n-m)!} (n+m).\\ \end{eqnarray*} Which is the first identity (upto a factor of $n$).