Algebraic and combinatorial proof of an identity

Question

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!

Answer 1

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?

Answer 2

Part (a) is straightforward: \begin{align*} \dbinom{k}{2} + k(n-k) + \dbinom{n-k}{2} &= \frac{k!}{(k-2)!2!} + k(n-k) + \frac{(n-k)!}{2!(n-k-2)!} \\ &= \frac{k(k-1)}{2} + k(n-k) + \frac{(n-k)(n-k-1)}{2} \\ &= \frac{k^2-k+2nk-2k^2 + n^2 - 2nk - n + k^2 + k}{2} \\ &= \frac{n(n-1)}{2} = \dbinom{n}{2}. \end{align*}

Answer 3

Part (b) is also straightforward. The LHS measures how many ways there are to choose 2 balls from n. This is the same as counting the ways to choose 2 from the first k, or 2 from the last n-k, or one in the first k and one in the last n-k.