三阶递推数列

葡萄糖

谁知道三阶递推数列的通解？
http://bbs.cnool.net/cthread-104349871.html#115403880
a_1=a,a_2=b,a_3=c

gxqcn

递推数列一般是解其对应的特征方程。

葡萄糖

gxqcn 发表于 2014-4-6 08:46
递推数列一般是解其对应的特征方程。

泰波那契数列(Tribonacci Number)是斐波拉契数列(Fibonacci number)的推广！

xiaoshuchong

理论上来讲并不难，我们知道线性递推数列的通项肯定是特征根n次方的线性组合。

麻烦的是系数怎么处理比较好？三阶递推需要算三次方程，特征根已经很复杂。

我们可以考虑将系数表示成特征根的多项式，使得最终的表达式足够简洁。

于是有如下Tribonacci数列的通项公式

\[\begin{eqnarray*}
F_{n}&=&\frac{1}{22}\left[\begin{array}{c}
a\\
b\\
c
\end{array}\right]^{T}\left[\begin{array}{ccc}
8\alpha^{2}-7\alpha-13 & 8\beta^{2}-7\beta-13 & 8\gamma^{2}-7\gamma-13\\
-5\alpha^{2}+14\alpha-7 & -5\beta^{2}+14\beta-7 & -5\gamma^{2}+14\gamma-7\\
\alpha^{2}-5\alpha+8 & \beta^{2}-5\beta+8 & \gamma^{2}-5\gamma+8
\end{array}\right]\left[\begin{array}{c}
\alpha^{n}\\
\beta^{n}\\
\gamma^{n}
\end{array}\right]
\end{eqnarray*}\]
其中，$\alpha,\beta,\gamma$是方程$x^{3}-x^{2}-x-1=0$的三个根

wayne

对于Tribonacci 数列, 如果是计算机计算, 其实写到这里就行, 因为矩阵幂运算的效率可以很高:
\[(a_{n+2},a_{n+1},a_{n})^T = \left(
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{array}
\right)^{n-1}*(a_3,a_2,a_1)^T\]

xiaoshuchong

wayne 发表于 2022-3-26 12:43
对于Tribonacci 数列, 如果是计算机计算, 其实写到这里就行, 因为矩阵幂运算的效率可以很高:
\[(a_{n+2},a ...

矩阵版的快速幂算法，对于一般的线性递推数列都是适用的。

xiaoshuchong

wayne 发表于 2022-3-26 12:43
对于Tribonacci 数列, 如果是计算机计算, 其实写到这里就行, 因为矩阵幂运算的效率可以很高:
\[(a_{n+2},a ...

矩阵版的快速幂算法，对于一般的线性递推数列都是适用的。