<s>[INST] 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}$ 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}$.
 [/INST] 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.
</s>