三阶递归序列的质及其应用.doc

单位代码 01 学号 1101110049 分 类 号 024 密 级 毕业论文三阶递归序列的性质及其应用 院(系)名称信息工程学院 专业名称信息与计算科学 学生姓名 * 指导教师*2015 年 5 月 15 日 第 IV 页三阶递归序列的性质及其应用摘 要斐波那契序列是一种经典的递推关系序列，由于后来的研究发现使得斐波那契序列有越来越多的性质被人们所发现，越来越多的应用被人们所使用，因而引起了国际上好奇数学家们的极大关注上个世纪有一本专门研究它的杂志Fibonacci Quarterly (斐波那契季刊)于1963年开始发行，并且在美国还专门设立了斐波那契数委员会，研究和处理有关问题如今所发现的许多生物和生活现象也都与斐波那契数密切相关，同时其推广和应用几乎渗透到数学的各个分支，并且在物理、生物等自然科学中起着重要作用后来科学家和研究者们又将二阶的斐波那契序列进行推广，得到了广义的三阶递归序列和三阶斐波那契序列其中三阶斐波那契序列形式多样，而把三阶斐波那契序列与矩阵法联系起来，一直受到人们的青睐本文便利用三阶线性递归序列的系数矩阵的若当标准形推出了三阶斐波那契序列的通项表达式以及前n 项和计算公式的性质，并得到了一些与斐波那契数列相似的性质，本文同时也涉及了三阶斐波那契数列的运用问题关键词：递归序列，三阶斐波那契序列，若当标准型，矩阵法Third-order Recursion Sequences Properties and its Applications Author: Zou Ke Tutor: Tang FengjunAbstractThe Fibonacci sequence is a kind of classic sequence of recursive relations. Due to later studies had found that the Fibonacci sequence had more and more natures to be found, and that had more and more applies to be used by people, thus it had caused the mathematicians being curious in the world. In the last century the specializes of a magazineFibonacci Quarterly was launched in 1963.In the United States it also set up a special committee of Fibonacci number to study and deal with related issues. Now in many biological and life phenomenon are closely related to the Fibonacci Numbers. At the same time its popularization and application of pervades virtually were a branch of mathematics, and in the natural sciences such as physic, biology also played an important role.Later scientists and researchers had popularized the second order of the Fibonacci sequence, so that had obtained the generalized third-order recursion sequence and the third-order Fibonacci sequence. The three-order of the Fibonacci sequence had varied forms. As we all known, the third-order the Fibonacci sequence was linked with matrix method, also had been under the favor of people. In this paper, by using the third-order of the coefficient matrix of the linear recursion sequence when standard form being launched the third order item expressions of the Fibonacci sequence and the nature of the calculation formula of the first n items. People also got some properties which were similar to the Fibonacci sequence. This paper also involves the use of the three-order about the Fibonacci sequence problems.Keywords: Recursion sequence, the third order of the Fibonacci sequence, Jordan Standard, Matrix method目 录1 绪论11.1 斐波那契序列简介11.2 矩阵方法的背景简介22 几种初级递推序列的介绍32.1 二阶斐波那契序列32.2 卢卡斯序列33 三阶线性递归序列53.1 三阶线性递归序列的定义53.2 三阶线性递归序列特征值与通项表达式53.2.1 若序列特征根两两不同53.2.2 若序列特征根两个相等63.2.3 若序列特征根全相等74 三阶线性递推序列通项及前n项和计算公式104.1 三阶线性递推序列通项及前n项和104.2 一类特殊的3 阶线性递推序列125 三阶斐波那契数列155.1 三阶斐波那契数列和矩阵的定义155.2 三阶斐波那契数列的通项表示的矩阵法及Cassini公式165.2.1 三阶斐波那契数列的通项表示的矩阵法165.2.2 三阶斐波那契数列的通项公式的Cassini公式165.3 三阶斐波那契数列通项表示的行列式形式175.4 阶斐波那契数列及性质186 三阶线性递归序列的应用197 结论21致 谢22参考文献23 第 9 页1 绪论1.1 斐波那契序列简介1202年，意大利比萨数学家斐波那契在一本为算盘书的数学著作中，提出了如下一个有趣的问题：假定兔子出生以后两个月就能生小兔，现养了初生的小兔一对（一雄一雌），若每月不多不少恰好生一对（一雄一雌），试问一年后共有多少对兔子（如果生下的小兔都能存活的话）？由兔子繁殖问题从而引出了一个有趣的数列斐波那契数列，记为，它是一个二阶线性递推数列：设 我们将这个数列的每一项都称为斐波那契数然而人们对斐波那契数列的研究兴趣历时几百年而依然不衰就是因为它有着许多奇特而美妙的性质例如，菠萝、茉莉花、冬青、牛眼花等许多植物的花瓣数恰为斐波那契数，而且在计算数学、优化理论、运筹学等许多领域有着十分广泛的运用目前为止，人们已经定义了二阶的斐波那契矩阵，同时还给出了斐波那契数列表示通项的多种表示形式，比如解析表达式： （1.1） 矩阵法表示形式： （1.2）行列式表示形式： （1.3）及组合数表示形式，其中表示的部分整数随着人们对其理论的不断深入研究，研究者们也不断地提出了斐波那契数列多种推广形式，这其中包括定义的三阶斐波那契数列，并用待定系数法求得的其与比内公式相似的通项公式，并将其推广到阶斐波那契数列，以及用生成函数的方法求得其通项表达式，而且还给出一些相关性质的结论及研究运用本文在此理论基础上运用矩阵法的方法，对三阶斐波那契数列进行了进一步的深入研究，同时还定义出了三阶斐波那契矩阵并给出相关的定理和证明，利用它们求得三阶斐波那契数列的通项公式，并得到了一些与二阶斐波那契数列相似的性质，同时本文也涉及一些三阶斐波那契数列生活中的运用问题1.2 矩阵方法的背景简介矩阵的英文名称为Matrix矩阵这一具体概念是由19世纪英国数学家凯利首先提出并形成矩阵代数这一系统理论的，在数学术语中，矩阵是用来运算和统计各种相互关联的数据的数学上，矩阵就是由方程组的系数项及常数项所构成的方阵，把它用来解各类线性方程组上即简洁又方便直观就是因为这些数字是有规律地排列在一起，形状像一个矩形，以此后来数学家们称其为矩阵此外，矩阵的一个重要用途是解线性方程组，另一个重要用途是表示线性变换，通过矩阵各种相关运算，就可以得出各类方程组的解来，而且矩阵的特征值和特征向量可以揭示线性变换的深层特性矩阵及其理论在现代科学技术的各个领域都有广泛的应用，常见于线性代数、线性规划、组合数学以及统计分析等2 几种初级递推序列的介绍2.1 二阶斐波那契序列若一个数列，若给定一个序列的前两项的值为0和1，那么定义从第三项起，每一项都是其前两项之和，称该数列为斐波那契序列，又称黄金分割数列用数学式表示1为： ；(对所有的正整数) （2.1）经早期研究者们发现，相邻两个斐波那契数的比值随着序号的增加而逐渐趋于黄金分割数2即：公元6世纪前古希腊的毕达哥拉斯学派在研究正十边形和正五边形的作图中发现的，因此现代数学学家们推断当时的毕达哥拉斯等学派可能已经涉及甚至掌握了黄金分割这一理论公元前4世纪，古希腊的数学家欧多克索斯首先系统地研究分析了黄金分割，并建立了比例理论把一条线段分成两段，使其中较大一段与原线段的比值等于较小一段与较大一段的比值，这样的分割成为黄金分割，比值称为黑金比由于按此比例设计的造型十分美丽，因此称为黄金分割黄金分割运用于在绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用斐波那契数列不仅仅只局限于兔子问题，在经济、科学、艺术、日常生活及优选法中具有广泛应用，黄金分割率的美感，更是一代代艺术家的不懈追求2.2 卢卡斯序列卢卡斯数是一个以数学家爱德华卢卡斯命名的整数序列，他既研究了这个数列，也研究了有密切关系的斐波那契数（两个数列都是卢卡斯数列）与斐波那契数一样，每一个卢卡斯数都定义为前两项之和，也就是说，它是一个斐波那契整数序列，两个相邻的卢卡斯数之比收敛于黄金分割比但是，最初两个卢卡斯数是 和，所以，卢卡斯数的性质与斐波那契数的性质有些不同卢卡斯序列的定义如下3 ，；， （2.2）3 三阶线性递归序列3.1 三阶线性递归序列的定义定义1 若满足的序列称为三阶复系数线性递归序列，有文4知，3阶复系数线性递归序列的特征矩阵或系数矩阵为.如果令，那么由第二数学归纳法可证得，因此可得，因而的特征方程为，即为对此可设，其中（复数），即设系数矩阵的特征根为以下我们分三种情况分别加以讨论 3.2 三阶线性递归序列特征值与通项表达式3.2.1 若序列特征根两两不同引理1 设系数矩阵，且的特征根两两不同，则存在三阶可逆方阵，使得其中证明：根据线性代数的知识可求得属于特征值的线性无关的特征向量分别为,因而由文 5引理1成立定理1 设序列且的特征根两两不同，则的通项表达式为6: （3.1）证明： 由引理1可知，则，因而而，代入即得定理1 3.2.2 若序列特征根两个相等不妨假设系数矩阵的特征根引理2 设系数矩阵，且的特征根，则存在三阶可逆方阵，使得，其中证明： 由知的初等因子为，因而存在三阶可逆方阵，使得，其中，则因而有，即，解此齐次线性方程组得，其中为任意常数特殊地取有，从而求得从，而引理2成立定理2 设序列，且的特征根,则的通项表达式为： （3.2）证明： 由，得而，代入可得定理2成立3.2.3 若序列特征根全相等 不妨假设系数矩阵的特征根.引理3 设系数矩阵，且的特征根为，则存在三阶可逆方阵，使得，其中证明： 同理由引理2的证明过程知，此时的初等因子为，因而存在可逆矩矩，使得，其中，则由解此线性方程组得，其中为任意复数不妨特殊地取，有，从而引理3成立 定理3 设序列且的特征根，则的通项表达式为： （3.3）其中证明: 由，得而代入即得定理3成立 推论1 ，证明： 容易证明对于，由以上的3 个引理可知：存在可逆矩阵，使得，且，其中为的若当标准形则可得即有，因而由的特征方程得，故推论1 成立 第 14 页4 三阶线性递推序列通项及前n项和计算公式4.1 三阶线性递推序列通项及前n项和定理4：设表示如下三阶线性递推关系序列7: (4.1) 则序列通项表达式为 (4.2)其中，其中，是序列的特征方程为互不相同的根，并设，是序列的初始值证明: 已知序列的特征方程为根为，和且两两互不相同，则通项为令，得方程组 (4.3) (4.4) (4.5)由(4.3)式得 (4.6)将(4.6)式代入(4.4)式得 (4.7) 将(4.6)式代入(4.5)式得 (4.8)将(4.7)式代入(4.8)式得 (4.9) 将(4.9)式代入(4.7)式得 (4.10)将(4.9)式、(4.10)式代入(4.6)得 (4.11)即得（4.2）式.在序列中给定一些特殊的不同初始值，可得到如下一些常见的3阶递推序列公式8: 命题1: ;序列的通项为：; (4.12); (4.13); (4.14)其中： ， ， (4.15)命题2: 序列通项可用，的线性组合表示: (4.16)证明: 由(4.12)-(4.14) 代入(4.16)右端 故(4.16)式成立4.2 一类特殊的3 阶线性递推序列在定理4中令序列有同系数线性递推序列为此时序列的特征方程为，且它的特征根很是复杂，由于序列通项用特征根表示显然困难，因此我们用发生函数的方法求序列通项与序列前项的和，这里规定符号表示的整数部分定理5设3 阶线性递推序列: ，并设初始值. (4.17) （1）序列通项表达式为： (4.18)（2）序列前项和表达式为： (4.19)证明: 设应用线性递推关系(4.17)计算可得到序列通项的中系数在，指数取为 ，并由组合序列恒等式所以于是便得到序列通项为：序列前项的和为中的系数，于是就得到 (4.19) 推论2:如果在序列(4.17)给定特殊的一些初始值，得到如下一些序列:（1）令称此三阶线性递推序列为三阶斐波那契序列序列通项为：, 序列前n 项的和为：. （2）令序列设为, 序列通项为：, 序列前n 项的和： . （3）令序列设为, 序列通项为：,序列前n 项的和：. （4）令序列设为, 序列通项为：, 序列前n 项的和：. （5）令序列设为, 序列通项为：, 序列前n 项的和为：. 第 21 页 5 三阶斐波那契数列5.1 三阶斐波那契数列和矩阵的定义定义1 若有数列，定义9 则称数列为三阶斐波那契数列，且称矩阵称为三阶斐波那契矩阵定理6 对于三阶斐波那契数列有： (5.1)证明：易得当 n = 3时，等式成立不妨假设当时，等式成立即 那么当时即得定理等式两边成立综上所述，对一切大于等于3的正整数，定理等式两边是恒成立的5.2 三阶斐波那契数列的通项表示的矩阵法及Cassini公式5.2.1 三阶斐波那契数列的通项表示的矩阵法由于系数矩阵的特征方程为，由一元三次方程的解法知它存在一个实根和二个共轭复根，不妨假设分别为，并设特征根对应的特征向量为，有高等代数的知识可知存在可逆矩阵，使得，则，而的第一行第一列元素即为，因而可将表示成其中，从而得到了以下推论推论3 设 是方程的三个根，并设，则存在可逆矩阵，使得三阶斐波那契数列的通项为10： . (5.2)5.2.2 三阶斐波那契数列的通项公式的Cassini公式事实上，定理6可看作是三阶斐波那契数列的矩阵式表示方法而且我们还可以将斐波那契数列的Cassini公式推广到了三阶，从而得到了三阶斐波那契数列的Cassini公式：定理7 对于三阶斐波那契数列，有 (5.3)证：由定理6知等式两边分别取行列式即得：化简即得.5.3 三阶斐波那契数列通项表示的行列式形式定理8 对于三阶斐波那契数列，有：等式右边是一个阶方阵我们运用第二数学归纳法来证明这个定理证明：当时，等式成立设当时，等式都成立则当时，将行列式则按最后一列展开可得：从而定理成立5.4 阶斐波那契数列及性质这里我们简要定义一下r阶斐波那契数列，并给出r阶斐波那契数列的通项公式以及前项和表达式定义：若一个数列满足递推公式11: (5.4)和初始条件 (5.5)我们称该数列(5.4)为r阶斐波那契数列，(5.4)中的每一项都称之为r阶斐波那契数简称阶数定理9r阶斐波那契数列(5.4)和满足初始条件(5.5)的通项公式为这里表示的整数部分定理10r阶斐波那契数列(5.4)前项和表达式为：.6 三阶线性递归序列的应用例1：假设共有三种票值分别为1元的、2元的和3元的邮票，且具有足够多的数量可供使用现今要贴出票面值为元的邮票，从左到右贴于一张信封上，记不同的排列为不同的方法，请问一共有多少种的贴法? 分析：记贴元票面值的方法共有种，那么为了求，我们考虑当第一张贴票面值为 1 元的邮票时，那么后面的方法共有 种贴法；如果第一张若贴票面值为 2元的邮票时，则后边的方法一共有种贴法；如果第一张若贴票面值为 3 元的邮票时，则后面的方法共有种贴法，于是有贴法，而且显然有，于是我们便得到了三阶斐波那契数列不妨我们作以下分析：假设为了贴出元票面值时，我们一共用3元票面值的邮票张，一共用2元票面值的邮票张，则1元票面值的邮票共需张，且， 这时一共需用邮票张，我们便从这个位置中选出个3 元邮票，再从剩余的个位置中选出个贴 2 元邮票，其余剩下的贴1元的，从而有不同的排列数为，于是我们就得到：，其中表示的整数部分例 2：现有一些白、黑、红三种颜色的小球（三色的球都足够多），要将它们放成一排，且必须满足如下的规定：每个白球的右边都至少有一个红球，每个黑球的右边都至少有一个白球，若一排有个位置，问有多少种不同的排法？分析：设共有种不同的排法若，则按要求只能放红球，所以只有一种排法，即；若，则按要求球的颜色只能是白红或红红，所以只有两种排法，即；若，则按要求球的颜色只能是白红红、黑白红、红白红或红红红，所以只有四种排法，即；若有个位置，则若第一个位置放红球，则以后的个位置只要按要求放即可，从而有种放法若第一个位置放白球，则后一个位置就必须放红球，而以后的个位置只要按要求放即可，从而有种放法若第一个位置放黑球，则以后的两个位置就必须放白球与红球，而再后面的个位置只要按要求放即可，从而有种放法综上所述且即排法数构成三阶斐波那契数列例3: 假如一个通讯员要将得到的电报传播出去，他决定发电报将这消息告诉其他的三个人，这三人接到电报后也立即再转告三人，依序每人分别将电报转告给另外三个，假定在这期间人员没有出现重复现象，且发通一电报需用一分钟时间，则 10 分钟后，共有多少人知道了这一电报？分析：根据题意，第一分钟中有 1 人的得到电报；第二分钟中有 2 人新得到电报；第三分钟有1+1+2=4 人新得到电报；第四分钟发布电报的人已通知了三人 ，他不再通知其它人 ，所以有1+2+4=7人新得到电报如此分析下去，第分钟中新得到电报的人数恰好是前三分钟得到电报的人数的总和，即它们恰好构成三阶斐波那契数列 ，从而10分钟后知道这一电报的人数就是总之，三阶斐波那契数列作为斐波那契数列的推广形式