To prove the identity $k \binom{k}{n} = n \binom{k-1}{n-1}$ using a combinatorial argument, let’s analyze both sides in the context of counting the same combinatorial situation in two different ways.

Combinatorial Argument:

Left-Hand Side: $k \binom{k}{n}$

• $\binom{k}{n}$ represents the number of ways to choose $n$ items from a set of $k$ items.
• $k$ represents the $k$ choices for identifying one specific item from the $k$ items.
• Thus, $k \binom{k}{n}$ counts the total number of ways to:
  1. First pick $n$ items from $k$ items.
  2. Then pick one specific item out of the $k$ total items (possibly one of the $n$ chosen ones or not).

Right-Hand Side: $n \binom{k-1}{n-1}$

• $\binom{k-1}{n-1}$ represents the number of ways to choose $n-1$ items from $k-1$ items.
• $n$ represents the $n$ choices for identifying one specific item from the $n$ items chosen in the final set of $n$.
• Thus, $n \binom{k-1}{n-1}$ counts the total number of ways to:
  1. First select one item to include in the set of $n$ (this will later be the "distinguished item").
  2. Then pick $n-1$ additional items from the remaining $k-1$ items.

Why They Are Equal

Both sides count the same combinatorial process: the number of ways to select $n$ items from $k$ items where one of the selected $n$ items is "distinguished" or "special."

• In the left-hand approach, the distinction of the "special" item occurs after choosing all $n$ items from $k$.
• In the right-hand approach, the "special" item is chosen first, and then the remaining $n-1$ items are selected.

Since both sides count the same quantity, we conclude: $k \binom{k}{n} = n \binom{k-1}{n-1}.$

Let me know if you'd like to explore further explanations or examples! Here are five related questions:

1. Can this identity be generalized for any $r$-combinations?
2. How does this identity connect to the Pascal triangle?
3. Can you derive the same formula algebraically rather than combinatorially?
4. What is the interpretation of $\binom{k}{n}$ when $k = n$?
5. How is this formula useful in probability or game theory?

Tip: When proving combinatorial identities, always look for "counting the same thing in two ways" as the core idea.