I encountered this in my homework. I derived two ways to solve the problem and the answer which I have tested using programming, seem to be the same, but I am not sure how to prove this equation.
Let $n$ and $k$ be nonnegative integers with $k\leq n$. Prove that $$\sum\limits_{j=0}^k\,j\,\binom{n}{j}\,\binom{n-j}{2k-2j}\,2^{2k-2j}=n\binom{2n-2}{2k-2}\,.$$
The original problem is the following:
A shoe rack has n pairs of shoes. Of those, 2k individual shoes are chosen at random, k ≤ n. Calculate the expected number of matching shoes among 2k chosen shoes.
The left hand side is from directly calculating expectation, while the right hand side is using sum of indicator variables of each pair being chosen. The expectation is just the equation divided by $\binom{2n}{2k}$.
Best Answer
Using coefficient extractors we present a minor variation and seek to prove
$$\sum_{j=1}^k {n-1\choose j-1} {n-j\choose 2k-2j} 2^{2k-2j} = {2n-2\choose 2k-2}$$
or alternatively
$$\sum_{j=0}^{k-1} {n-1\choose j} {n-j-1\choose 2k-2j-2} 2^{2k-2j-2} = {2n-2\choose 2k-2}.$$
The LHS is
$$\sum_{j=0}^{k-1} {n-1\choose j} 2^{2k-2j-2} [z^{2k-2j-2}] (1+z)^{n-j-1} \\ = 2^{2k-2} [z^{2k-2}] (1+z)^{n-1} \sum_{j=0}^{k-1} {n-1\choose j} (1+z)^{-j} z^{2j} 2^{-2j}.$$
The coefficient extractor enforces the upper limit of the sum:
$$ 2^{2k-2} [z^{2k-2}] (1+z)^{n-1} \sum_{j\ge 0} {n-1\choose j} (1+z)^{-j} z^{2j} 2^{-2j} \\ = 2^{2k-2} [z^{2k-2}] (1+z)^{n-1} \left(1+\frac{z^2}{4(1+z)}\right)^{n-1} \\ = 2^{2k-2} [z^{2k-2}] \left(1+z+\frac{z^2}{4}\right)^{n-1} = [z^{2k-2}] \left(1+2z+z^2\right)^{n-1} \\ = [z^{2k-2}] (1+z)^{2n-2} = {2n-2\choose 2k-2}.$$
This is the claim.