Expected value of pairs remaining after draw Problem: Someone removed $m$ shoes from a pile with $n$ distinct pairs of shoes ($2n$ shoes total). Assuming that every shoe has an equal chance of $1/(2n)$ to be removed, what is the mean number of complete pairs of shoes to remain in the pile.
Solutions:
Defining $K$, a random variable denoting the number of shoes left in the pile, I argued that the probability of $k_i$ pairs of shoes remaining in the pile would be given by: 
\begin{align}
p_{k_i} & = \cfrac{{2n - 2k_i \choose m}}{2n \choose m} & \text{therefore,} \\
E(K) & = \sum\limits_{k=0}^n k\cfrac{{2n - 2k \choose m}}{2n \choose m}
\end{align}
However, I was given another solution, that defined the random variable $X$, such that, $x_i = 1$, when the $i$th pair remains in the pile. Then,
\begin{align}
p_{x_i = 1} & = \cfrac{{2n - 2 \choose m}}{2n \choose m} & \text{and,} \\
E(X) & = \sum\limits_{i=1}^n x_i\cfrac{{2n - 2 \choose m}}{2n \choose m} \\
& = n\cfrac{{2n - 2 \choose m}}{2n \choose m}
\end{align}
Are either solution correct? And most importantly, why?
Edit With some real numbers, it appears the second answer is correct, but I still do not understand the reasoning (or the error in reasoning for the first proposed answer).
ans1 <- function(n, m) {
  sum(sapply(1:n, function(k) k*choose(2*n - 2*k, m)/choose(2*n, m)))
}
ans2 <- function(n, m) {
  n*choose(2*n - 2, m)/choose(2*n, m)
}
list('ans1' = ans1(10, 4), 'ans2' = ans2(10, 4))
# $ans1
# [1] 2.73808
# 
# $ans2
# [1] 6.315789

Clearly, if we remove 4 shoes, the maximum number of pairs destroyed is 4, so an expected value less than 6 is impossible. 
 A: The second formula is correct, easier to see via Linearity of Expectation.
Let $X_i$ be the indicator variable for the $i^{th}$ pair.  Thus, $X_i=1$ if the pair remains in the pile, and it $=0$ otherwise.
We remark that $$E_m[X_i]=\frac {2n-m}{2n}\times \frac {2n-m-1}{2n-1}$$  By Linearity we have your answer as $$E_m=nE_m[X_i]=\frac {(2n-m)(2n-m-1)}{2(2n-1)}$$
Note that this is equivalent to the second formula you provide.
As a crude Sanity Check we note that $$E_0=n \quad \&\quad  E_1=n-1$$
as expected.
A: The latter solution appears largely correct. To be clear, if $X_{i}=1$ if the $i$th pair of shoes remains after the selection, and is 0 otherwise, then $X_{i}\sim$Bernoulli($p$), where $p=\binom{2n-2}{m}/\binom{2n}{m}$. Then $X=\sum_{i=1}^{n}X_{i},$ so $E(X)=\sum_{i=1}^{n}E(X_{i})=np.$ Note that despite the similarity in computation, $X$ is not Binomial, however, since the $X_{i}$ are not independent.
One problem with the first solution is that you're saying that the probability of $k_{i}$ pairs of shoes remaining is $\binom{2n-2k_{i}}{m}/\binom{2n}{m},$ so the numerator is essentially counting the number of ways to select $m$ shoes from the $2n-2k_{i}$ shoes left over, given that $k_{i}$ pairs are left intact. But this does not account for the fact that there are multiple ways to select the $k_{i}$ pairs from the $n$ possible. To see an example, suppose we have shoes labeled $1,2,3,4,$ with $1,2$ being a pair, and $3,4$ being a pair. Then if $k_{i}=1,$ $m=1$, then $\binom{4-2}{1}=2$, as you have counted. But we may remove any of the four shoes, and exactly one pair will remain, so the correct number should be $4=\binom{2}{1}\binom{4-2}{1}$.
