For any two integers $2 \le k \le n-2$, there is the identity
$$\dbinom{n}{2} = \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2}.$$
a) Give an algebraic proof of this identity, writing the binomial coefficients in terms of factorials and simplifying.
b) Give a combinatorial proof (and interpretation) of this identity.
For part a, I turned the combinations into factorials and tried to get the RHS equal to the LFS, which is $\frac{n!}{2!(n-2)!}$. However, I got stuck on the third step with all the $k$'s and $(n-k)!$'s.
For part b, I got as far as saying you choose 2 kids out of n kids to receive candy on the LHS. I see the $k$ and $n-k$ in a way accounts for each other on the right but I cannot explain this in words.
I am fairly new to mathematical proofs and any help is appreciated. Thanks!
Best Answer
HINT: For (a), you have
$$\binom{k}2+k(n-k)+\binom{n-k}2=\frac{k!}{2!(k-2)!}+k(n-k)+\frac{(n-k)!}{2!(n-k-2)!}\;.$$
Start by doing a lot of cancellation:
$$\begin{align*} \frac{n!}{(n-2)!}&=n(n-1)\\ \frac{k!}{(k-2)!}&=k(k-1)\;,\text{ and }\\ \frac{(n-k)!}{(n-k-2)!}&=(n-k)(n-k-1)\;. \end{align*}$$
Once you’ve done that, the algebra becomes very straightforward.
For (b), suppose that there are $k$ boys and $n-k$ girls. Then $\binom{k}2$ is the number of ways to choose two boys, $\binom{n-k}2$ is the number of ways to choose two girls, and $k(n-k)$ is the number of ways to choose ... what?