请求对组合恒等式∑ₖ=iⁿ C(n,k)C(k,i)=C(n,i)·2ⁿ⁻ᵢ做概念性解释

Let me walk you through this with a simple, relatable scenario—no algebraic manipulation needed, just counting the same thing two different ways!

What the left-hand side (LHS) counts #

Think of this as a two-step process for building a team from n total people:

• First, pick any subset of k people (where k is at least i, since we need to pick i core members from them). There are $\binom{n}{k}$ ways to do this.
• Then, from that k-person subset, select i people to be the core team members. That's $\binom{k}{i}$ ways.
• We sum this over every possible valid k (from i to n) to account for all possible team sizes that can support a core of i people.

What the right-hand side (RHS) counts #

Now let's flip the order of operations—we get the exact same total number of outcomes, but it's easier to compute:

• First, directly pick the i core team members from the n people. There are $\binom{n}{i}$ ways to choose this core group.
• For the remaining n-i people, each one has two choices: either they join the larger team (alongside the core) or they don't. That's $2^{n-i}$ total combinations of additional team members.

Why they're equal #

Both sides are counting the exact same set of possibilities: every possible pair of (a team of size ≥i, a core of i members from that team). We're just breaking down the selection process in two different orders, so the total count has to be identical.

内容的提问来源于stack exchange，提问作者B.Li