(combinatorial proof) Let n and k be arbitrary integers such that 0 ≤ k ≤ n. Using the fact that
n
2

is the number of edges in Kn, find a
combinatorial, not algebraic, proof of the following identity:

Question

(combinatorial proof) Let n and k be arbitrary integers such that 0 ≤ k ≤ n. Using the fact that
n
2

is the number of edges in Kn, find a
combinatorial, not algebraic, proof of the following identity:

bee_see · Answer

attachment

ybarrap · Answer

Take for example, $n=5$ and $k=2$. The number of ways to group 5 people in groups of 2 can be broken down into 3 mutually exclusive ways:
A) Number of ways that the $n-k$ people can form groups of 2
B) Number of ways that $k$ people can form groups of 2
C) Number of ways that each of the $n-k$ people can be grouped with an individual from the $k$ group.
|dw:1448851067610:dw|

So A is the number of ways of forming a group of 2 $within$ that group of $n-k$, similarly, B is the number of ways of forming a group of 2 $within$ that group of $k$ people. But you also still need to count the number of ways to match $between$ the $n-k$ and the $k$ group-- this is what C counts.

Think of C as the number of ways that 3 forks can be matched with 2 knives -- there are $3\times 2$ ways.

$$
A={n-k\choose 2}\
B={k\choose 2}\
C=k\times (n-k)
$$
The sum of these must equal to the number of ways that $n$ people can form groups of 2:$\large {n\choose2}=A+B+C$.

Does this make sense?