本帖最后由 TSC999 于 2017-5-12 16:49 编辑
mathematica 发表于 2017-5-12 10:22
这个公式我在10楼提过了呀
\[\frac{1}{44} \left(2 \sqrt{11 \left(3 \sqrt{33}+77\right)}+\sqr ...
您那个公式可以简化成：
\( \frac{1}{22×3^{n+1} } \left(22+ \sqrt{847+33 \sqrt{33}}+\sqrt{847-33 \sqrt{33}}\right) \left(1+\sqrt{19+3 \sqrt{33}}+\sqrt{19-3 \sqrt{33}}\right)^n \)
u = 1/3 (1 + Power, (3)^-1] + Power, (
3)^-1]);
f := N[(2 u^2 + u + 5)/22 u^n, 100];
g1 :=
N[1/(44 3^(
n + 1)) (44 + Power, (3)^-1] +
2 Power), (3)^-1]) (1 + Power[
19 - 3 Sqrt, (3)^-1] + Power, (3)^-1])^n,
100];
g2 :=
N[1/(22 3^(
n + 1)) (22 + Power, (3)^-1] + Power[
847 + 33 Sqrt, (3)^-1]) (1 + Power, (
3)^-1] + Power, (3)^-1])^n, 100];
f
g1
g2
经验证，您的公式与 elim 的完全一样，计算结果纹丝不差。只是我不知道，elim 的原公式中为何多出一项 0.5，我引用时已经把 0.5 给删掉了。
不论是 【mathematica】的通项公式，还是 elim 的通项公式，都算不出整数来，但是经过四舍五入得到的整数，又全都正确。
不知道有没有不需要四舍五入、直接算出来即是整数的通项公式？
矩阵形式和多项式环形式都是直接整数计算
mathe 发表于 2017-5-14 13:28
矩阵形式和多项式环形式都是直接整数计算
矩阵形式,可以快速计算,而多项式似乎不行吧?
mathematica 发表于 2017-5-14 14:34
矩阵形式,可以快速计算,而多项式似乎不行吧?
你应该先好好看看前面的回复，如果有不明白的，可以继续提问
本帖最后由 kastin 于 2017-5-14 16:05 编辑
TSC999 发表于 2017-5-14 10:37
不论是 【mathematica】的通项公式，还是 elim 的通项公式，都算不出整数来，但是经过四舍五入得到的整数， ...
因为他们舍去了小量部分，所以要四舍五入，精确的通项公式不能舍去小量部分，并且恰好就能算得是整数。
这一点从斐波那契数列的通项公式就可得知——$$F_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]\tag{1}$$上面方括号内第二项底数绝对值是0.618...，故其 `n` 次幂除以`\sqrt{5}`之后不超过0.5（`n\geqslant 1`），故可写成四舍五入形式：$$\mathrm{Round}\left(\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n\right)\tag{2}$$当然，由于上面是二阶线性递推方程，特征根为两实单根（不同的实数），所以通项公式直接就能写出来；当特征根为两共轭虚根时候，通项公式最简形式就需要用三角函数表示了。
例如二阶递推式 `c_{n+2}=-2c_{n+1}-2c_n\;(c_1=c_2=1)` 有两共轭虚根 `-1\pm i`，标准通项公式为复数形式:$$\frac{i-1}{4}\left((1+2 i) (-1-i)^n+(2+i) (-1+i)^n\right)\tag{3.1}$$这个形式可以通过二项式定理展开合并，写成纯实数的多项式形式，但会非常复杂，且需要根据 `n` 模4的结果分好几类。
事实上，由于特征根为复数，其幅角为 `\D\pm\frac{3}{4}\pi`，因此通项公式可用欧拉公式实数化，结果必然是特征根模长的幂与该幅角 `n` 倍角正余弦的乘积项的形式：$$c_n=-2^{\frac{n}{2}-1} \left(\sin\frac{3 \pin}{4} +3\cos \frac{3 \pin}{4} \right)=-2^{\frac{n}{2}-1}\sqrt{10}\cos\left(\frac{3 \pin}{4}-\arctan\frac{1}{3}\right)\tag{3.2}$$前面的根号2为特征根的模长。
同样，对于三阶线性递推方程，其特征方程是三次代数方程，特征根可能是三个实根，或者一个实根与一对共轭虚根。如果三个实根中存在二重根或者三重根的特殊情况，这些情况与单根情形不同，需要特殊处理。楼主的问题属于一个实根与一对共轭虚根情形，故仅讨论这种情况。因此通项公式是 `(1)` 和 `(3)` 的组合形式。类似地，也可以同样将共轭虚根写成三角函数形式化简。
$$a_n=\frac{1}{22\*3^{n+1} } \left(22+\sqrt{847+33 \sqrt{33}}+\sqrt{847-33 \sqrt{33}}\right) \left(1+\sqrt{19+3 \sqrt{33}}+\sqrt{19-3 \sqrt{33}}\right)^n+\frac{1}{11\*3^{n+1}}\sqrt{-22 \sqrt{847+33 \sqrt{33}}+\left(847+33 \sqrt{33}\right)^{2/3}-22 \sqrt{847-33 \sqrt{33}}+\left(847-33 \sqrt{33}\right)^{2/3}+396}\left(-\sqrt{19+3 \sqrt{33}}+\left(19+3 \sqrt{33}\right)^{2/3}-\sqrt{19-3 \sqrt{33}}+\left(19-3 \sqrt{33}\right)^{2/3}-3\right)^{\frac{n}{2}}\cos(\theta_1+n\theta_2)$$其中$$\theta_1=\arctan\frac{\sqrt{3} \sqrt{11} \left(\sqrt{77-3 \sqrt{33}}-\sqrt{77+3 \sqrt{33}}\right)}{\sqrt{847+33 \sqrt{33}}+\sqrt{847-33 \sqrt{33}}-44},\theta_2=\arctan \frac{\sqrt{3} \left(\sqrt{19+3 \sqrt{33}}-\sqrt{19-3 \sqrt{33}}\right)}{\sqrt{19+3 \sqrt{33}}+\sqrt{19-3 \sqrt{33}}-2}-\pi.$$结果验证符合
Subscript[\, 1] =
Arg[1/3 -
1/264 (1 + I Sqrt) Power, (
3)^-1] - ((1 - I Sqrt) Power, (3)^-1])/(
12 11^(2/3))];
Subscript[\, 2] =
Arg) Power, (3)^-1] -
1/6 (1 + I Sqrt) Power, (3)^-1]];
a = 1/
44 (44 + Power, (3)^-1] +
2 Power), (3)^-1]) 3^(-n -
1) (1 + Power, (3)^-1] + Power, (
3)^-1])^n +
1/(11*3^(n +
1)) Sqrt[(-(19 + 3 Sqrt)^(1/3) + (19 + 3 Sqrt)^(2/
3) - (19 - 3 Sqrt)^(1/3) + (19 - 3 Sqrt)^(2/3) -
3)^n (-22 (847 + 33 Sqrt)^(1/3) + (847 + 33 Sqrt)^(2/
3) - 22 (847 - 33 Sqrt)^(1/3) + (847 - 33 Sqrt)^(2/
3) + 396)] Cos[
Subscript[\, 1] + nSubscript[\, 2]] // Simplify
a100 = RecurrenceTable[{x == x + x + x,
x == 1, x == 2, x == 4}, x, {n, 100, 100}]
a // N[#, 1+IntegerLength @@ a100] &(* 复杂根式100次方化简需要很长时间，也许根本电脑无法给出确定结果，但可通过数值验算到任意精度 *)
mathe 发表于 2017-5-14 15:17
你应该先好好看看前面的回复，如果有不明白的，可以继续提问
你在17楼的回复中说
http://bbs.emath.ac.cn/forum.php?mod=redirect&goto=findpost&ptid=9480&pid=66047
递推计算在我的电脑上用pari/gp要到200,000项才会感觉到延时，但是计算到2,000,000项就完全不行了
20,000,000项也就是数秒的时间。只是这时Pari/gp默认内存大小不够用，需要增加内存
为什么你一个方法会有不同的差距???????????
kastin 发表于 2017-5-14 15:56
因为他们舍去了小量部分，所以要四舍五入，精确的通项公式不能舍去小量部分，并且恰好就能算得是整数。 ...
1，1，1，2，2，3，4，5，7，9，12，16，21，28，37，49，65，86，..........
相当于有 m(m≥2) 级楼梯，每次可上2级 , 3级，有几种走法（不能上1级）。
冒昧请教大师！可以有通项公式吗？
设$r_1,r_2,r_3$是方程$x^3-x-1=0$的三个根，所以$r_1+r_2+r_3=0,r_1r_2+r_2r_3+r_3r_1=-1,r_1r_2r_3=1$
可以设通项为$u_1r_1^n+u_2r_2^n+u_3r_3^n$
于是$[(1,1,1),(r_1,r_2,r_3),(r_1^2,r_2^2,r_3^2)][(u_1),(u_2),(u_3)]=[(1),(0),(1)]$
于是$u_3=\frac{1+r_1r_2}{r_3^2-(r_1+r_2)r_3+r_1r_2}=\frac{1+1/r_3}{r_3^2+1+2/r_3}=\frac{r_3+1}{r_3^3+r_3+2}=\frac{r_3+1}{2r_3+3}$
类似可以得出$u_1,u_2$
于是$a_n=\frac{r_1+1}{2r_1+3}r_1^n+\frac{r_2+1}{2r_2+3}r_2^n+\frac{r_3+1}{2r_3+3}r_3^n$
类似16#,我们先要计算$x^n(mod x^3-x-1)=u_n+v_n*x+w_n*x^2$
其中$u_1=0,v_1=1,w_1=0$
假设我们已经知道$u_k,v_k,w_k$
于是我们只要计算$Mod((u_k+v_k*x+w_k*x^2)^2, x^3-x-1)=Mod(w_k^2*x^4 + 2*w_k*v_k*x^3 + (2*w_k*u_k + v_k^2)*x^2 + 2*v_k*u_k*x + u_k^2,x^3-x-1)=Mod((2*w_k*v_k*x^3 + (2*w_k*u_k + v_k^2+w_k^2)*x^2 + (2*v_k*u_k+w_k^2)*x + u_k^2,x^3-x-1)=Mod( (2*w_k*u_k + v_k^2+w_k^2)*x^2 + (2*v_k*u_k+w_k^2+ 2*w_k*v_k)*x + u_k^2+ 2*w_k*v_k,x^3-x-1)$
由此可以算出$u_{2k},v_{2k},w_{2k}$,同样还可以容易计算$u_{2k+1},v_{2k+1},w_{2k+1}$等