如何用容斥原理（IEP）证明∑ₖ=₀ⁿ (-1)^k C(n,k)=0？

嘿，作为离散数学新手，把容斥原理和这个二项式等式联系起来确实有点抽象——别担心，我用一个简单的场景一步步给你讲清楚，保证你能跟上！

首先，先快速回顾容斥原理的核心：它是通过「加加减减」来计算不满足任何给定性质的元素个数。对于n个性质A₁, A₂, ..., Aₙ，公式是：

|A₁' ∩ A₂' ∩ ... ∩ Aₙ'| = |U| - ∑|Aᵢ| + ∑|Aᵢ∩Aⱼ| - ∑|Aᵢ∩Aⱼ∩Aₖ| + ... + (-1)ⁿ|A₁∩A₂∩...∩Aₙ|

这里的U是我们讨论的全集，Aᵢ'表示「不满足性质Aᵢ」的元素集合，∑符号分别对应选择1个、2个、…、n个性质的所有组合。

构造匹配的场景 #

我们可以用一个极简的场景来贴合这个等式：

• 设全集U是仅含1个元素的集合，比如 U = {x}
• 定义n个性质A₁, A₂, ..., Aₙ：每个Aᵢ都表示「元素x具有性质Aᵢ」（换句话说，每个Aᵢ其实就是全集U本身，因为x必然满足每个Aᵢ）

分析容斥公式的左右两边 #

左边：不满足任何性质的元素个数

|A₁' ∩ A₂' ∩ ... ∩ Aₙ'| 这个集合代表「x不满足A₁到Aₙ中的任何一个性质」。但我们定义每个Aᵢ都是x必然满足的性质，所以不存在这样的元素——这个集合是空集，大小为0。

右边：用容斥展开计算

我们把容斥公式的右边逐项展开：

• |U| = 1：对应求和式中k=0的项，即 (-1)^0 C(n,0) = 1*1 = 1
• -∑|Aᵢ|：每个Aᵢ都是U，所以|Aᵢ|=1，总共有C(n,1)个这样的项，这部分等于 -C(n,1)*1，对应求和式中k=1的项 (-1)^1 C(n,1) = -C(n,1)
• +∑|Aᵢ∩Aⱼ|：任意两个性质的交集还是U，|Aᵢ∩Aⱼ|=1，总共有C(n,2)个项，这部分等于 +C(n,2)*1，对应求和式中k=2的项 (-1)^2 C(n,2) = +C(n,2)
• 以此类推，对于任意k（0≤k≤n），选择k个性质的交集大小都是1，共有C(n,k)个这样的交集，所以这部分在容斥公式中的项是 (-1)^k * C(n,k)*1

把右边全部写出来，就是：
1 - C(n,1) + C(n,2) - C(n,3) + ... + (-1)^n C(n,n)

等式成立 #

因为容斥公式的左边等于0，右边正好是我们要证明的求和式，所以：
∑ₖ=₀ⁿ (-1)^k C(n,k) = 0

（注：当n=0时，求和式结果为1，这是因为没有性质时，「不满足任何性质」的元素就是全集U本身，大小为1，符合(1-1)^0=1的结果，题目中的等式针对n≥1的情况）

举个例子验证（n=3） #

求和式计算：1 - 3 + 3 - 1 = 0
用容斥原理验证：U={x}，三个性质都是{x}，不满足任何性质的集合是空集，大小为0；容斥计算：1 - 3*1 + 3*1 - 1*1 = 0，完全匹配！

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