小学奥数:有 m 级楼梯，每次可上1级、2级或3级，有几种走法？

TSC999

mathematica 发表于 2017-5-12 10:22
这个公式我在10楼提过了呀

\[\frac{1}{44} \left(2 \sqrt[3]{11 \left(3 \sqrt{33}+77\right)}+\sqr ...

您那个公式可以简化成：

\( \frac{1}{22×3^{n+1} } \left(22+ \sqrt[3]{847+33 \sqrt{33}}+\sqrt[3]{847-33 \sqrt{33}}\right) \left(1+\sqrt[3]{19+3 \sqrt{33}}+\sqrt[3]{19-3 \sqrt{33}}\right)^n \)

1. u = 1/3 (1 + Power[19 - 3 Sqrt[33], (3)^-1] + Power[19 + 3 Sqrt[33], (
   
2.      3)^-1]);
   
3. f[n_] := N[(2 u^2 + u + 5)/22 u^n, 100];
   
4. g1[n_] :=
   
5.   N[1/(44 3^(
   
6.      n + 1)) (44 + Power[6776 - 264 Sqrt[33], (3)^-1] +
   
7.       2 Power[11 (77 + 3 Sqrt[33]), (3)^-1]) (1 + Power[
   
8.       19 - 3 Sqrt[33], (3)^-1] + Power[19 + 3 Sqrt[33], (3)^-1])^n,
   
9.    100];
   
10. g2[n_] :=
    
11.   N[1/(22 3^(
    
12.      n + 1)) (22 + Power[847 - 33 Sqrt[33], (3)^-1] + Power[
    
13.       847 + 33 Sqrt[33], (3)^-1]) (1 + Power[19 - 3 Sqrt[33], (
    
14.       3)^-1] + Power[19 + 3 Sqrt[33], (3)^-1])^n, 100];
    
15. f[7]
    
16. g1[7]
    
17. g2[7]
    

复制代码

经验证，您的公式与 elim 的完全一样，计算结果纹丝不差。只是我不知道，elim 的原公式中为何多出一项 0.5，我引用时已经把 0.5 给删掉了。

TSC999

不论是 【mathematica】的通项公式，还是 elim 的通项公式，都算不出整数来，但是经过四舍五入得到的整数，又全都正确。
不知道有没有不需要四舍五入、直接算出来即是整数的通项公式？

mathe

矩阵形式和多项式环形式都是直接整数计算

mathematica

mathe 发表于 2017-5-14 13:28
矩阵形式和多项式环形式都是直接整数计算

矩阵形式,可以快速计算,而多项式似乎不行吧?

mathe

mathematica 发表于 2017-5-14 14:34
矩阵形式,可以快速计算,而多项式似乎不行吧?

你应该先好好看看前面的回复，如果有不明白的，可以继续提问

kastin

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 \pi  n}{4} +3\cos \frac{3 \pi  n}{4} \right)=-2^{\frac{n}{2}-1}\sqrt{10}\cos\left(\frac{3 \pi  n}{4}-\arctan\frac{1}{3}\right)\tag{3.2}$$前面的根号2为特征根的模长。

同样，对于三阶线性递推方程，其特征方程是三次代数方程，特征根可能是三个实根，或者一个实根与一对共轭虚根。如果三个实根中存在二重根或者三重根的特殊情况，这些情况与单根情形不同，需要特殊处理。楼主的问题属于一个实根与一对共轭虚根情形，故仅讨论这种情况。因此通项公式是 `(1)` 和 `(3)` 的组合形式。类似地，也可以同样将共轭虚根写成三角函数形式化简。
$$a_n=\frac{1}{22\*3^{n+1} } \left(22+\sqrt[3]{847+33 \sqrt{33}}+\sqrt[3]{847-33 \sqrt{33}}\right) \left(1+\sqrt[3]{19+3 \sqrt{33}}+\sqrt[3]{19-3 \sqrt{33}}\right)^n+\frac{1}{11\*3^{n+1}}\sqrt{-22 \sqrt[3]{847+33 \sqrt{33}}+\left(847+33 \sqrt{33}\right)^{2/3}-22 \sqrt[3]{847-33 \sqrt{33}}+\left(847-33 \sqrt{33}\right)^{2/3}+396}\left(-\sqrt[3]{19+3 \sqrt{33}}+\left(19+3 \sqrt{33}\right)^{2/3}-\sqrt[3]{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[3]{11} \left(\sqrt[3]{77-3 \sqrt{33}}-\sqrt[3]{77+3 \sqrt{33}}\right)}{\sqrt[3]{847+33 \sqrt{33}}+\sqrt[3]{847-33 \sqrt{33}}-44},\theta_2=\arctan \frac{\sqrt{3} \left(\sqrt[3]{19+3 \sqrt{33}}-\sqrt[3]{19-3 \sqrt{33}}\right)}{\sqrt[3]{19+3 \sqrt{33}}+\sqrt[3]{19-3 \sqrt{33}}-2}-\pi.$$结果验证符合

1. Subscript[\[Theta], 1] =
   
2.   Arg[1/3 -
   
3.     1/264 (1 + I Sqrt[3]) Power[6776 - 264 Sqrt[33], (
   
4.      3)^-1] - ((1 - I Sqrt[3]) Power[77 + 3 Sqrt[33], (3)^-1])/(
   
5.     12 11^(2/3))];
   
6. Subscript[\[Theta], 2] =
   
7.   Arg[1/3 - 1/6 (1 - I Sqrt[3]) Power[19 - 3 Sqrt[33], (3)^-1] -
   
8.     1/6 (1 + I Sqrt[3]) Power[19 + 3 Sqrt[33], (3)^-1]];
   
9. a[n_] = 1/
   
10.     44 (44 + Power[6776 - 264 Sqrt[33], (3)^-1] +
    
11.       2 Power[11 (77 + 3 Sqrt[33]), (3)^-1]) 3^(-n -
    
12.      1) (1 + Power[19 - 3 Sqrt[33], (3)^-1] + Power[19 + 3 Sqrt[33], (
    
13.       3)^-1])^n +
    
14.    1/(11*3^(n +
    
15.           1)) Sqrt[(-(19 + 3 Sqrt[33])^(1/3) + (19 + 3 Sqrt[33])^(2/
    
16.             3) - (19 - 3 Sqrt[33])^(1/3) + (19 - 3 Sqrt[33])^(2/3) -
    
17.          3)^n (-22 (847 + 33 Sqrt[33])^(1/3) + (847 + 33 Sqrt[33])^(2/
    
18.            3) - 22 (847 - 33 Sqrt[33])^(1/3) + (847 - 33 Sqrt[33])^(2/
    
19.            3) + 396)] Cos[
    
20.      Subscript[\[Theta], 1] + n  Subscript[\[Theta], 2]] // Simplify
    
21. a100 = RecurrenceTable[{x[n] == x[n - 1] + x[n - 2] + x[n - 3],
    
22.    x[1] == 1, x[2] == 2, x[3] == 4}, x[n], {n, 100, 100}]
    
23. a[100] // N[#, 1+IntegerLength @@ a100] &  (* 复杂根式100次方化简需要很长时间，也许根本电脑无法给出确定结果，但可通过数值验算到任意精度 *)

复制代码

mathematica

mathe 发表于 2017-5-14 15:17
你应该先好好看看前面的回复，如果有不明白的，可以继续提问

你在17楼的回复中说
http://bbs.emath.ac.cn/forum.php ... =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级）。

冒昧请教大师！可以有通项公式吗？

mathe

设$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$

mathe

类似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}$等