<s>[INST] What is $\binom{n}{2} \binom{n}{1} + \binom{n}{3} \binom{n}{2} + \ldots + \binom{n}{n-1} \binom{n}{n-2} + \binom{n}{n} \binom{n}{n-1}$? 
A bag contains $n$ white and $n$ black balls, all of equal size. Balls are drawn at random. Find the probability that there are both white and black balls in the draw and that the number of white balls is greater than that of black balls by $1$.

The total number of possible draws will be the number of subsets of a set with $2n$ elements (minus the empty set) since we have $2n$ balls, hence $2^{2n} - 1$. The number of draws satisfying the conditions there's both white and black in the draw and also the number of white being greater than that of black by $1$ involves computing the following sum:$$\binom{n}{2} \binom{n}{1} + \binom{n}{3} \binom{n}{2} + \ldots + \binom{n}{n-1} \binom{n}{n-2} + \binom{n}{n} \binom{n}{n-1},$$which I don't know how to do. Could anybody help? Thanks. I've tried playing around with paths on an $n \times n$ grid, also an $2n \times n$ grid to come up with a combinatorial proof, not to any success.
 [/INST] A combinatoric proof : Let :
$$A = \{1, 2, \ldots, 2 k\}, B = \{1, \ldots, k\} \text{ and } C = \{k + 1, \ldots, 2 k\}$$
We need to choose $k - 1$ elements from $A$. There are two ways :

*

* First way : Choose $k - 1$ element directly for $A$ : In this case, we have then :
$$\binom{2 k}{k - 1}$$
ways.

* Second way : We can choose $r$ elements from $B$ and $k - 1 - r$ from $C$ for $r \in \{0, \ldots, k -1 \}$ : In this case we have :
$$\sum_{r = 0}^{k-1} \binom{k}{r} \binom{k}{k - 1 - r}$$
ways.

We deduce that : 
$$\binom{2 k}{k - 1} = \sum_{r = 0}^{k-1} \binom{k}{r} \binom{k}{k - 1 - r} = \sum_{r = 0}^{k-1} \binom{k}{r} \binom{k}{r + 1}$$
</s>