我们要证明的公式是容斥原理(Inclusion-Exclusion Principle),它用于计算有限个集合的并集的元素个数。具体地:
设 {Ai∣i∈In} 是一族有限集,其中 In={1,2,⋯,n},则有:
i=1⋃nAi=k=1∑n(−1)k−1K⊂In∣K∣=k∑α∈K⋂Aα
我们将使用数学归纳法来证明这个等式。
基础情况:n=1
当 n=1 时,只有集合 A1,所以:
i=1⋃1Ai=∣A1∣
右边为:
k=1∑1(−1)k−1K⊂I1∣K∣=k∑α∈K⋂Aα=(−1)0⋅∣A1∣=∣A1∣
左右两边相等,成立。
归纳假设:
假设对于某个 n=m,命题成立,即:
i=1⋃mAi=k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K⋂Aα
归纳步骤:证明 n=m+1 成立
我们考虑:
i=1⋃m+1Ai=(i=1⋃mAi)∪Am+1
利用两个集合的并集公式:
∣X∪Y∣=∣X∣+∣Y∣−∣X∩Y∣
令 X=⋃i=1mAi,Y=Am+1,则:
i=1⋃m+1Ai=∣X∣+∣Y∣−∣X∩Y∣
由归纳假设,我们知道:
∣X∣=k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K⋂Aα
而 X∩Y=(⋃i=1mAi)∩Am+1=⋃i=1m(Ai∩Am+1)
因此我们可以再次用归纳假设(对 Bi=Ai∩Am+1)得到:
∣X∩Y∣=k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K⋂(Aα∩Am+1)=k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K∪{m+1}⋂Aα
现在代入原式:
i=1⋃m+1Ai=∣X∣+∣Y∣−∣X∩Y∣
=k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K⋂Aα+∣Am+1∣−k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K∪{m+1}⋂Aα
将第一项和第三项合并,注意符号变化:
=k=1∑m(−1)k−1K⊂Im∣K∣=k∑α∈K⋂Aα+∣Am+1∣+k=1∑m(−1)(k+1)−1K⊂Im∣K∣=k∑α∈K∪{m+1}⋂Aα
注意到最后那个求和项可以写成:
k=1∑m(−1)kK⊂Im∣K∣=k∑α∈K∪{m+1}⋂Aα
这相当于所有包含 m+1 的子集 K′⊂Im+1,其中 m+1∈K′,且 ∣K′∣=k+1。
于是整个表达式可以整理为:
k=1∑m+1(−1)k−1K⊂Im+1∣K∣=k∑α∈K⋂Aα
这就完成了从 n=m 到 n=m+1 的归纳步骤。
结论:
由数学归纳法,对所有正整数 n,都有:
i=1⋃nAi=k=1∑n(−1)k−1K⊂In∣K∣=k∑α∈K⋂Aα
证毕 ✅
如有需要,我也可以帮你解释这个公式的直观含义或举例子说明它的应用。