作业帮容斥原理不用数学归纳法如何证明查了半天都是数学归纳法的证明.请问可以不用数学归纳法证明容斥原理吗?
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/04 05:53:22
容斥原理不用数学归纳法如何证明查了半天都是数学归纳法的证明.请问可以不用数学归纳法证明容斥原理吗?
容斥原理不用数学归纳法如何证明
查了半天都是数学归纳法的证明.请问可以不用数学归纳法证明容斥原理吗?
容斥原理不用数学归纳法如何证明查了半天都是数学归纳法的证明.请问可以不用数学归纳法证明容斥原理吗?
首先说明一点,数学归纳法原理是自然数的公理之一.
所以关于自然数的命题基本上都有数学归纳法背景.
常用的"依此类推","..."这样的写法本质上也是数学归纳法的简略形式.
要在"形式上"不用数学归纳法证明容斥原理,可以用二项式定理.
设A[1],A[2],...,A[n]是n个集合,用|S|表示集合S的元素个数,C(m,k)表示m中选k的组合数.
证明容斥原理:|A[1]∪A[2]∪...∪A[n]| = ∑{1 ≤ i ≤ n} |A[i]|-∑{1 ≤ i < j ≤ n} |A[i]∩A[j]|
+∑{1 ≤ i < j < k ≤ n} |A[i]∩A[j]∩A[k]|-...+(-1)^(n-1)·|A[1]∩A[2]∩...∩A[n]|.
对任意x ∈ A[1]∪A[2]∪...∪A[n],设A[1],A[2],...,A[n]中恰有m个集合包含x.
A[i]∩A[j]包含x当且仅当A[i]与A[j]都包含x.
因此在A[1],A[2],...,A[n]的两两之交中恰有C(m,2)个交集包含x.
在三三之交中恰有C(m,3)个集合包含x,依此类推.
可知在右端的和式中,x被计数的次数为C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1).
而由二项式定理,有0 = (1-1)^m = 1-C(m,1)+C(m,2)-C(m,3)+...+(-1)^m.
即C(m,1)-C(m,2)+C(m,3)-...+(-1)^(m-1) = 1.
A[1]∪A[2]∪...∪A[n]中的任意元素,在右端和式中恰好被计数1次.
即证明了容斥原理.