容斥原理不用数学归纳法如何证明
题目
容斥原理不用数学归纳法如何证明
查了半天都是数学归纳法的证明.请问可以不用数学归纳法证明容斥原理吗?
答案
首先说明一点,数学归纳法原理是自然数的公理之一.
所以关于自然数的命题基本上都有数学归纳法背景.
常用的"依此类推","..."这样的写法本质上也是数学归纳法的简略形式.
要在"形式上"不用数学归纳法证明容斥原理,可以用二项式定理.
设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次.
即证明了容斥原理.
举一反三
我想写一篇关于奥巴马的演讲的文章,写哪一篇好呢?为什么好
最新试题
- 磷矿粉是常见的磷肥,其主要成分磷酸钙[Ca3(PO4)2]中的磷元素的化合价是多少?
- 在两个直角三角形中,若有一对角(非直角)相等,一对边相等则两个直角三角形________?
- 方圆一百里是多少平方公里?
- 实验表明,常温下20°C,100克水中最多能溶解36克盐,我们把这种不能再溶解盐的盐水称为饱和食盐水,则常温下
- (a+b+c)^3>=3abc怎么证明
- 《王顾左右而言他》这个故事的原因及结果(概括在30字)
- 编一道有理数混合运算题,并满足以下条件.一必须含有加减乘除乘方5种运算;二幂底数必须是负的带分数; 三、被除数必须是负分数 四、计算结果是2007
- 如图,E,F,G,H分别是正方形ABCD各边的中点,要使中间阴影部分小正方形的面积是5,那么大正方形的边长应该是( ) A.25 B.35 C.5 D.5
- 育红小学三、四、五六年级参加献爱心捐款活动.其中三年级捐了总数的1/5
- 控制生物特征的最小单位是 ,它位于 上,实际上它是一段 分子.亲缘关系越近的生物其相同的 也越多
热门考点
- 没有目的的而悠闲的走的词语是什么
- 1-9这9个数字在下面算式个出现1次.写出这个 乘法算式4×19×()()=()()52
- 某班有44名学生,他们都订阅了甲,乙,丙,三种报刊中的若干种,(每名学生订了其中—种,两种或三种),至少有几名学生订阅的损刊是完全相同?
- 已知y=y1-y2,y1与x的平方成正比例,y2与x-1成反比例,当x=负1时,y=3;当x=2时,y=负三.求y与x之间的函
- 解方程 3y-15=y-19 4分之y+2-6分之2y-3=1 16分之x=8分之4x+5+2
- 能与AgN03溶液作用产生白色沉淀的离子是
- 一个循环小数0.604604...的小数部分,第10位是几?第50位是几?第1000位呢?
- 仿写句子 我们原想收获一缕春风,你却给了我们整个春天; ,.,.
- 物理伏安法电路中,外接与内接的区别!
- 1.杭州某风景区内一吊桥长约250米,其中250米属于( )