#Charles Wolf #Feel free to use any of this. #I used GuessRec from class in some of my programs. I also #assumed GuessRec should be able to figure out the recursion #with a sequence of length 20. I'm not sure if this was too #liberal or too conservative, but the programs seem to work #fine. Help:=proc(): print(` GuessRec1(L,r),GuessRec(L),RecToSeq(C,n),BT(C),Add1(C1,C2),Mult1(C1,C2),Tsect(C,t,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: ########################################################### #2. #RecToSeq(C,n): inputs a C-finite sequence C and a positive #integer n and outputs the list of length n with the first n #terms of the sequence. RecToSeq:=proc(C,n) local L2,i,j,L1,k,m,L3: L2:=C[2]: if nops(L2)+1>=n then [seq(L2[i],i=1..n)]: else L1:=C[1]: L3:=L2: for j from nops(L2)+1 to n do m:=-1*add(L1[k]*L3[j-k],k=1..nops(L2)): L3:=[op(L3),m]: od: L3: fi: end: ############################################################# #3. #Add1(C1,C2): inputs two C-finite sequences in our notation #and outputs a C-finite sequence that describes their sum. Add1:=proc(C1,C2): GuessRec(RecToSeq(C1,20)+RecToSeq(C2,20): end: ############################################################# #4.Mult1(C1,C2): inputs two C-finite sequences in our #notation and outputs a C-finite sequence that describes #their product. Mult1:=proc(C1,C2) local L1,L2, i: L1:=RecToSeq(C1,20): L2:=RecToSeq(C2,20): GuessRec([seq(L1[i]*L2[i],i=1..20)]): end: #It's strange that Maple adds sequences term by term but does #not multiply: if you input something like `[1\$10]+[2\$10]` #the output will be `[3,3,3,3,3,3,3,3,3,3],` but if you #input `[1\$10]*[2\$10],` the output will be #`(1,1,1,1,1,1,1,1,1,1)(2,2,2,2,2,2,2,2,2,2).` I'm using #Maple 13, so perhaps it was updated in Maple 15. If not, #hopefully it will be updated in the next edition. ########################################################### #5. #BT(C): inputs a C-finite sequence and outputs its Binomial #Transform. BT:=proc(C) local L,i,j,L1: L:=RecToSeq(C,20): L1:=[seq(add(binomial(j,i)*L[i],i=1..j),j=1..nops(L))]: GuessRec(L1): end: ############################################################ #6. #Tsect(C,t,r): inputs a C-finite sequence and a positive #integer t, non-negative integer r, (0 ≤ r < t) such that if #C is the C-finite description of a sequence a(n), then the #output is the C finite description of the sequence a(tm+r), #m=0,1,2,3,4 ... Tsect:=proc(C,t,r) local L,L1,m: L:=(RecToSeq(C,t*20+r): L1:=[seq(L[t*m+r+1],m=0..20)]: GuessRec(L1): end: