Help in proving relations involving finite sums containing factorials, coming from an odd card problem Let's say I have a deck of $2P$ cards, with $P$ of them red and $P$ black ($P$ is a "large" integer, such as 26). I then randomly form $P$  pairs of cards. I was able to show that the probability of having exactly $c$ red-red ($RR$) pairs, which is equal to the number of $BB$ pairs, is given by
$$
    \text{Pr}(P,\,c) = \frac{P!\,P!}{(2P)!} \times
    \frac{P!}{c!\,c!\,(P-2c)!} \times 2^{P-2c} \qquad (0 \le c \le P/2)
$$
But I'm having trouble trying to prove that these probabilities are normalized, that is
$$
\sum_{c=0}^{P/2} \text{Pr}(P,\,c) = 1 \,,
$$
and also that the expected $c$ value is
$$
\langle c \rangle = \sum_{c=0}^{P/2} c \, \text{Pr}(P,\,c) =  \frac{P(P-1)}{2 (2P-1)} \,.
$$
By the way, I checked the normalization and calculated the last expression using  Mathematica. But I have no idea how the software arrived at the results...
My question is: How to prove the last two relations? I don't mean a proof by induction. I mean a strategy to arrive at the expressions.
Thanks for the feedback, all help will be greatly appreciated!
 A: For starters, I would say that your argument constitutes a full proof that that complicated summation is equal to $1$. You have started with a partition of the set of possible pairings into several classes, and proven an enumeration for each class. It follows the sum of the sizes is equal to the total number of pairings. However, we can provide a proof by induction as well.
Mathematica likely simplifies these summations using Zeilberger's algorithm. Using the same algorithm, we can generate a human readable proof. Let $$F(n,k)=\frac{n!^3}{(2n)!k!^2(n-2k)!}2^{n-2k},\qquad S_n=\sum_{k=0}^{\lfloor n/2\rfloor} F(n,k)$$
so you want to prove $S_n=1$ for all $n\ge 1$. I will adopt the convention $F(n,k)=0$ when $2k>n$, so $S_n=\sum_{k=0}^\infty F(n,k)$ as well.
Now, let $$
G(n,k)=F(n,k)\cdot\color{blue}{\frac{4k^2}{(n-2k+1)(2n+1)}}=\frac{n!^3k^2}{(2n+1)!k!^2(n-2k+1)!}2^{n-2k+2}
$$
with the convention that $G(n,k)=0$ when $2k>n+1$. You can then show that
$$
F(n,k)-F(n+1,k)=G(n,k+1)-G(n,k)\tag1
$$
Proving this just takes a lot of tedious algebraic manipulation, no creativity at all. Start by canceling common factorials until all that remains is ratio of polynomials in $k$ and $n$ on both sides, get a common denominator, and then simplify.
Now, sum both sides of $(1)$ from $k=0$ to $\infty$. We get
$$
\sum_{k=0}^\infty F(n,k)-\sum_{k=0}^\infty F(n+1,k)=\sum_{k=0}^\infty (G(n,k+1)-G(n,k)
$$
The summations on the left are $S_n$ and $S_{n+1}$, while the right hand side is a telescoping series. We therefore get
$$
S_n-S_{n+1}=-G(n,0)=0,
$$
(to see why $G(n,0)=0$, note the $k^2$ in the numerator of $G(n,k)$), so that $S_{n+1}=S_n$ for all $n$. Therefore, to verify $S_n=1$, you need only check that $S_1=1$.

A similar method can be used to prove $\sum c\text{Pr}(P,c)=P(P-1)/2(2P-1)$, but the linearity of expectation argument in the comments is the nicer way. (In case it gets deleted: for each card, the probability it is paired with a same-colored card is $\frac{P-1}{2P-1}$. Summing over call cards, you get $2P\cdot \frac{P-1}{2P-1}$, and this will count each pair of cards twice, so divide by $2$.)
