主題
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)。

另請參閱

比內公式, 整數序列, 二次對映, 二次遞推方程, 遞推方程

使用 探索

參考文獻

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。

在 中引用

線性遞推方程

引用為

Weisstein, Eric W. “線性遞推方程。”來自 —— 資源。 https://mathworld.tw/LinearRecurrenceEquation.html

主題分類