线性递推关系毕业论文

【定义】一般地，如果一个数列从第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 ，…的地推关系和初始条件，通过求解递推关系，确定算法所需要的时间。 例如计算快速排序，归并排序,选择排序等。详见数据结构。