请求证明组合恒等式：C(n,0)+C(n+1,1)+…+C(2n,n)=C(2n+1,n)

Nice question! Let's walk through a few clear, intuitive ways to prove this combinatorial identity—whether you prefer algebraic manipulation, induction, or counting arguments that make the math feel meaningful, there's something here for you.

$$\binom{n}{0}+\binom{n+1}{1}+\binom{n+2}{2}+...+\binom{2n}{n}=\binom{2n+1}{n}$$

方法1：数学归纳法 #

This is the classic go-to for identities like this. Let's break it down step by step:

• Base case (n=0): The left-hand side (LHS) is just $\binom{0}{0} = 1$. The right-hand side (RHS) is $\binom{1}{0} = 1$. They match, so the base case holds.

• Inductive step: Assume the identity is true for some integer $k \geq 0$, meaning:
  $$\binom{k}{0} + \binom{k+1}{1} + \dots + \binom{2k}{k} = \binom{2k+1}{k}$$
  Now we need to show it works for $k+1$. Let's write out the LHS for $n=k+1$:
  $$\binom{k+1}{0} + \binom{k+2}{1} + \dots + \binom{2k+2}{k+1}$$
  Use Pascal's identity $\binom{m}{r} = \binom{m-1}{r} + \binom{m-1}{r-1}$ to rewrite every term except the first:

  • $\binom{k+2}{1} = \binom{k+1}{1} + \binom{k+1}{0}$
  • $\binom{k+3}{2} = \binom{k+2}{2} + \binom{k+2}{1}$
  • ...
  • $\binom{2k+2}{k+1} = \binom{2k+1}{k+1} + \binom{2k+1}{k}$
    Substitute these back into the LHS and rearrange terms into two separate sums:
    $$\binom{k+1}{0} + \left(\binom{k+1}{1} + \binom{k+2}{2} + \dots + \binom{2k+1}{k}\right) + \left(\binom{k+1}{0} + \binom{k+2}{1} + \dots + \binom{2k+1}{k+1}\right)$$
    The first parenthetical sum is exactly our inductive hypothesis minus $\binom{k}{0}$ (which is 1), so that's $\binom{2k+1}{k} - 1$. The second parenthetical sum equals $\binom{2k+1}{k+1}$ (since $\binom{m}{r} = \binom{m}{m-r}$, and $\binom{2k+1}{k} = \binom{2k+1}{k+1}$).

  Plugging those in and simplifying:
  $$1 + \left(\binom{2k+1}{k} - 1\right) + \binom{2k+1}{k+1} = \binom{2k+1}{k} + \binom{2k+1}{k+1}$$
  Using Pascal's identity again, this sum equals $\binom{2k+2}{k+1}$. Combining this with the shifted inductive terms, we finally get $\binom{2k+3}{k+1}$, which is exactly the RHS for $n=k+1$. The induction holds!

方法2：组合双计数法（最直观！） #

This is my favorite approach because it turns abstract math into a concrete counting problem. Let's think about what both sides represent:

• RHS: $\binom{2n+1}{n}$ counts the number of ways to choose $n$ elements from a set of $2n+1$ distinct items (let's label them $1, 2, ..., 2n+1$).

• LHS: Let's categorize these $n$-element subsets by the largest element in the subset:

  • If the largest element is $n+1$: We need to pick the remaining $n-1$ elements from the first $n$ items ($1$ to $n$). That's $\binom{n}{n-1} = \binom{n}{0}$ (since $\binom{m}{r} = \binom{m}{m-r}$).
  • If the largest element is $n+2$: We pick the remaining $n-1$ elements from $1$ to $n+1$. That's $\binom{n+1}{n-1} = \binom{n+1}{1}$.
  • ...
  • If the largest element is $2n+1$: We pick the remaining $n-1$ elements from $1$ to $2n$. That's $\binom{2n}{n-1} = \binom{2n}{n}$.

  Adding up all these cases gives exactly the sum on the LHS. Since we're counting the same collection of subsets in two different ways, the LHS must equal the RHS. It's that simple!

方法3：利用“曲棍球棒恒等式”直接推导 #

If you remember the hockey-stick identity (a staple combinatorial identity), this proof is almost one line. The hockey-stick identity states:
$$\sum_{k=0}^m \binom{r+k}{r} = \binom{r+m+1}{r+1}$$
In our problem, let $r = n$ and $m = n$. Then our sum becomes:
$$\sum_{k=0}^n \binom{n+k}{n} = \binom{n + n + 1}{n+1} = \binom{2n+1}{n+1}$$
But since $\binom{2n+1}{n+1} = \binom{2n+1}{(2n+1)-(n+1)} = \binom{2n+1}{n}$, this is exactly the RHS of our identity. Done in seconds if you recall the identity!

内容的提问来源于stack exchange，提问作者Roman83