主题
Search

线性递推方程

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

线性递推方程是关于数字序列 {x_n} 的递推方程，它将 x_n 表示为 x_k 的一次多项式，其中 k<n。例如

x_n=Ax_(n-1)+Bx_(n-2)+Cx_(n-3)+....
(1)

商差表 最终产生一行 0，当且仅当起始序列由线性递推方程定义时。

Wolfram 语言 命令LinearRecurrence[ker, init, n] 给出通过迭代线性递推得到的长度为 n 的序列，其中内核为 ker，初始值为 init，例如内核 {c_1,c_2} 表示递推关系 a_n=c_1a_(n-1)+c_2a_(n-2)，初始值为 {a_1,a_2,...}。FindLinearRecurrence[list] 尝试找到生成列表的最小线性递推式。RecurrenceTable[eqns, expr, {n, nmax}] 基于求解指定的递推方程生成 expr 的连续 n 值列表。

下表总结了一些常见的线性递推方程和相应的解。

递推式初始条件解
a_n=a_(n-1)+a_(n-2)a_1=a_2=1斐波那契数 F_n
a_n=a_(n-1)+a_(n-2)a_1=1, a_2=3卢卡斯数 L_n
a_n=a_(n-2)+a_(n-3)a_0=a_1=a_2=1帕多瓦序列 P_n
a_n=2a_(n-1)+a_(n-2)a_0=0, a_1=1佩尔数 P_n
a_n=2a_(n-1)+a_(n-2)a_0=a_1=2佩尔-卢卡斯数 Q_n
a_n=a_(n-2)+a_(n-3)a_0=3, a_1=0, a_2=2佩兰序列 P_n

一般的二阶线性递推方程

x_n=Ax_(n-1)+Bx_(n-2)
(2)

对于常数 A 和 B，以及任意的 x_1 和 x_2，其项为

x_1=x_1
(3)
x_2=x_2
(4)
x_3=Bx_1+Ax_2
(5)
x_4=Bx_2+ABx_1+A^2x_2
(6)
x_5=B^2x_1+2ABx_2+A^2Bx_1+A^3x_2
(7)
x_6=B^2x_2+2AB^2x_1+3A^2Bx_2+A^3Bx_1+A^4x_2
(8)
x_7=B^3x_1+4A^3Bx_2+3A^2B^2x_1+3AB^2x_2+A^4Bx_1+A^5x_2.
(9)

因此，任意项可以写成

x_n=sum_(k=0)^(n-2)(|_1/2(n+k-2)_|; k)A^kB^(|_(n-k-1)/2_|)x_1^([n+k (mod 2)])x_2^([n+k+1 (mod 2)])
(10)
=-(Ax_1-x_2)sum_(k=0)^(n-2)A^(2k-n+2)B^(-k+n-2)(k; n-k-2)+x_1sum_(k=0)^(n-1)A^(2k-n+1)B^(-k+n-1)(k; n-k-1).
(11)

如果 x_1=x_2=1，则 x_n 的闭合形式由下式给出

x_n=(alpha^nbeta(1-beta)-beta^nalpha(1-alpha))/(alphabeta(alpha-beta)),
(12)

其中 alpha 和 beta 是二次方程 的根

x^2-Ax-B=0,
(13)
alpha=1/2(A+sqrt(A^2+4B))
(14)
beta=1/2(A-sqrt(A^2+4B)).
(15)

如果改为 x_1=1 和 x_2=A，则解变为

x_n=(alpha^n-beta^n)/(alpha-beta).
(16)

例如，斐波那契数 F_n，对于 n=1, 2, ... 等于 1, 1, 2, 3, 5, 8, ...，有 A=B=1，所以 alpha=(1+sqrt(5))/2 和 beta=(1-sqrt(5))/2，给出

F_n=([1/2(1+sqrt(5))]^n-[1/2(1-sqrt(5))]^n)/(sqrt(5))
(17)
=((1+sqrt(5))^n-(1-sqrt(5))^n)/(2^nsqrt(5)).
(18)

Grosjean (1993) 讨论了如何将这种“根的幂之差”解改写为显式整数形式。

广义斐波那契数的递推式为

f_n=f_(n-1)+f_(n-2)
(19)

其中 f_1=a 和 f_2=b，其解由下式给出

f_n=1/2[(3a-b)F_n+(b-a)L_n],
(20)

其中 F_n 是斐波那契数，L_n 是卢卡斯数。

任何满足二项递推方程 b(n) 的序列 b(n) 可以写成

b(n)=b(n-1)-b(n-2)
(21)

可以写成

b(n)=b(0)a(n)+[b(1)-b(0)]a(n-1),
(22)

其中

a(n)=U_n(1/2)
(23)
=2/3sqrt(3)sin(1/3(n+1)pi)
(24)

是 麦克劳林级数 1/Phi_6(x) 中的系数序列，其中 Phi_6(x) 是分圆多项式 (OEIS A010892)，U_n(z) 是第二类切比雪夫多项式。

线性二阶递推

f_(n+1)=xf_n+yf_(n-1)
(25)

可以使用“速率加倍”快速求解，

f_(n+2)=(x^2+2y)f_n-y^2f_(n-2),
(26)

“速率三倍”

f_(n+3)=(x^3+3xy)f_n+y^3f_(n-3),
(27)

或者，更一般地，“速率 k 倍”公式

f_(n+k)=p_kf_n+q_kf_(n-k),
(28)

其中

p_0=2
(29)
p_1=x
(30)
p_k=2(-y)^(k/2)T_k(x/(2isqrt(y)))
(31)
p_(k+1)=xp_k+yp_(k-1)
(32)

（此处，T_k(x) 是第一类切比雪夫多项式）和

q_0=-1
(33)
q_1=y
(34)
q_k=-(-y)^k
(35)
q_(k+1)=-yq_k
(36)

(Gosper 和 Salamin 1972)。

一般的线性三阶递推方程

x_n=Ax_(n-1)+Bx_(n-2)+Cx_(n-3)
(37)

有解

x_n=x_1((alpha^(-n))/(A+2alphaB+3alpha^2C)+(beta^(-n))/(A+2betaB+3beta^2C)+(gamma^(-n))/(A+2gammaB+3gamma^2C)) -(Ax_1-x_2)((alpha^(1-n))/(A+2alphaB+3alpha^2C)+(beta^(1-n))/(A+2betaB+3beta^2B)+(gamma^(1-n))/(A+2gammaC+3gamma^2C)) -(Bx_1+Ax_2-x_3)((alpha^(2-n))/(A+2alphaB+3alpha^2C)+(beta^(2-n))/(A+2betaB+3beta^2C)+(gamma^(2-n))/(A+2gammaB+3gamma^2C)),
(38)

其中 alpha、beta 和 gamma 是多项式

Cx^3+Bx^2+Ax=1.
(39)

对于函数的有限线性递推序列

s_i(x)=A_i(x)s_(i+1)(x)+B_i(x),
(40)

其中 i=1, ..., r-1，并且 s_r(x)=h(x)，则

s_1(x)=|B_1(x) -A_1(x) 0 ... 0; B_2(x) 1 -A_2(x) ... 0; B_3(x) 0 1 ... |; | | ... ... 0; B_(r-1)(x) 0 0 ... -A_(r-1)(x); h(x) 0 0 ... 1|
(41)

(Mansour 2000)。

另请参阅

比内公式, 整数序列, 二次映射, 二次递推方程, 递推方程

使用 Wolfram|Alpha 探索

参考文献

Gosper, R. W. 和 Salamin, E. Beeler, M.; Gosper, R. W.; 和 Schroeppel, R. 中的项目 14。HAKMEM。 Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 8-9, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/recurrence.html#item14.Grosjean, C. C. 在 单变量和多变量多项式及其应用主题：纪念 P.L. Chebyshev (1821-1894) 的卷 (Ed. T. M. Rassias, H. M. Srivastava, 和 A. Yanushauskas)。新加坡：World Scientific, 1993。Mansour, T. "避免来自 S_k 的模式以及来自 S_3 的至少两个模式的排列。" 2000 年 7 月 31 日。 http://arxiv.org/abs/math.CO/0007194.Sloane, N. J. A. 整数序列在线百科全书中的序列 A010892。

在 Wolfram|Alpha 中引用

线性递推方程

引用为

Weisstein, Eric W. “线性递推方程。”来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/LinearRecurrenceEquation.html

主题分类