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



#Given a sequence L of even length,  Finds a linear recurrence
#equation, with constant coefficients of order nops(L)/2
#[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:

if nops(L)<2*n then
 RETURN(FAIL):
fi:


 
rec:=[seq(a[i],i=1..n)]:




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)/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 initial values, finds the description of the sum
#(empirically, YET RIGOROULSLY!)
AddC:=proc(C1,C2) local N,S1,S2,S,C1a,C2a,Sa,TrueOrder:

 if nops(C1) mod 2<>0 or nops(C2) mod 2<>0 then
  ERROR(`Bad input`):
fi:
 

N:=nops(C1)+nops(C2):

C1a:=SeqToCfinite(C1):
C2a:=SeqToCfinite(C2):

S1:=CfiniteToSeq(C1a,N):
S2:=CfiniteToSeq(C2a,N):

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

[op(1..2*TrueOrder,S)]:

end:




#MultC(C1,C2): Given two C-finite sequences in terms of
#their initial values, finds the description of the product
#(empirically, YET RIGOROULSLY!)
MultC:=proc(C1,C2) local N,S1,S2,S,C1a,C2a,Sa,TrueOrder:

 if nops(C1) mod 2<>0 or nops(C2) mod 2<>0 then
  ERROR(`Bad input`):
fi:
 

N:=2*(nops(C1)/2)*(nops(C2)/2):

C1a:=SeqToCfinite(C1):
C2a:=SeqToCfinite(C2):

S1:=CfiniteToSeq(C1a,N):
S2:=CfiniteToSeq(C2a,N):

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

[op(1..2*TrueOrder,S)]:

end:

#JB(Li,K,M,X): inputs a C-finite sequence in Occam's format
#and a pos. integer K, and outputs the set of Justin-Bush-type
#identities of degree <=K, For example
#JB([1,1,2,3],2,0,X) should output Cassini's identity
# [X[1]*X[2]^(-1)-X[1]^0*X[2]^0, [-1,1]]
JB:=proc(Li,K,M,X)
end: