循环数列的通项公式

chyanog

设数列{a(n)}各项为a1,a2,a3,...ak,...a1,a2,a3,...ak,...，其中a1,a2,...ak(k∈N*)循环出现，则称{a(n)}为循环数列。
这类数列的通项除了可以用mod, floor等表示外，还可以用三角函数等。
Mathematica的RSolve解这类递推方程应该用的是先求特征方程（通过Trace及TraceInternal -> True看得出），然后用待定系数法解线性方程组得到特解，速度很慢，如RSolve[{a[n]==a[n-11],Sequence@@Table[a==c,{i,11}]},a[n],n]；
而Maple的rsolve处理这类递推方程速度很快，如 rsolve (a (n) = a (n - 23), a) 可以瞬间得到结果，从形式上看是用RootSum表示的，不知道Maple用的是什么算法，
是ZTransform及InverseZTransform吗？


补充内容 (2015-4-3 11:22):
注意：Maple给出的不是通解，而是特解。

kastin

循环出现的数列大多跟单位根有关，因为单位根的幂是循环遍历各个根，可以看成一个循环群。
比如 `a_{n+4}=a_n` 的通解就是 `c_4 (-i)^n+c_2 i^n+c_3 (-1)^n+c_1` ，其中  `1, i, -1, -i`分别就是1的4个四次方根。
同样，`a_{n+5}=a_n`的通解表示为 `\D c_2 \exp( \frac{2 \pi i}{5}) + c_3 \exp( \frac{4 \pi i}{5}) + c_4 \exp( \frac{6 \pi i}{5}) + c_5 \exp( \frac{8 \pi i}{5}) + c_1`
上面可以改写为三角函数形式，或根式 $$a_n \to c_2 \left(-\frac{1}{4}+\frac{\sqrt{5}}{4}+i \sqrt{\frac{5}{8}+\frac{\sqrt{5}}{8}}\right)^n+c_3 \left(-\frac{1}{4}-\frac{\sqrt{5}}{4}+i \sqrt{\frac{5}{8}-\frac{\sqrt{5}}{8}}\right)^n+c_4 \left(-\frac{1}{4}-\frac{\sqrt{5}}{4}-i \sqrt{\frac{5}{8}-\frac{\sqrt{5}}{8}}\right)^n+c_5 \left(-\frac{1}{4}+\frac{\sqrt{5}}{4}-i \sqrt{\frac{5}{8}+\frac{\sqrt{5}}{8}}\right)^n+c_1$$

至于23次方根，照上面同样可求出通解。

kastin

kastin 发表于 2015-4-2 17:04
循环出现的数列大多跟单位根有关，因为单位根的幂是循环遍历各个根，可以看成一个循环群。
比如 `a_{n+4}= ...

特解有点麻烦，因为需要解方程。而这里面的n是未知数，所以需要全部展开。

zeroieme

kastin 发表于 2015-4-2 18:26
特解有点麻烦，因为需要解方程。而这里面的n是未知数，所以需要全部展开。

请教，对于从a(1)递归到a(n-1)的数列怎么求通项公式？
$a(n)=sum _{i=1}^{n-1} a(i)f(i)$

kastin

zeroieme 发表于 2015-4-2 19:30
请教，对于从a(1)递归到a(n-1)的数列怎么求通项公式？
$a(n)=sum _{i=1}^{n-1} a(i)f(i)$

若 `f(i)` 是常值，这种递归关系便是典型的线性齐次差分方程，一般的解法是：列出特征方程，求出特征根，代入通解公式即可（重根情况，通解中相关项的形式有所改变）。

另外还可以用母函数（生成函数）法，但仍然避不开求解 `n` 次代数方程这一步(因为母函数法需要对分母因式分分解)，所以当 `n \geqslant 5` 时，特征根不一定能用根式表达，这就需要数值求解了。

zeroieme

kastin 发表于 2015-4-2 20:00
若 `f(i)` 是常值，这种递归关系便是典型的线性齐次差分方程，一般的解法是：列出特征方程，求出特征根， ...

$(i!*(n-i!)/(n!))(a*p^i+b*q^i)$

zeroieme

kastin 发表于 2015-4-2 20:00
若 `f(i)` 是常值，这种递归关系便是典型的线性齐次差分方程，一般的解法是：列出特征方程，求出特征根， ...

f(i)是个相对复杂的函数
具体可以看我几天前的求助帖
http://bbs.emath.ac.cn/thread-6070-1-1.html

wayne

不知道Maple用的是什么算法

Maple2015出来了。
=====
该不会是先对前n-1项做 拉格朗日插值，然后再推广到周期域吧的

kastin

zeroieme 发表于 2015-4-3 09:26
f(i)是个相对复杂的函数
具体可以看我几天前的求助帖
http://bbs.emath.ac.cn/thread-6070-1-1.html

`f`本身是什么样的不重要，只要能计算出确定的数值即可。刚刚才发现，关键在于递归关系的阶数是 `n-1`，上面提到的特征方程的方法似乎并不可行。例如我们给出$$a_n=a_{n-1}+a_{n-1}+\cdots+a_1$$特征方程为$$x^{n-1}=x^{n-2}+x^{n-3}+\cdots+x+1$$因为 `n` 是变数，故特征方程只在局部有效，所以对于通解并无意义。除非是精心构造的系数和初值，这种形式的递推关系也不一定存在封闭的通解形式，因为递归关系的阶并不是稳定的。

chyanog

wayne 发表于 2015-4-3 10:02
Maple2015出来了。
=====
该不会是先对前n-1项做 拉格朗日插值，然后再推广到周期域吧的

不清楚，不过我猜出来了一个“公式”，也可以瞬间出结果，但不会证明。比如11阶的，

1. Block[{m=11,x=(-1)^(2i/m)},Sum[x^n/m FromDigits[Array[C,m],x],{i,m}]]
   
2. Collect[Table[%,{n,30}],_C,RootReduce]

复制代码