#John Kim #Use whatever you like Help:=proc(): print(` GuessRec1(L,r) `): end: #GuessRec1(L,r): inputs a sequence of numbers, L, and a pos. #integer r, and tries to guess a linear recurrence equation #of order r satisfied by it #L(n)+c1*L(n-1)+...+cr*L(n-r)=0 for all n within the range #The output would be given as a list of r numbers #[[c1,c2,...,cr],InitialConditions] #For example, the Fibonacci sequence is #[[-1,-1], [1,1]] GuessRec1:=proc(L,r) local c,i,var,eq: if nops(L)<=2*r+6 then RETURN(FAIL): fi: var:={seq(c[i],i=1..r)}: eq:={seq( L[n]+add(c[i]*L[n-i],i=1..r)=0 , n=r+1..nops(L))}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): fi: [[seq(subs(var, c[i]),i=1..r)], L[1..r] ] ; end: #GuessRec(L): inputs a sequence of numbers, L, # and tries to guess a linear recurrence equation #of some order, r, satisfied by it #L(n)+c1*L(n-1)+...+cr*L(n-r)=0 for all n within the range #The output would be given as a list of r numbers #[[c1,c2,...,cr],InitialConditions] #For example, the Fibonacci sequence is #[[-1,-1], [1,1]] GuessRec:=proc(L) local r,ans: for r from 1 to (nops(L)-6)/2 do ans:=GuessRec1(L,r): if ans<>FAIL then RETURN(ans): fi: od: FAIL: end: #RecToSeq(C,n): inputs a C-finite sequence, in our notation, and a pos. integer n, #and outputs the list of length n with the first n terms of the sequence. #For example, RecToSeq([[-1,-1],[1,1]],10); should output [1,1,2,3,5,8,13,21,34,55]. RecToSeq:=proc(C,n) local L,r,i,j: L:=C[2]: r:=nops(C[1]): for i from r+1 to n do L:=[op(L),add(-C[1][j]*L[i-j],j=1..r)]: od: L: end: #Add1(C1,C2): inputs two C-finite sequences in our notation and outputs a C-finite #sequence that describes their sum. For example Add1([[-1],[1]],[[-2],[1]]); #should output [[-3,2],[2,3]]. Add1:=proc(C1,C2) local r1,r2,L1,L2,L: r1:=nops(C1[1]): r2:=nops(C2[1]): L1:=RecToSeq(C1,2*(r1+r2)+7): L2:=RecToSeq(C2,2*(r1+r2)+7): L:=L1+L2: GuessRec(L): end: #Mult1(C1,C2): inputs two C-finite sequences in our notation and outputs the C-finite #sequence that is their product. For example Mult1([[-2],[1]],[[-3],[1]]); #should output [[-6],[1]]. Mult1:=proc(C1,C2) local r1,r2,L1,L2,L,i: r1:=nops(C1[1]): r2:=nops(C2[1]): L1:=RecToSeq(C1,2*(r1*r2)+7): L2:=RecToSeq(C2,2*(r1*r2)+7): L:=[seq(L1[i]*L2[i],i=1..nops(L1))]: GuessRec(L): end: #BT(C): inputs a C-finite sequence and outputs its Binomial Transform BT:=proc(C) local r,L,B: r:=nops(C): L:=RecToSeq(C,2*r+7): B:=[seq(expand(add(binomial(n,i)*L[i+1],i=0..n)),n=0..nops(L)-1)]: GuessRec(B): end: #Tsect(C,t,r) that inputs a C-finite sequence and a positive integer t, #non-negative integer r, (0<=r