6
$\begingroup$

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!

$\endgroup$
7
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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*}

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.