Help:=proc(): print(`SeqToCfinite1(L,n), SeqToCfinite(L) `): 
print(`CfiniteToSeq([C1,D1],N), AddC(C1,C2), MulC(C1,C2) `):
end:



#Given a sequence L, tries to find a linear recurrence
#equation, with constant coefficients if order n
#satisfying it followed by the L initial conditions
#[op(1..n,L)]; the linear reruccence 
#f(x)=a1*f(x-1)+ a2*f(x-2)+ ...+ an*f(x-n) is represneted
#by [a1,a2, ..., an]. [rec,initila]
#For example, the Fibonacci sequence
#is represented by [[1,1],[1,1]];
#the Lucas sequence is represented by [[1,1],[1,3]]
SeqToCfinite1:=proc(L,n) local rec,a,i,eq,var,sol:
rec:=[seq(a[i],i=1..n)]:

if nops(L)<2*n+4 then
 print(`Insufficient data`):
 RETURN(FAIL):
fi:


var:=convert(rec,set):

eq:={seq(L[x]=add(a[i]*L[x-i],i=1..n),x=n+1..nops(L))};


sol:=solve(eq,var):

if sol=NULL then
  RETURN(FAIL):
fi:

[subs(sol,rec),[op(1..n,L)]];

end:



#Given a sequence L, tries to find a linear recurrence
#equation, with constant coefficients of least possible order
#satisfying it followed by the L initial conditions
#[op(1..n,L)]; the linear reruccence 
#f(x)=a1*f(x-1)+ a2*f(x-2)+ ...+ an*f(x-n) is represneted
#by [a1,a2, ..., an]. [rec,initila]
#For example, the Fibonacci sequence
#is represented by [[1,1],[1,1]];
#the Lucas sequence is represented by [[1,1],[1,3]]
SeqToCfinite:=proc(L) local n,P:

for n from 1 to trunc((nops(L)-4)/2) do

 P:=SeqToCfinite1(L,n):
 
  if P<>FAIL then
      RETURN(P):
  fi:
od:

FAIL:

end:


#CfiniteToSeq(C,N): Given a C-finite sequence in the
#format C=[C1,D1] where C1 is [c1,c2, ..., ck] 
#indicating that our sequence solves the
#recurrence
#a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k)
#and D1 are the initial conditions
#D1=[a(1),... , a(k)] outputs the first
#N terms of that sequence

CfiniteToSeq:=proc(C,N) local C1,D1,L,n,newguy,i:
C1:=C[1]: D1:=C[2]:

L:=D1:

for n from nops(D1)+1 to N do
newguy:=add(C1[i]*L[n-i],i=1..nops(C1)):


L:=[op(L),newguy]:

od:

L:

end:


#AddC(C1,C2): Given two C-finite sequences in terms of
#their descriptions, finds the description of the sum
#(empirically)
AddC:=proc(C1,C2) local N,S1,S2,S:

if nops(C1[1])<>nops(C1[2]) or nops(C2[1])<>nops(C2[2]) then
  ERROR(`Bad input`):
fi:
 

N:=2*(nops(C1[1])+nops(C2[1]))+8:

S1:=CfiniteToSeq(C1,N):
S2:=CfiniteToSeq(C2,N):

S:=[seq(S1[i]+S2[i],i=1..N)]:

SeqToCfinite(S):

end:


#MulC(C1,C2): Given two C-finite sequences in terms of
#their descriptions, finds the description of the sum
#(empirically)
MulC:=proc(C1,C2) local N,S1,S2,S:

if nops(C1[1])<>nops(C1[2]) or nops(C2[1])<>nops(C2[2]) then
  ERROR(`Bad input`):
fi:
 

N:=2*(nops(C1[1])*nops(C2[1]))+8:

S1:=CfiniteToSeq(C1,N):
S2:=CfiniteToSeq(C2,N):

S:=[seq(S1[i]*S2[i],i=1..N)]:

SeqToCfinite(S):

end: