how to solve $\sum _{m=0}^{k-1}mC_{k-1}^{m}C_{N-k}^{m}$?

Question

solving

$$\sum _{m=0}^{k-1} mC_{k-1}^m C_{N-k}^m$$

the solution seems to be

$$\frac {\left( N-2\right) !} {\left( k-2\right) !\left( N-k-1\right) !}$$

according to some clue from the other problem.

struggle with this the whole afternoon, please help.

i tried to extend it, but it's too complicated. i think there should be some smart trick to apply on it to make it easier.

i remember i saw this problem long time ago, but i forgot the solution.

UPDATE: the original suspected solution is wrong. now it's corrected.

Answer 1

Suppose we seek to evaluate $$\sum_{m=0}^{k-1} m {k-1\choose m} {N-k\choose m}.$$

Start from $${N-k\choose m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{N-k} \; dz.$$

This gives the following integral for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{m=0}^{k-1} m {k-1\choose m} \frac{1}{z^{m+1}} (1+z)^{N-k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{N-k}}{z} \sum_{m=0}^{k-1} m {k-1\choose m} \frac{1}{z^m} \; dz.$$

Now recall that $$x ((1+x)^n)' = \sum_{q=0}^n q {n\choose q} x^q$$ and $$x ((1+x)^n)' = n x (1+x)^{n-1}$$ so that the sum in the integral simplifies to $$\frac{k-1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{N-k}}{z} \frac{1}{z}\left(1 + \frac{1}{z}\right)^{k-2} \; dz. \\ = \frac{k-1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{N-k}}{z} \frac{1}{z}\frac{(1+z)^{k-2}}{z^{k-2}} \; dz \\ = \frac{k-1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{N-2}}{z^k} \; dz.$$

The last integral may be evaluated by inspection and gives $$(k-1) {N-2\choose k-1} = \frac{(N-2)!}{(k-2)!(N-k-1)!}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.

Answer 2

Related techniques: (I). We have

$$ \sum _{m=0}^{k-1} m\,C_{k-1}^m C_{N-k}^m = \frac{1}{(N-k)!}\sum _{m=0}^{k-1} m\,C_{k-1}^m\frac{m!}{(m-(N-k))!}. $$

Let's start with the identity

$$S= \sum_{m=0}^{k-1} C_m^{k-1}x^m = (1+x)^{k-1}\implies \sum_{m=0}^{k-1} m\,C_m^{k-1}x^{m-1} = (k-1)(1+x)^{k-2} $$

Multiplying both sides of the last equation by $x$, differentiating $N-k$ times and dividing by $(N-k)!$ gives

$$ \frac{1}{(N-k)!}\sum_{m=0}^{k-1} mC_m^{k-1}\frac{m!}{(m-(N-k))!}x^{m-(N-k)} = \frac{(k-1)}{(N-k)!}\sum_{i=0}^{N-k} C_{i}^{N-k} x^{(i)}((1+x)^{k-2})^{(N-k-i)}. $$

You can see that on the right hand side of the last equation that all the terms are $0$ except $i=0,1$. So there is nothing left in the problem except to simplify the above and then substitute $x=1$.

Notes: You need the following facts

1) The $r$th differentiation formula for $x^s$

$$ D^{r}x^{s} = \frac{s!}{(r-s)!} x^{s-r}. $$

2) The product formula for differentiation

$$ (fg)^{(r)} \sum_{i=0}^{n}{r \choose i } f^{(i)}g^{(r-i)} $$

Answer 3

after a few days research, i have come up with a easy arithmetic solution without calculus.

$$\sum _{m=0}^{k-1} mC_{k-1}^m C_{N-k}^m$$ $$=\sum _{m=0}^{k-1} (k-1)C_{k-2}^{m-1} C_{N-k}^m$$ this will be proved by simply extending it. $$=\sum _{m=0}^{k-1} (k-1)C_{k-2}^{k-m-1} C_{N-k}^m$$ $$=(k-1)C_{N-2}^{k-1}\ ............\ lemma\ 1$$ this will be proved later $$=\frac{(k-1)(N-2)!}{(k-1)!(N-k-1)!}$$ $$=\frac{(N-2)!}{(k-2)!(N-k-1)!}$$

now i will prove lemma 1. observe $(1+x)^{a+b}$, and its extension. notice that the factor of term $x^d$ is $C_{a+b}^d$.

then for $(1+x)^{a}$, the factor of term $x^e$ is $C_{a}^e$. then for $(1+x)^{b}$, the factor of term $x^f$ is $C_{b}^f$.

let $e+f=d$, list the summation: $$\sum_{e:\ as\ much\ as\ meaningful}C_{a}^eC_{b}^{d-e}=C_{a+b}^d$$ proved

Answer 4

$$Vandermonde's Identity: \sum_{i=0}^{j} \binom{y}{j-i}\binom{x}{i}=\binom{x+y}{j}$$

$$\sum_{m=0}^{k-1} m\binom{k-1}{m}\binom{N-k}{m}=\sum_{m-1=0}^{k-2} m\binom{k-1}{k-1-m}\frac{N-k}{m}\binom{N-k-1}{m-1}$$ $$\quad\quad\quad\quad=(N-k)\sum_{m-1=0}^{k-2} \binom{k-1}{k-2-(m-1)}\binom{N-k-1}{m-1}$$ $$\quad=(N-k)\binom{N-2}{k-2} (By\;Vandermonde's\; Identity)$$ $$\quad=(N-k)\frac{(N-2)!}{(k-2)!(N-k)!}$$ $$\quad=\frac{(N-2)!}{(k-2)!(N-k-1)!}$$