|
|
[watermark]一些特殊数列
设X为一整数列，并满足X0＝a,X1＝b,其递推关系式为Xn+1＝g×Xn－Xn-1。本篇专门讨论的是初值X0＝0，X1＝1以及X0＝1，X1＝1时的两种情形下的X数列特征。
一、基础定义。
g为整数，P，S是两个函数，满足P(g,0)＝0, S(g,0)＝1；
n为正整数，P(g，n),S(g，n)｛以下简称Pn、Sn，即P,S是两个数列｝满足： Sn＝(g－2)×Pn-1＋Sn-1和 Pn＝Sn＋Pn-1。
可计算出S1＝1,P1＝1,{这两个值与g无关。} S2＝g－1，P2＝g。
很容易证明：Pn＝(g－1)×Pn＋Sn ，Pn＝S1＋S2＋S3＋…＋Sn-1＋Sn。
下面用数学归纳法证明： Sn+1＝g×Sn－Sn-1 ，Pn+1＝g×Pn－Pn-1。 (Ⅰ)
显然当n＝1时，而由Ⅰ式可同样得出S2＝g－1,P2＝g；
假设对于n＝1…i时，Ⅰ式都成立，即g×Pi－Pi-1－Pi+1＝0，Si+1－g×Si＋Si-1＝0；
则当n＝i+1时，由S，P的递推关系式，可知
Si+2＝(g－2)×Pi+1＋Si+1
＝(g－2)×(Si+1+Pi)＋Si+1
＝g×Si+1－2×Pi＋g×Pi－Si+1
＝g×Si+1－Pi＋g×Pi－(Pi＋Si+1)
＝g×Si+1－(Si＋Pi-1)＋g×Pi－Pi+1
＝g×Si+1－Si＋g×Pi－Pi-1－Pi+1
＝g×Si+1－Si (Ⅱ)
Pi+2＝Si+2＋Pi+1＝g×Si+1－Si＋g×Pi－Pi-1 {代入Ⅱ式}
＝g×(Si+1＋Pi)－(Si＋Pi-1)
＝g×Pi+1－Pi
证毕。
可见S 、P正好是符合前述X特征的数列，可计算出Sn,Pn的通项公式。当|g|≥2时，极限Lim[n→∞] (Xn+1／Xn)存在，可计算出：
Lim[n→∞] (Xn+1／Xn)＝（g＋√(g^2－4) ）／2。
二、基础等式。本篇假定1≤n≤m,k≥0。
基础等式§1（核心等式）
Pn+k+1×Sn+1－Sn+k+1×Pn+1
＝((g－1)×Pn+k＋Sn+k)×((g－2)×Pn＋Sn) ｛根据定义替代，并展开化简｝
－((g－2)×Pn+k＋Sn+k)×((g－1)×Pn＋Sn)
＝(g－2)×(g－1)×Pn+k×Pn＋(g－1)×Pn+k×Sn＋(g－2)×Sn+k×Pn＋Sn+k×Sn
－(g－2)×(g－1)×Pn+k×Pn－(g－2)×Pn+k×Sn－(g－1)×Sn+k×Pn－Sn+k×Sn
＝Pn+k×Sn－Sn+k×Pn
因此 Pn+k+1×Sn+1－Sn+k+1×Pn+1＝Pn+k×Sn－Sn+k×Pn
由上式结果对标号n进行递推得到：{也可变换成数学归纳法的形式}
Pn+k×Sn－Sn+k×Pn＝Pk×S0－Sk×P0＝Pk；
此式可通过标号替代变换成另一形式：Pm×Sn＝Sm×Pn＋Pm-n。
基础等式§2
Pm×Pn－Pm+1×Pn-1
＝(Pm+1－Sm+1)×Pn－Pm+1×(Pn－Sn)
＝Pm+1×Pn－Sm+1×Pn－Pm+1×Pn＋Pm+1×Sn
＝Pm+1×Sn－Sm+1×Pn＝Pm-n+1 ｛根据等式§1｝
即Pm×Pn＝Pm+1×Pn-1＋Pm-n+1；
此式可变换成Pn+k×Pn＝Pn+k+1×Pn-1＋Pk+1。当k＝0时，即Pn^2＝Pn+1×Pn-1＋1；当n≥2，|g|≥2时，可将其变换成Pn+1＝(Pn^2－1)／Pn-1，作为P数列的另一递推关系式。
基础等式§3
Sm×Sn－Sm+1×Sn-1
＝Sm×((g－2)×Pn-1＋Sn-1)－((g－2)×Pm＋Sm)×Sn-1 ｛根据定义替代｝
＝(g－2)×Sm×Pn-1＋Sm×Sn-1－(g－2)×Pm×Sn-1－Sm×Sn-1｛展开化简｝
＝－(g－2)×(Pm×Sn-1－Sm×Pn-1)
＝－(g－2)×Pm-n+1 ｛根据等式§1｝
即Sm×Sn＝Sm+1×Sn-1－(g－2)×Pm-n+1；
此式可变换成Sn+k×Sn＝Sn+k+1×Sn-1－(g－2)×Pk+1。
当k＝0时，即Sn^2＝Sn+1×Sn-1－(g－2)；当|g|≥2时，可将其变换成Sn+1＝(Sn^2＋(g－2))／Sn-1，作为S数列的另一递推关系式。
基础等式§4
Sm×Pn－Sm+1×Pn-1
＝Pm×Sn－Pm-n－Sm+1×Pn-1 ｛根据等式§1替代｝
＝Pm×((g－2)Pn-1＋Sn-1)－((g－2)×Pm＋Sm)×Pn-1－Pm-n ｛根据定义替代｝
＝(g－2)×Pm×Pn-1＋Pm×Sn-1－(g－2)×Pm×Pn-1－Sm×Pn-1－Pm-n｛展开消元｝
＝Pm×Sn-1－Sm×Pn-1－Pm-n ｛根据等式§1｝
＝Pm-n+1－Pm-n
即Sm×Pn＝Sm+1×Pn-1＋Pm-n+1－Pm-n；
此式可变换成Sn+k×Pn＝Sn+k+1×Pn-1＋Pk+1－Pk。
二、导出等式。
等式§5{基础等式§2的扩展}
Pm×Pn＝Pm+1×Pn-1＋Pm-n+1
Pm+1×Pn-1＝Pm+2×Pn-2＋Pm-n+3
Pm+2×Pn-2＝Pm+3×Pn-3＋Pm-n+5
……
Pm+n-2×Pn-n+2＝Pm+n-1×Pn-n+1＋Pm-n+2n-3
Pm+n-1×Pn-n+1＝Pm+n×Pn-n＋Pm-n+2n-1
上述各式左右迭加，再化减得：Pm×Pn＝Pm-n+1＋Pm-n+3＋Pm-n+5…＋Pm+n-1；
当m＝n时，即有Pn^2＝P1＋P3＋P5…＋P2n-1；
此式可变换成：Pm+n×Pn＝Pm+1＋Pm+3＋Pm+5…＋Pm+2n-1。
等式§6 ｛基础等式§3的扩展｝
Sm×Sn＝Sm+1×Sn-1－(g－2)×Pm-n+1
Sm+1×Sn-1＝Sm+2×Sn-2－(g－2)×Pm-n+3
Sm+2×Sn-2＝Sm+3×Sn-3－(g－2)×Pm-n+5
……
Sm+n-2×Sn-n+2＝Sm+n-1×Sn-n+1＋Pm-n+2n-3
Sm+n-1×Sn-n+1＝Sm+n×Sn-n－(g－2)×Pm-n+2n-1
上述各式左右迭加，再化减得：Sm×Sn＝Sm+n－(g－2)×(Pm-n+1＋Pm-n+3＋Pm-n+5…＋Pm+n-1) ＝Sm+n－(g－2)×Pm×Pn；
当m＝n时，有S2n＝ (g－2)×Pn^2＋Sn^2,将S2n＝(g－2)×P2n-1＋S2n-1代入，又可得S2n-1＝Sn^2＋(g－2)×Pn-1^2。利用上述等式，很容易证明：
S2n－S2n-1＋S2n-2－S2n-3…S4－S3＋S2－S1＝(g－2)×Pn^2； S2n-1－S2n-2＋S2n-3－S…―S4＋S3－S2＋S1＝Sn^2。
等式§7 {基础等式§4的扩展}
Sm×Pn＝Sm+1×Pn-1＋Pm-n+1－Pm-n
Sm+1×Pn-1＝Sm+2×Pn-2＋Pm-n+3－Pm-n+2
Sm+2×Pn-2＝Sm+3×Pn-3＋Pm-n+5－Pm-n+4
……
Sm+n-2×Pn-n+2＝Sm+n-1×Pn-n+1＋Pm-n+2n-3－Pm-n+2n-4
Sm+n-1×Pn-n+1＝Sm+n×Pn-n＋Pm-n+2n-1－Pm-n+2n-2
上述各式左右迭加，再化减得：
Sm×Pn＝Pm+n-1－Pm+n-2＋Pm+n-3－Pm+n-4…＋Pm-n+5－Pm-n+4＋Pm-n+3－Pm-n+2＋Pm-n+1－Pm-n；
当m＝n时，有Pn×Sn＝P2n-1－P2n-2…＋P5－P4＋P3－P2＋P1；
当m=n+1时，有Pn×Sn+1＝P2n－P2n-1…＋P4－P3＋P2－P1。
等式§8
Sn+1^2－(g－2)×Pn+1×Pn－(Sn^2－(g－2)×Pn×Pn-1)
＝Sn+1^2－Sn^2－(g－2)×Pn×(Pn+1－Pn-1)
＝(Sn+1－Sn)×(Sn+1＋Sn)－(g－2)×Pn×((g－1)×Pn＋Sn－(Pn－Sn))
＝(g－2)×Pn×((g－2)×Pn＋2×Sn)－(g－2)×Pn×((g－2)×Pn＋2×Sn)
＝0
因此Sn+1^2－(g－2)×Pn+1×Pn＝Sn^2－(g－2)×Pn×Pn-1；
由上式结果对n进行递推得到：
Sn^2－(g－2)×Pn×Pn-1＝S1^2－(g－2)×P1×P0＝1^2－(g－2)×1×0＝1。
等式9：|g|≥2，Pnm＝0Mod(Pm)。
根据等式§8，有Sm^2＝(g－2)×Pm×Pm-1＋1，因此Sm ，Pm互质。
用数学归纳法证明：Pnm＝0Mod(Pm)。
显然n＝1时，等式是成立的。
假设对于n＝1…i时，Pnm＝0Mod(Pm)都成立, 令Pim＝t×Pm，
则当n＝i+1时，
由等式§1可知：P[i+1]m×Sm－S[i+1]m×Pm＝Pm
=> [i+1]m×Sm＝S[i+1]m×Pm＋Pim
=>[i+1]m×Sm＝(S[i+1]m＋t)×Pm
因Sm与Pm互质，故Sm不含Pm的任何因子，由此Pm 必可整除P[i+1]m，
即P[i+1]m＝0Mod(Pm)。
证毕。
等式10：|g|≥2，若a为一整数，并且Pm、Pn＝0Mod(a)，t为m、n的最大公约数，
则 Pt＝0Mod(a)。
构造一个过程证明如下：
令x＝m，y＝n，则
① 由基础等式1可得： Px×Sy－Sx×Py＝Px-y。
显然，因Px、Py＝0Mod(a)，故Px-y＝0Mod(a)，令t＝x-y；
若t＝y，则t为n、m-n的最大公约数，并且满足Pt＝0Mod(a)，等式得证；
否则，令x＝Max (x-y，y)，y＝Min(x-y，y)，再转到 ①
因t，x，y均为正整数，故上述构造过程步骤是有限的，一定可以找到满足条件的t。
证毕。
等式11：|g|≥2,对于任何大于2的质数a，都存有某个正整数v≤a，使得Pvn＝0Mod(a×Pn)。
把所有整数对于a的不为0的模余分为(a－1)/2模余组：
(1,a－1)，(2,a－2)，(3,a－3)，…((a－3)/2 ，(a＋3)/2) ，((a－1)/2 ，(a＋1)/2)，
取Pn ，P2n,P3n…P[(a+1)/2，P[(a+3)/2]n等(a＋1)/2个P数列单元。
根据等式9可知，(Pn／Pn＝1,P2n／Pn，P3n／Pn…，Pin／Pn，…P[(a+1)/2]n／Pn)均为整数，在此(a+1)/2个整数对a的模余中：
一、若其中有某个i，使得Pin／Pn＝0Mod(a)，显然i≠1，则令v=i，显然v≤a，并有Pvn＝0Mod(a×Pn)，等式得证；
二、否则，即此(a+1)/2个整数对a的模余均不为0；
在(1，P2n／Pn，P3n／Pn，…，P[(a+1)/2]n／Pn) 等(a+1)/2个整数对a的模余数中，其个数比a的模余组数(a－1)/2多一个，因此必有两个j ，i，使得：Pjn／Pn，Pin／Pn对a的模余在同一个组中。
不妨设j＞i，这样就有Pjn／Pn－Pin／Pn＝0Mod(a)或Pjn／Pn＋Pin／Pn＝0Mod(a)，亦即(Pjn／Pn－Pin／Pn)×(Pjn／Pn＋Pin／Pn) ＝0Mod(a)
根据等式4有：
Pjn^2－Pin^2＝P[j+i]n×P[j-i]n
=>(Pjn／Pn－Pin／Pn)×(Pjn／Pn＋Pin／Pn)＝P[j+i]n／Pn×P[j-i]n／Pn
从而P[j+i]n／Pn×P[j-i]n／Pn＝0Mod(a)，由于a是质数，因此
若P[j-i]n／Pn＝0Mod(a)，与此(a+1)/2个整数对a的模余均不为0的题设矛盾；
故必有P[j+i]n／Pn＝0Mod(a)，令v=j＋i，显然也有v≤a，并且Pvn＝0Mod(a×Pn)，证毕。
等式12：|g|≥2,Tn为一数列，T0＝0，对于所有标号n,Tn＝Pnm／Pm，
令h＝P2m／Pm ,则Tn＝P（h，n）。
由定义可知， P(h，0)＝0，P(h，1)＝1, 并可以计算出P(h，2)＝h＝P2m／Pm,并由等式3可知：P(h，n+1) ＝(P(h，n) ^2－1)／P(h，n-1)。
同样：T0＝0，T1＝P1m／Pm＝1，T2＝P2m／Pm；
由等式4可知：Pnm^2－Pm^2 ＝P[n-1]m×P[n+1]m
=> (Pnm／Pm) ^2－1 ＝P[n+1]m／Pm×P[n-1]m／Pm
=> P[n+1]m／Pm×(P[n-1]m／Pm)＝(Pnm／Pm) ^2－1
=>Tn+1＝(Tn ^2－1)／Tn-1；
数列P（h）和数列T有同样的初始值和递推关系式，很明显Tn＝P(h，n)。
由此等式可定义整数列H(g)：|g|≥2，对于所有的标号m,均有：Hm＝P2m／Pm，并且对于所有的标号n,P(Hm,n)＝Pnm/ (Pm)。｛注：当g＝3时，令Cn＝Hn－2，则C为Chebyshev数列。｝
三、其他特征描述。
P(0)、S(0)数列是周期为4的循环数列, P(1)、S(1)数列是周期为6的循环数列, P(-1)、S(-1)数列是周期为3的循环数列。
并且满足：S(g，n)－S(0，n)＝0Mod(g)，P(g，n)－P(0,n)＝0Mod(g)；g为正整数时，P(g, n)－P(-1，n)＝0Mod(g＋1), S(g，n)－S(-1，n)＝0Mod(g＋1)；g为负整数时,
S(g，n)－S(1，n)＝0Mod(g－1),P(g，n)－P(1，n)＝0Mod(g－1)。
|g|≥2时，由等式9，10可知，m、n互质，是P(g，m)与P(g，n)互质的充分必要条件；再由等式11可推导出，a为整数并且|a|≥2，都存有某个n≤a,使得a可整除P(g，n)，这可通过将a转换成一系列质数的乘积后，再通过等式11对P(g，n)的反复寻找过程得出此结论。
当g＝2时，则Sn为等于1的常数列，Pn为自然数列。上述有关P数列的等式可很简单的通过直接代入其标号来验证。
当g＝－2时，则Sn为正负交错的奇数列，Pn为正负交错的自然数列。
当g＝3时，令F2n-1=Sn,F2n＝Pn,则Fn为Fibonacci数列。
当g＝6时，存在一个数列An,使得Sn^2＝An^2＋(An＋1)^2。
[/watermark] |
|
IP卡
狗仔卡
发表于 2006-4-22 13:14
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡