和Fibonacci相关的化简问题

chyanog

http://andrejv.wordpress.com/2010/02/11/fibonacci-numbers/ 不方便翻墙的看这里http://chyanog.iteye.com/blog/1858532 上述链接里的maxima代码比Mathematica快的多，不知道mathematica代码能否进一步优化呢?

1. fibRatio[a_, b_] := FullSimplify[Sum[Fibonacci[n + i], {i, 0, a}]/Fibonacci[n + b]]
2. Select[Flatten[Table[{a, b, fibRatio[a, b]}, {a, 1, 10}, {b, 1, a}], 1], IntegerQ[#[[3]]] &]

复制代码

wayne

那是因为FullSimplify的时候没有告诉软件 n 是什么类型的数

1. fibRatio[a_,b_]:=FullSimplify[Sum[Fibonacci[n+i],{i,0,a}]/Fibonacci[n+b],Element[n,Integers]&&n>0];
   
2. Select[Flatten[Table[{a,b,fibRatio[a,b]},{a,1,20},{b,1,a}],1],IntegerQ[#[[3]]]&]
   

复制代码

不负所望，返回全部结果，速度也不算慢：

{{2, 2, 2}, {5, 4, 4}, {9, 6, 11}, {13, 8, 29}, {17, 10, 76}}

wayne

跑了一下100的情况：

{2,2,2}
{5,4,4}
{9,6,11}
{13,8,29}
{17,10,76}
{21,12,199}
{25,14,521}
{29,16,1364}
{33,18,3571}
{37,20,9349}
{41,22,24476}
{45,24,64079}
{49,26,167761}
{53,28,439204}
{57,30,1149851}
{61,32,3010349}
{65,34,7881196}
{69,36,20633239}
{73,38,54018521}
{77,40,141422324}
{81,42,370248451}
{85,44,969323029}
{89,46,2537720636}
{93,48,6643838879}
{97,50,17393796001}

wayne

有点意思，除了第一组{2,2,2}外，规律是很明显的:

$\sum_{k=0}^{4m-3}F_{n+k} =C_mF_{n+2m}$，m，n 为任意正整数。
其中$C_m=F_{2m-2}+F_{2m-4}$，也即是A093960数列：
在整数序列大全上找到了条目：
http://oeis.org/A093960

特例：n=0，m=1时，即是F数列的定义形式F0+F1=F2

chyanog

后来我也找到两个相对快点的方法，同时也发现Mathematica9的化简速度比7、8大概慢了一半：

1. 
   
2. fibRatio[a_, b_] := FunctionExpand[Sum[Fibonacci[n + i], {i, 0, a}]/Fibonacci[n + b],
   
3.   Element[n, Integers]]
   
4. Select[Join @@ Table[{a, b, fibRatio[a, b]}, {a, 1, 20}, {b, 1, a}],
   
5.   IntegerQ@Last@# &] // AbsoluteTiming

复制代码

1. Clear["`*"];
   
2. fibRatio[a_, b_] := (2^(-1 - a +  b) (-2^a (1 - Sqrt[5])^(1 + n) - (1 - Sqrt[5])^(a + n) (-3 +   Sqrt[5]) + (1 + Sqrt[5])^
   
3.          n (2^a (1 + Sqrt[5]) - (1 + Sqrt[5])^a (3 + Sqrt[5]))))/((1 - Sqrt[5])^(b + n) - (1 + Sqrt[5])^(b + n));
   
4. 
   
5. Select[Join @@ Table[{a, b, fibRatio[a, b] // Cancel}, {a, 1, 20}, {b, 1, a}],
   
6.   IntegerQ[#[[3]]] &] // AbsoluteTiming

复制代码