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}$

Question

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}$.

Answer 1

The identity is equivalent to $$\sum\limits_{i=0}^{k-1}\binom{n-1}{i}\,\binom{n-1-i}{2k-2-2i}\,4^{2k-2-i}=4^{k-1}\binom{2n-2}{2k-2}$$ where $i=j-1$. By considering the Cauchy product, the LHS is $$4^{2k-2}[z^{2k-2}](1+z)^{n-1}\left(1+\frac{z^2}{4(1+z)}\right)^{n-1}$$ which can be written as $$4^{2k-2}[z^{2k-2}]\left(1+\frac{z}{2}\right)^{2n-2}$$ that is the RHS.

Answer 2

Let's take the RHS term, multiply it by $x^{2k}$, and sum over $k$ $$ \eqalign{ & F_R (x^{\,2} ,n) = \sum\limits_{0\, \le \,k} {n\left( \matrix{ 2n - 2 \cr 2k - 2 \cr} \right)x^{\;2k} } = \cr & = n\,x^{\,2} \,\sum\limits_{0\, \le \,\left( {1\, \le } \right)\,k} {\left( \matrix{ 2\left( {n - 1} \right) \cr 2\left( {k - 1} \right) \cr} \right) \left( {x^{\,2} } \right)^{\;k - 1} } = \cr & = n\,x^{\,2} \,\sum\limits_{0\, \le \,\left( {1\, \le } \right)\,k} {\left( \matrix{ 2\left( {n - 1} \right) \cr 2k \cr} \right)\left( {x^{\,2} } \right)^{\;k} } = \cr & = {{n\,x^{\,2} } \over 2}\left( {\left( {1 + x} \right)^{2n - 2} + \left( {1 - x} \right)^{2n - 2} } \right) \cr} $$

Then we do the same on the LHS $$ \eqalign{ & F_L (x^{\,2} ,n) = \sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,j} {j\left( \matrix{ n \cr j \cr} \right) \left( \matrix{ n - j \cr 2k - 2j \cr} \right)2^{\,2k - 2j} x^{\;2k} } } = \cr & = n\sum\limits_{0\, \le \,k} {\sum\limits_{0\, \le \,j} {\left( \matrix{ n - 1 \cr j - 1 \cr} \right)\left( \matrix{ n - j \cr 2\left( {k - j} \right) \cr} \right) \left( {2^{\,2} x^{\,2} } \right)^{\,\left( {k - j} \right)} x^{\;2j} } } = \cr & = n\sum\limits_{0\, \le \,j} {\left( \matrix{ n - 1 \cr j - 1 \cr} \right)x^{\;2j} \sum\limits_{0\, \le \,\left( {k - j} \right)} {\left( \matrix{ n - j \cr 2\left( {k - j} \right) \cr} \right) \left( {2^{\,2} x^{\,2} } \right)^{\,\left( {k - j} \right)} } } = \cr & = {n \over 2}\sum\limits_{0\, \le \,j} {\left( \matrix{ n - 1 \cr j - 1 \cr} \right)x^{\;2j} \left( {\left( {1 + 2x} \right)^{n - j} + \left( {1 - 2x} \right)^{n - j} } \right)} = \cr & = {{nx^{\;2n} } \over 2}\sum\limits_{0\, \le \,j} {\left( \matrix{ n - 1 \cr n - j \cr} \right)x^{\;2j - 2n} \left( {\left( {1 + 2x} \right)^{n - j} + \left( {1 - 2x} \right)^{n - j} } \right)} = \cr & = {{nx^{\;2n} } \over 2}\sum\limits_{0\, \le \,n - j} {\left( \matrix{ n - 1 \cr n - j \cr} \right) \left( {\left( {{{1 + 2x} \over {x^{\;2} }}} \right)^{n - j} + \left( {{{1 - 2x} \over {x^{\;2} }}} \right)^{n - j} } \right)} = \cr & = {{nx^{\;2n} } \over 2}\left( {\left( {1 + {{1 + 2x} \over {x^{\;2} }}} \right)^{n - 1} + \left( {1 + {{1 - 2x} \over {x^{\;2} }}} \right)^{n - 1} } \right) = \cr & = {{nx^{\;2} } \over 2}\left( {\left( {1 + x} \right)^{\,2\left( {n - 1} \right)} + \left( {1 - x} \right)^{\,2\left( {n - 1} \right)} } \right) \cr} $$

The two polynomials are equal, so must be their coefficients.

Answer 3

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.