#Homework by Ben Miles for Experimental math assigned 2/6 OK to post
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:=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 and a pos. integer n, and outputs the list of the first n terms of the sequence
RecToSeq:=proc(C,n) local l,k,G,i: option remember:
l:=nops(C[2]):
k:=nops(C[1]):
G:=C[2]:
if l<k then
 RETURN("Not Enough Initial Conditions"):
fi:
for i from l+1 to n do
G:=[op(G),-add(C[1][j-(i-k-1)]*G[2*i-k-1-j],j=i-k..i-1)]:
od:
G:
end:

#Add1(C1,C2) inputs two C-finite sequences and outputs a C-finite sequence that describes their sum
Add1:=proc(C1,C2) local L1,L2,L, n1,n2,n,i:
n1:=nops(C1[1])*3+10:
n2:=nops(C2[1])*3+10:
n:=max(n1,n2);
L1:=RecToSeq(C1,n);
L2:=RecToSeq(C2,n);
L:=[];
for i from 1 to n do
L:=[op(L),L1[i]+L2[i]]:
od:
GuessRec(L):
end:

#Mult1(C1,C2) inputs two C-finite sequences and outputs their product
Mult1:=proc(C1,C2) local L1,L2,L, n1,n2,n,i:
n1:=nops(C1[1])*3+10:
n2:=nops(C2[1])*3+10:
n:=n1*n2;
L1:=RecToSeq(C1,n);
L2:=RecToSeq(C2,n);
L:=[];
for i from 1 to n do
L:=[op(L),L1[i]*L2[i]]:
od:
GuessRec(L):
end:

#BT(C) inputs a C-finite sequence and outputs its Binomial Transform
BT:=proc(C) local L,G,i,n;
n:=nops(C[1])*3+10;
L:=[];
G:=RecToSeq(C,n);
for i from 1 to n do
 L:=[op(L),sum(binomial(i,j-1)*G[j],j=1..i)];
od:
GuessRec(L);
end:

#Tsect(C,t,r) inputs a C-finite sequence and a positive integer t, non-negative integer r, such that if C is the C-finite description of a sequence a(n), then the output is the description of the sequence a(tm+r), m=0,1,2,3,4 ...
Tsect:=proc(C,t,r) local n,G,L,i:
n:= (nops(C[1])*3+10)*t+r:
G:= RecToSeq(C,n);
L:=[];
for i from 1 to (nops(C[1])*3+10) do:
 L:=[op(L), G[t*i+r]];
od:
GuessRec(L);
end: