《数列、排列组合的精讲与习题讲解》由会员分享，可在线阅读，更多相关《数列、排列组合的精讲与习题讲解（6页珍藏版）》请在金锄头文库上搜索。
1、1数列、排列组合的精讲与习题讲解数列、排列组合的精讲与习题讲解数列数列 归纳法归纳法 递归数列递归数列 满足递推公式的数列称为递归数列满足递推公式的数列称为递归数列。 特征方程特征方程1.设设其中其中，求，求012ni 1i+2ia1,a ,a ,a0aaa ,i1,2,n2LL+且n2的最小值。的最小值。012na +a +a +aL解：取，若用 u 除一下，则得到nn 1n-2n 1nn-3n-2n 1a0au,aa+au,aa+a2u-由了斐波那契级数。取（u 为待定常数）01nn 1n 2F0,F1,FFF,n2,3,Lin iauF1由于，猜测它为最小值。0n n1auF1,u=Fn
2、nii i=0i 0n1aFF可以证明nin 2 i=0FF1用归纳法当时，成立n002F0,F1=0设时成立nk当时，可知等式成立。nk1k+1ik 1k+2k+3 i=1FFF1=F1可以证明所求的最小值为nM只要证：01nna +a +aML下面用归纳法证明。当时，设满足条件n2012a ,a ,a则且，0a10121aa +a01242 21a +a +a2=(F1)MF当时，由，n=321a1 a 012311553 31a +a +a +a1 a1 aa2=(F1)MF 当时，设满足题设条件，则n412340a ,a ,a ,a ,a0121a1,ca0,a1 a1 c 2由于34
3、201234aaa1 c, a +a +a +aa1+c+2(1-c)=3-c 另一方面，由，从而231a +aac01234a +a +a +a +a1 cc12c 01234a +a +a +a +amax(3c,12c)例 1：已给定实数，使得，令，, 0x1f(x)(x)x1 求 存在非负整数 k 使得M= uR(k)1f(u) 其中若 k 为正整数，(k) 0 00kff ffL14 2 4 3 个 0fuu, uR 解：化为数列问题：，0xun n+1xx,u0,1,2,x1 Lk1M= uRx 使得先看系数的二阶行列式 111 （i）即0 1当 ，于是1x, x1 x1 1M （
4、ii）,特征方程：，即112, 令nnnx y x 设，则0,0n 1n 1 n n 1n 1x x1yx x1 3n 1n 1n 1x11y1+1+x 所以0 nn n00x11y() y()1+1+x 令，即：n1x nyn 01() y1+1+1-可得n 1n 1nn 1n 1(1+)(1-) x,n0,1,2(1+)(1-) Ln 1n 1n 1n 1(1+)(1-) Mn0,1,2(1+)(1-) L例 1 设。证明，这样的数列只有一个。.)2 , 1 , 0( , 0, 1210naaaaannnn分析：都是已知的，由知数列是唯一确定的。10,aa21nnnaaa证：nnnaaa1
5、2012nnnaaa特征方程：012 xx解出特征根2512, 1xnn ncca)251()251(210, 0nnana由，0)251(n0)251(n，由1|251|0,nan4知 c2=0若不然， （1）c20,当 n 取充分大的奇数时， 0na（2）c20,当 n 取充分大的偶数时， 0na都出现矛盾， n nca)251(1由1)251(110 10cca 0)251(1n na例 2122322( 5),.:,rnA AArA AAAL LU111任何个不同的集合, 证明: 其中至少存在r=2n 个不同集合使得这个集合中任何一个集合不是另外两个集合的并集.分析:(1)先从n个给定
6、的集合中选出满足下列条件的集合: 任何一个集合不是另外两个集合的并集.(2)再证明挑出的集合个数r=2n证明设这n个集合中元素个数最少的两个集合为A是除A和外且不是A的其余集合中元素个数最3222212,(0,(2)11:,2)2421112(,)42 ,kkkkAAAAAAAnkck knkkntnt nttA A L LLLLL111K+1K+1少的一个(是存在的, 因为n5),当A选好后, 在A以外且不是A中任何两个集合之并的其余集合中选元素个数最少的一个作为A当时A 存在即时亦即时设给定所以是唯一确定的一个正整数有上面的分析可知可以选出个集合,tA 满足题中要求522222211224
7、2 (1)1(1)trtnttntttttttttt ttt 下面证明2n由2n例例 36,3 63 6个点每两个点之间有一条线相连线染上红色或蓝色证明一定有两个以这些点为顶点的三角形, 每个三角形的边是同一种颜色(可能有公共的边)分析: 我们称三边同色的三角形为同色三角形设为X个, 本题证X2则异色三角形共有(C-x)个下面计算图形中同色角的个数S(1)S=3x+1(C-x)=2x+20同色 红 兰 兰 红红 兰 (2) r 条红边 一个点 因为 6 个点,所以从任一点发出的边共 5 条兰边 设 5 条中有 r 条边为红,5-r 条边为蓝 兰边 以这个点为顶点的同色角为2222 53240,
8、1,2,3,4,5rrCCCCr6424(1)(2)22024220242SxSxx综合得函数迭代函数迭代 定义和符号定义和符号 设 f(x)是定义在集合 M 上并在 M 上取值的函数，归纳地定义函数迭代如下：f(1)(x)=f(x) (xM) f(n)(x)=f(f(n-1)(x) (xM) (n2) f(n)(x)称为函数 f(x)的 n 次迭代。 有时还规定 f(0)(x)=f(x) (xM) 1设设 f(x)=x2+px+q, A=x|x=f(x), B=x|ff(x)=x。 求证：AB；如果 A=1,3，求 B。6解析：设 x0是集合 A 中的任一元素，即有 x0AA=x|x=f(x) x0=f(x0)ff(x0)=f(x0)=x0x0B AB A=1,3=x|x2+px+q=x=x|x2+(p-1)x+q=0f(x)= x2-x-3 qp 3) 1() 1(31 31 qpff(x)=xx4-2x3-6x2+6x+9=0(x2-2x-3)(x2-3)=0x=-1 或 3 或或-33B=-1,3,-,。33
