递归数列通项与不动点原理

第 29 卷第 3 期 喀什师范学院学报 Vol. 29 No. 3 2008 年 5 月 Journal of Kashgar T eachers College May 2008 递归数列通项与不动点原理� 邓 � 勇 (喀什师范学院 数学系,新疆 喀什 844007) 摘 � 要:运用线性空间的不动点原理, 研究了几类递归数列通项问题, 获得了求三类递归数列通项公式的一种新 方法. 关键词:递归数列; 连续函数;不动点定理; 通项公式 中图分类号: O151. 2 � � 文献标识码: A � � 文章编号: 1006-432X( 2008) 03-0023-03 1 � 问题的提出 定义[ 1] � 方程 f ( x ) = 0 的根称为函数 f ( x ) 的不动 点. 设 f : I� R,其中 I 是 R的一个区间, 数列{ an}由 x 1 � I 和递归关系 an= f ( an- 1 ) n� 2) 所确定. 若 f 是连续的且 { an }收敛于 r , 即 r = lim n � � an = limn � � f ( an- 1) = f ( limn � � an- 1 ) = f ( r ) , [ 4] 因此,求数列{ an }收敛点的问题就转化为求方程 f ( x )= x 的不动点了. 数列{ an }可以看作是定义在自然数集合上的函数 an = f ( n ) [ 2] .因此, 可利用递归数列 f ( n)的不动点将某些递 推关系所确定的数列化为等比数列或降为阶数较低的递归 数列. 这种求递归数列通项公式的方法称为不动点方 法. [ 3] 2 � 线性递归数列 2. 1 � 一阶线性递归数列 设一阶线性递归数列由递归方程 an = pan- 1 + q ( p � 0) 给出. 当 q= 0 时 an = pan- 1 ( n � 2) , ( 1) 设 f ( x ) = px , 则( 1)由递归关系 an = f ( an- 1 )给出. 当给 定初始值 a1时, (1)等价于一个首项为 a1 ,公比为 p 的等 比数列{ an| an= a1p n- 1 } . 当 q � 0 时, an = pan- 1 + q ( n � 2) , ( 2) 设 f ( x )= ( p - 1) x+ q ,则( 2)由递归关系 an= f ( an - 1)给 出.只需把( 2)转化为(1)的情形即可. 为此, 令 an= b n+ � ( �为待定常数) ,并将它代入( 2) 得 bn + �= p ( bn- 1+ �) + q , bn = pbn- 1+ ( p�- �+ q ) . � � 为要{ bn }满足( 1) , 只要 p�- �+ q= 0, 即 �= q1- p . 这说明 �是函数 f ( x )= ( p - 1) x + q 的不动点. [ 5]于是有 下面的 定理 1 � 若 �是 f ( x ) = ( p - 1) x + q ( p � 0, 1)的不 动点,则一阶非齐次线性递归数列(2)等价于齐次线性递归 数列 an - �= p ( an- 1- �) . (3) � � 由定理 1 可得(2)所确定的非齐次线性递归数列的通 项公式 an= �+ ( a1- �) p n - 1 ( n�2) . 例 1 � 已知 a1= 1, an= 12 an - 1+ 1,求 an . 解 � 设 f ( x ) = 1 2 x + 1, 则方程的不动点为 �= 2. 又 已知 a1= 1, p = 12 ,所以 an = 2+ ( 1- 2) ( 1 2 ) n- 1 = 2 - ( 1 2 ) n- 1 � = 2 - 1 2n- 1 . 2. 2� 二阶线性递归数列 设二阶线性递归数列由递归方程 an = pan- 1+ qan- 2+ r ( n � 3) (4) 给出.为求( 5)所确定数列的通项, 我们希望用一阶线性递 归数列的相应结果. 为此令 bn = an - �an- 1 ( �为待定常 数) , 并将它代入(4)得 bn = ( p - �) an- 1 + qan- 2 + r � = ( p - �) [ an- 1+ qp - �an- 2 ] + r . � � 为要{ bn }成为( 2)的形式, 即 bn= ( p - �) b n- 1+ r , 只 �收稿日期: 2007-10-25 作者简介:邓 � 勇( 1967- ) ,男 ,四川遂宁人, 副教授,主要从事基础数学教学研究. 要 q p - �= - �, 于是 �必须满足方程�2- p�- q= 0. 若令 f ( x ) = x 2- px - q, 则 �为函数 f ( x )的不动点[ 5] . 于是有 下面的 定理 2� 若 �是 f ( x ) = x 2- px- q 的不动点,则二阶 非齐次线性递归数列(4)等价于一阶非齐次线性递归数列 a n- �a n- 1 = ( p - �) ( an- 1- �a n- 2 ) + r ( n � 3) . ( 5) � � 根据定理 2, 一般地, 可将 k 阶线性递归数列 an+ k= p 1an+ k - 1+ p 2an+ k- 2+ �+ p kan 降为 k- 1 阶线性递归数 列. 特别地,当( 4)中的 r= 0 时, ( 4)所对应的齐次线性递 归数列为 an = pan- 1 + qan- 2 ( n � 3) . ( 6) � � 下面我们分两种情况讨论(6)的通项公式: (1) 当 x 2- px - q= 0 有两个不相等的根 �1 , �2 时, 由定理 2, (6)等价于 an - �1 an- 1 = ( p - �1 ) ( an- 1 - �1an- 2) 或 an - �1 an- 1 = �2( an- 1- �1an- 2 ) , 递推之得 an - �1an- 1 = �n- 22 ( a2 - �1 a1) ; ( 7) 同理 an - �2an- 1 = �n- 21 ( a2 - �2 a1) . ( 8) � � 由(7) (8)两式解得 an = a2 �n- 11 - �n- 12�1 - �2 + qa1 �n- 21 - �n- 22�1- �2 . ( 9) � � (2) 当 x 2- px - q= 0 有两个相等的根 �1= �2 时, 把 ( 9)式改写为 an= a2 ( �n- 21 + �n- 31 �2 + �+ �1�n- 32 + �n - 22 ) + qa1 ( �n- 31 + �n- 41 �2+ �+ �1�n- 42 + �n- 32 ) . 令 �1= �2= �, 则 an = a2( n - 1) �n- 2 + qa1( n - 2) �n- 3. (10) � � 例 2 � 已知 a1= 2, a2= 1, an= 5 an - 1- 6 an - 2+ 1, 求 an . 解 � 设 f ( x )= x 2- 5x + 6, 则它的两个根为 �1= 2,�2 = 3. 由定理 2, 原递归数列等价于 an- 2an- 1= (5- 2) ( an - 1- 2an- 2 )+ 1 � � � = 3( an- 1- 2an- 2 )+ 1. 令 bn= an- 2an- 1 ,则有 bn= 3 bn- 1+ 1, b 2= - 3. 所以 b n= - 1 2 (1+ 5�3n- 2 ) , 从而 an = 2an- 1 - 1 2 ( 1 + 5� 3n- 2) , 即 an+ 1 = 2an - 1 2 ( 1 + 5� 3n- 1) . 所以 an = 2 n- 1� 2 + 2n �n- 1 k= 1 g( k ) 2k+ 1 , 其中 g ( k )= - 1 2 (1+ 5�3k- 1) . 最后解得: an= 12 + 1 2 �3n - 1+ 2n + 1- 3n . 例 3 � 求 Fibonacci数列 F 1= F2= 1, Fn= Fn- 1+ Fn - 2 ( n �3)的通项公式 F n 解 � 由于 F ibonacci数列是二阶齐次线性递归数列, 所 以由(9)得 F n = �n- 11 - �n- 12�1 - �2 + �n- 21 - �n- 22�1 - �2 , 其中 �1 , �2是方程 x 2- x- 1= 0 的两个根,即 �1= 1+ 52 , �2= 1- 52 . 而 1+ �1= �21, 1+ �2= �22, 于是 Fn = �n1- �n2�1- �2 , 故 Fn = 1 5 ( 1 + 5 2 ) n - ( 1- 5 2 ) n . 3 � 分式线性递归数列 由递归方程 x n = ax n- 1 + b cx n- 1+ d ( ad � bc, c � 0, n � 2) ( 11) 所确定的数列称为分式线性递归数列. 为求(11)所确定的分式线性递归数列的通项,我们只 需将(11)化为线性递归方程即可,为此我们有 定理 3 � 若 �1 , �2是 f ( x )= ax+ bcx + d 的两个不动点, 则 (1) 当 �1� �2 时, ( 11)等价于 x n - �1 x n - �2 = K x n- 1- �1 x n- 1 - �2 ( K = a - c�1 a - c�2 ) ; ( 12) � � (2) 当 �1= �2= �时, (11)等价于 1 x n - �= 1 x n- 1- �+ K (K = 2c a + d ) . ( 13) � � 证明 � (1) 因为 �1, �2 是 f ( x ) = ax+ bcx + d 的不动点, 即 方程 x= ax+ b cx + d 或 cx 2+ ( d - a) x - b= 0 有两个相异的根 �1 , �2. 于是 x n- �1 x n- �2= ax n- 1+ b cx n- 1+ d - �1 ax n- 1+ b cx n- 1+ d - �2 � � � = ( a- �1c) x n- 1+ b- �1d ( a- �2c) x n- 1+ b- �2d � � � = a- �1c a- �2c � x n- 1+ b- �1d a- �1c x n- 1+ b- �2d a- �2c , 因为 �1 , �2 是方程的根,所以 c�21+ ( d - a) �1= b , c�22+ ( d - a)�2= b ,于是 b - �1d a - �1c = �1( c�1 - a) a - �1c = - �1 , b - �2d a - �2c = �2( c�2 - a) a - �2c = - �2 , 从而 x n- �1 x n- �2 = a - �1 c a - �2 c � x n- 1 - �1 x n- 1 - �2 = K � x n- 1- �1 x n- 1- �2 . �24� � � � 喀什师范学院学报 第 29 卷 � � 反之, 由上式可解出 x n= ax n- 1+ bcx n- 1+ d . 因此 (11)与( 12) 等价. (2) 设 �是方程 cx 2+ ( d - a) x - b= 0 的二重根, 则 �= ( d- a) 2+ 4 bc= 0, �= a- d 2c .因为 x n- �= ax n- 1 + bcx n- 1+ d - �= a- �c c � x n- 1+ b - �d a- �c x n- 1 + d c , 又 b- �d a- �c = - �,故 x n- �= a- �cc � x n- 1- � x n - 1+ d/ c , 于是 1 x n- �= c a- �c� x n - 1- �+ ( dc + �) x n- 1- � � � = c a- �c� 1+ d / c+ � x n - 1- � � � = d+ c� a- c�� 1x n - 1- �+ c a- c�. 由于 �= a- d 2c , 所以d + c� a- c�= 1, ca- c�= 2ca+ d , 则 1x n- �= 1 x n- 1- �+ K ( K = 2c a+ d ) . 反之,由上式可以解得 x n = ax n- 1+ bcx n- 1+ d . 因此 ( 11) 与 ( 13)等价. 例 4� 已知 x 1= 5, x n= 3x n- 1+ 12x n- 1+ 2,求 x n . 解 � 因为方程 2 x 2 - 3 x - 1= 0 的不动点为 �1= - 1 2 , �2= 1,所以有 xn + 1 2 xn - 1 = 3- 2� (- 1 2 ) 3- 2� 1 n- 1 5- (- 1 2 ) 5- 1 � � � � = 4n- 1 � 11 4� 2 = 11� 22 n- 5, 解得 x n= 11�22 n- 5+ 1 2 11�22 n- 5- 1 = 11�22 n- 4+ 1 11�22 n- 4- 2. 4 � 二元线性递推数列 设两个数列{ x n } , { yn }满足 x 1 = �, y 1 = �, x n+ 1 = �x n + by n y n+ 1 = cx n+ dyn ( ad � bc) ( 14) 则由(14)式所确定的数列{ x n } , { y n }称为二元线性一阶递 推数列. 若 b= c= 0,则( 14)式成为转化为一阶线性递归数列 的情形; 若 b , c 均不为零, 由递推方程(14)可得 x n+ 1 yn+ 1 = ax n+ by n cx n + dy n = a x n y n + b c x n y n + d , 令 z n= x ny n ,则有 z n+ 1= az n+ b cz n+ d .于是问题转化为分式线性 递归数列的情形[ 5] . 所以,不论是上述哪种情况, (14)所确定数列的通项公 式都可获得. 5 � 结 � 语 本文给出的求递归数列通项公式的不动点方法并非是 一种简单、便捷的方法,但它却为我们提供了一种寻求递归 数列通项的全新思路, 这就是数列的函数观点.虽然本文只 例举了三类递归数列, 但我们今后可依据这种思想方法去 探究其他更多的递归数列. 参考文献: [ 1] Kenneth H Rosen. Elementary Number Theor y [ M ] . Ad- dison Wesley / Pearson, 2005. [ 2] 余元希, 田万海,毛宏德 .初等代数研究( 下册 数学七年级下册拔高题下载二年级下册除法运算下载七年级下册数学试卷免费下载二年级下册语文生字表部编三年级下册语文教材分析 ) [ M ] . 北 京: 高等教育出版社, 1988. [ 3] 王娟, 董树权.关于不动点的几个命题[ J] . 长春师范学 院学报, 2002, ( 2) : 12-14. [ 4] 冯艳青. 数学 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 中的不动点问题 [ J] . 青海师范大学 学报(自然科学版) , 2001, ( 4) : 16-17. [ 5] 邓勇. 常系数非齐次线性递归数列通项公式计算的通 项变换法[ J] .喀什师范学院学报, 2005, ( 3) : 28-30. General Term Formula of Recurrence Sequence and Fixed Point Theorem DENG Yong ( Depar tment of Mathematics, Kashgar Teachers College, Kashgar 844007, Xinjiang, China) Abstract: This paper does the research on the types of recurrence sequence general quest ion by fixed point the- ory on linear space, and a new method of three kinds of recurrence sequences for general term formula w as ob- tained. Key words: Recurrence sequence; Cont inuous funct ion; Fixed point theorem ; General term formula �25�第 3 期 邓 � 勇:递归数列通项与不动点原理 � �