线性递推关系毕业论文

二阶级特征方程解决数列相关问题原理是特征方程的原理。一个数列:X(n+2)=C1X(n+1)+C2X(n)设r，s使X(n+2)-rX(n+1)=s[X(n+1)-rXn]所以X(n+2)=(s+r)X(n+1)-srXnC1=s+rC2=-sr消去s就导出特征方程式 r*r-C1*r-C2=0特征方程用于求解特征向量.递推是中学数学中一个非常重要的概念和方法，递推数列问题能力要求高，内在联系密切，蕴含着不少精妙的数学思想和数学方法。新教材将数列放在高一讲授，并明确给出“递推公式”的概念：如果已知数列na的第1项（或前几项），且任一项na与它的前一项1na（或前几项）间的关系可以用一个公式来表示，那么这个公式叫做数列的递推公式。有通项公式的数列只是少数，研究递推数列公式给出数列的方法可使我们研究数列的范围大大扩展。新大纲关于递推数列规定的教学目标是“了解递推公式是给出数列的一种方法，并能根据递推公式写出数列的前几项”，但从近几年来高考试题中常以递推数列或与其相关的问题作为能力型试题来看，这一目标是否恰当似乎值得探讨，笔者以为“根据递推公式写出数列的前几项”无论从思想方法还是从培养能力上来看，都不那么重要，重要的是学会如何去发现数列的递推关系，学会如何将递推关系转化为数列的通项公式的方法。本文以线性递推数列通项求法为例，谈谈这方面的认识。

【定义】一般地，如果一个数列从第2项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列（arithmetic sequence），这个常数叫做等差数列的公差（common difference），公差通常用字母d表示。【缩写】等差数列可以缩写为.（Arithmetic Progression）。【等差中项】由三个数a，A，b组成的等差数列可以堪称最简单的等差数列。这时，A叫做a与b的等差中项（arithmetic mean）。有关系：A＝（a＋b）/2【通项公式】an=a1+(n-1)dan=Sn-S(n-1) (n≥2)【前n项和】Sn=n(a1+an)/2=n*a1+n(n-1)d/2【性质】且任意两项am，an的关系为：an=am+(n-m)d它可以看作等差数列广义的通项公式。 从等差数列的定义、通项公式，前n项和公式还可推出：a1+an=a2+an-1=a3+an-2=…=ak+an-k+1，k∈{1,2,…,n} 若m，n，p，q∈N*，且m+n=p+q，则有am+an=ap+aqSm-1=(2n-1)an，S2n+1=(2n+1)an+1Sk，S2k-Sk，S3k-S2k，…，Snk-S(n-1)k…或等差数列，等等。和＝（首项＋末项）×项数÷2 项数＝（末项-首项）÷公差＋1 首项=2和÷项数-末项末项=2和÷项数-首项设a1,a2,a3为等差数列。则a2为等差中项,则2倍的a2等于a1+a3，即2a2=a1+a3。等比数列【定义】一般地，如果一个数列从第2项起，每一项与它的前一项的比等于同一个常数，这个数列就叫做等比数列（geometric sequence）。这个常数叫做等比数列的公比（common ratio），公比通常用字母q表示。【缩写】等比数列可以缩写为.（Geometric Progression）。【等比中项】如果在a与b中间插入一个数G，使a，G，b成等比数列，那么G叫做a与b的等比中项。有关系：G^2＝ab；G＝±(ab)^(1/2)注：两个非零同号的实数的等比中项有两个，它们互为相反数，所以G^2=ab是a,G,b三数成等比数列的必要不充分条件。【通项公式】an=a1q^(n-1)an=Sn-S(n-1) (n≥2)【前n项和】当q≠1时，等比数列的前n项和的公式为Sn=a1(1-q^n)/(1-q)=(a1-an*q)/(1-q) (q≠1)【性质】任意两项am，an的关系为an=am·q^(n-m)（3）从等比数列的定义、通项公式、前n项和公式可以推出： a1·an=a2·an-1=a3·an-2=…=ak·an-k+1，k∈{1,2,…,n} （4）等比中项：aq·ap=ar^2，ar则为ap，aq等比中项。记πn=a1·a2…an，则有π2n-1=(an)2n-1，π2n+1=(an+1)2n+1另外，一个各项均为正数的等比数列各项取同底数数后构成一个等差数列；反之，以任一个正数C为底，用一个等差数列的各项做指数构造幂Can，则是等比数列。在这个意义下，我们说：一个正项等比数列与等差数列是“同构”的。 性质： ①若 m、n、p、q∈N*，且m＋n=p＋q，则am·an=ap·aq； ②在等比数列中，依次每 k项之和仍成等比数列. “G是a、b的等比中项”“G^2=ab（G≠0）”.(5) 等比数列前n项之和Sn=A1(1-q^n)/(1-q)在等比数列中，首项A1与公比q都不为零. 注意：上述公式中A^n表示A的n次方。一般数列的通项求法一般有：an=Sn-Sn-1 （n≥2）累和法（an-an-1=... an-1 - an-2=... a2-a1=...将以上各项相加可得an）。逐商全乘法（对于后一项与前一项商中含有未知数的数列）。 化归法（将数列变形，使原数列的倒数或与某同一常数的和成等差或等比数列）。特别的：在等差数列中，总有Sn S2n-Sn S3n-S2n2(S2n-Sn)=(S3n-S2n)+Sn即三者是等差数列,同样在等比数列中。三者成等比数列不动点法（常用于分式的通项递推关系）数列前N项和公式的求法(一)1.等差数列: 通项公式an=a1+(n-1)d 首项a1,公差d, an第n项数 an=ak+(n-k)d ak为第k项数 若a,A,b构成等差数列 则 A=(a+b)/2 2.等差数列前n项和: 设等差数列的前n项和为Sn 即 Sn=a1+a2+...+an; 那么 Sn=na1+n(n-1)d/2 =dn^2(即n的2次方) /2+(a1-d/2)n 还有以下的求和方法: 1,不完全归纳法 2 累加法 3 倒序相加法 (二)1.等比数列: 通项公式 an=a1*q^(n-1)(即q的n-1次方) a1为首项,an为第n项 an=a1*q^(n-1),am=a1*q^(m-1)则an/am=q^(n-m) (1)an=am*q^(n-m) (2)a,G,b 若构成等比中项,则G^2=ab (a,b,G不等于0) (3)若m+n=p+q 则 am×an=ap×aq 2.等比数列前n项和 设 a1,a2,a3...an构成等比数列 前n项和Sn=a1+a2+a3...an Sn=a1+a1*q+a1*q^2+....a1*q^(n-2)+a1*q^(n-1)(这个公式虽然是最基本公式,但一部分题目中求前n项和是很难用下面那个公式推导的,这时可能要直接从基本公式推导过去,所以希望这个公式也要理解) Sn=a1(1-q^n)/(1-q)=(a1-an*q)/(1-q); 注: q不等于1; Sn=na1 注:q=1 求和一般有以下5个方法: 1,完全归纳法（即数学归纳法） 2 累乘法 3 错位相减法 4 倒序求和法 5 裂项相消法

以A(n+2)-3A(n+1)+2A(n)=0,假定A（1）=2，A（2）=3，求A(n)。特征方程为x^2-3x+2=0,两根为1和2。利用根1，可以这样处理方程：[A(n+2)-A(n+1)]-2[A(n+1)-A(n)]=0 即可得到：[A(n+2)-A(n+1)]/[A(n+1)-A(n)]=2 此时令B（n）=A(n+1)-A(n)为等比数列，q=2，所以B(n)=2^（n-1)[A(2)-A(1)]=2^（n-1) 即A(n+1)-A(n)=2^（n-1)同理可以得到A（n+2)-2A(n+1)=A(n+1)-2A(n) C(n)=A(n+1)-2A(n)=-1联立 A(n+1)-A(n)=2^（n-1)和A(n+1)-2A(n)=-1 即可得出 A(n)=2^(n-1)+1 亦即A（n)=2^(n-1) +1^(n-1)也就是像这种二阶级特征方程数列问题，结果都是y=aX(1)^(n-1)+bX(2)^(n-1)X(1),X(2)是特征根，a,b由初始条件联立方程可以求得。 另外特征根不是有理数也没关系，只要是实数就行，兔子数列每个数都是整数，但其通项里却有无理数。特征方程为x^2-x-1=0,初始条件为A(1)=A(2)=1你可以求求看。 希望可以帮到你。

原理：一般地，如果一个数列从第2项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列（arithmetic sequence），这个常数叫做等差数列的公差（common difference），公差通常用字母d表示。【缩写】等差数列可以缩写为.（Arithmetic Progression）。【等差中项】由三个数a，A，b组成的等差数列可以堪称最简单的等差数列。这时，A叫做a与b的等差中项（arithmetic mean）。有关系：A＝（a＋b）/2【通项公式】an=a1+(n-1)dan=Sn-S(n-1) (n≥2)【前n项和】Sn=n(a1+an)/2=n*a1+n(n-1)d/2【性质】且任意两项am，an的关系为：an=am+(n-m)d它可以看作等差数列广义的通项公式。 从等差数列的定义、通项公式，前n项和公式还可推出：a1+an=a2+an-1=a3+an-2=…=ak+an-k+1，k∈{1,2,…,n} 若m，n，p，q∈N*，且m+n=p+q，则有am+an=ap+aqSm-1=(2n-1)an，S2n+1=(2n+1)an+1Sk，S2k-Sk，S3k-S2k，…，Snk-S(n-1)k…或等差数列，等等。和＝（首项＋末项）×项数÷2 项数＝（末项-首项）÷公差＋1 首项=2和÷项数-末项末项=2和÷项数-首项设a1,a2,a3为等差数列。则a2为等差中项,则2倍的a2等于a1+a3，即2a2=a1+a3。等比数列【定义】一般地，如果一个数列从第2项起，每一项与它的前一项的比等于同一个常数，这个数列就叫做等比数列（geometric sequence）。这个常数叫做等比数列的公比（common ratio），公比通常用字母q表示。【缩写】等比数列可以缩写为.（Geometric Progression）。【等比中项】如果在a与b中间插入一个数G，使a，G，b成等比数列，那么G叫做a与b的等比中项。有关系：G^2＝ab；G＝±(ab)^(1/2)注：两个非零同号的实数的等比中项有两个，它们互为相反数，所以G^2=ab是a,G,b三数成等比数列的必要不充分条件。【通项公式】an=a1q^(n-1)an=Sn-S(n-1) (n≥2)【前n项和】当q≠1时，等比数列的前n项和的公式为Sn=a1(1-q^n)/(1-q)=(a1-an*q)/(1-q) (q≠1)【性质】任意两项am，an的关系为an=am·q^(n-m)（3）从等比数列的定义、通项公式、前n项和公式可以推出： a1·an=a2·an-1=a3·an-2=…=ak·an-k+1，k∈{1,2,…,n} （4）等比中项：aq·ap=ar^2，ar则为ap，aq等比中项。记πn=a1·a2…an，则有π2n-1=(an)2n-1，π2n+1=(an+1)2n+1另外，一个各项均为正数的等比数列各项取同底数数后构成一个等差数列；反之，以任一个正数C为底，用一个等差数列的各项做指数构造幂Can，则是等比数列。在这个意义下，我们说：一个正项等比数列与等差数列是“同构”的。 性质： ①若 m、n、p、q∈N*，且m＋n=p＋q，则am·an=ap·aq； ②在等比数列中，依次每 k项之和仍成等比数列. “G是a、b的等比中项”“G^2=ab（G≠0）”.(5) 等比数列前n项之和Sn=A1(1-q^n)/(1-q)在等比数列中，首项A1与公比q都不为零. 注意：上述公式中A^n表示A的n次方。一般数列的通项求法一般有：an=Sn-Sn-1 （n≥2）累和法（an-an-1=... an-1 - an-2=... a2-a1=...将以上各项相加可得an）。逐商全乘法（对于后一项与前一项商中含有未知数的数列）。 化归法（将数列变形，使原数列的倒数或与某同一常数的和成等差或等比数列）。特别的：在等差数列中，总有Sn S2n-Sn S3n-S2n2(S2n-Sn)=(S3n-S2n)+Sn即三者是等差数列,同样在等比数列中。三者成等比数列不动点法（常用于分式的通项递推关系）数列前N项和公式的求法(一)1.等差数列: 通项公式an=a1+(n-1)d 首项a1,公差d, an第n项数 an=ak+(n-k)d ak为第k项数 若a,A,b构成等差数列 则 A=(a+b)/2 2.等差数列前n项和: 设等差数列的前n项和为Sn 即 Sn=a1+a2+...+an; 那么 Sn=na1+n(n-1)d/2 =dn^2(即n的2次方) /2+(a1-d/2)n 还有以下的求和方法: 1,不完全归纳法 2 累加法 3 倒序相加法 (二)1.等比数列: 通项公式 an=a1*q^(n-1)(即q的n-1次方) a1为首项,an为第n项 an=a1*q^(n-1),am=a1*q^(m-1)则an/am=q^(n-m) (1)an=am*q^(n-m) (2)a,G,b 若构成等比中项,则G^2=ab (a,b,G不等于0) (3)若m+n=p+q 则 am×an=ap×aq 2.等比数列前n项和 设 a1,a2,a3...an构成等比数列 前n项和Sn=a1+a2+a3...an Sn=a1+a1*q+a1*q^2+....a1*q^(n-2)+a1*q^(n-1)(这个公式虽然是最基本公式,但一部分题目中求前n项和是很难用下面那个公式推导的,这时可能要直接从基本公式推导过去,所以希望这个公式也要理解) Sn=a1(1-q^n)/(1-q)=(a1-an*q)/(1-q); 注: q不等于1; Sn=na1 注:q=1 求和一般有以下5个方法: 1,完全归纳法（即数学归纳法） 2 累乘法 3 错位相减法 4 倒序求和法 5 裂项相消法

定义：建立序列中第n项与其前趋元素间的关系递归算法的分析。 递推关系an a 1 =5 初始条件 a n = a n-1 +3 n≥2 a 2 =a 1 +3=5+3=8 a 3 =a 2 +3 = 8+3=11 递推关系是由数列第n项前的若干项确定第n项,并由此确定数列。

数列a 0 ,a 1 , ...的递推关系是一个由a 0 ,a 1 ,… a n-1 中的一些或全部确定a n 的等式。 数列a 0 .,a 1 , ...的初始条件是对数列的有限个元素给定的确定值。

递推关系f n =f n-1 +f n-2 （n≥3） 且 初始条件f 1 =1 f 2 =2

递推关系、递归算法、数学归纳法 三者间关系非常密切！ 例：S n 不含111的n位二进制字符串的个数，确定递推关系。 解： 以0开始的 以10开始的 以110开始的 S n = S n-1 +S n-2 n≥4 S 1 =2,S 2 =4，S 3 =7 C k-1 *C n-k

思路：(0,0) → （k，k）→（n，n）通项公式如下：

C n 移动次数 C n =2C n-1 +1 n≥2 C 1 =1 其通项公式为：

习题：P219,1,4,5,37

方法：数列a 0 ,a 1 …a n :的通项公式a n . 代入法 定常系数线性齐次递推关系 例 1 ：S n =2S n-1 S 0 =1。 例 2 ：a 1 =2，a n =a n-1 +3 n≥2

常系数线性齐次递推关系 形如a n =c 1 a n-1 +c 2 a n-2 + ... +c k a n-k c k ≠0的递推关系称为常系数线性齐次递推关系 K阶常系数线性齐次递推关系

设a n = c 1 a n-1 +c 2 a n-2 是2阶常系数线性齐次递推关系，如果S，T是解，则U=bS+dT也是解 如果r是t 2 - c 1 *t -c 2 =0的根，则r n 是解。 a 0 =c 0 ，a 1 =c 1 r 1 ，r 2 是t 2 -c 1 *t -c 2 =0的不同的根，则存在b，d使得

例：鹿群n=0:200n=1 : 220 从n-1到n的增长头数为n-2到n-1的增长头数的两倍，写出递推关系，求通项公式。 定理 r 1 = r 2 设a n = c 1 a n-1 + C 2 a n-2 是2阶常系数线性齐次递推关系 a 0 =c 0 ,a 1 =c 1 r 1 =r 2 =r是t 2 -c 1 t-c 2 =0的(同)根，则存在b，d使得 例：d n =4（d n-1 -d n-2 ） d 0 =d 1 =1 t 2 -4t+4=0 r 1 =r 2 =2 d n =b 2 n +d* n 2 n 且d 0 =d 1 =1 d 0 =1=b2 0 + d * 0 * 2 n =b d 1 =1=b * 2 1 +d * 1 * 2 1 =2 b+2*d=1 b=1,d=-1/2 d n =2 n -n * 2 n-1 习题：P231,1,4,14,22

k阶常系数线性齐次递推关系 如果r是方程t k -c 1 t k-1 -c 2 t k-2 -…=0的m重根， 则可证明r n ,n r n ,…,n m-1 r n 都是解

用递推关系分析算法运行的时间 基本思想： a n 表输入量为n时算法运行的时间 确定数列a 0 ，a 1 ，…的地推关系和初始条件，通过求解递推关系，确定算法所需要的时间。 例如计算快速排序，归并排序,选择排序等。详见数据结构。