# Kristen Lew, Homework 6
# Exp Math, 2012
# Post if you wish

Help:=proc():  print(`RecToSeq(C,n), Add1(C1,C2), Mult1(C1,C2), BT( C), Tsect(C,t,r) `): 
print(`Old processes:  GuessRec1(L,r), GuessRec(L)`):
end:

### Problem 2
## RecToSeq(C,n): inputs a C-finite sequence and a pos int n and outputs the list
# of length n with the first n terms of the sequence. 
RecToSeq:=proc(C,n) local L, L1, L2, i, j, t:
	L1:=C[2]: L2:=C[1]: t:=nops(L1)+1: 
	for i from t to n do
		L1:=[op(L1), add(-L2[j]*L1[i-j], j=1..t-1)]:
	od:
L1:
end:

### Problem 3
## Add1(C1,C2): inputs two C-finite sequences and outputs a C-finite sequence 
# that describes their sum.
Add1:=proc(C1,C2) local a,b,c,A,B,C:
	a:=nops(C1[1]):
	b:=nops(C2[1]):
	c:=a+b:
	A:=RecToSeq(C1,7*c):
	B:=RecToSeq(C2,7*c):
	C:=A+B:
	GuessRec(C):
end:
		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:

### Problem 4
## Mult1(C1,C2) that inputs two C-finite sequences and outputs the C-finite 
# sequence that is their product.  
Mult1:=proc(C1,C2) local a,b,c,A,B,C:
	a:=nops(C1[1]):
	b:=nops(C2[1]):
	c:=a*b:
	A:=RecToSeq(C1,10*c^2):
	B:=RecToSeq(C2,10*c^2):
	C:=[seq(A[i]*B[i], i=1..10*c^2)]:
	GuessRec(C):
end:

### Problem 5
## BT( C) inputs a C-finite sequence and outputs its Binomial Transform.
BT:=proc( C) local L,B:
	L:=RecToSeq( C, 7*nops( C)):
	B:=[seq(add(binomial(n,i)*L[i+1], i=0..n), n=0..nops( C)-1)]:	
end:


### Problem 6
## Tsect(C,t,r) inputs a C-finite sequence and pos int t, non neg int r ( 0<=t<r)
# 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(t m + r), m=0,1,2,3,4…
Tsect:=proc(C,t,r) local d,a,A:
	d:=nops(C[1]):
	a:=RecToSeq(C,t*(10*d+10)):
	A:=[seq(a[t*m+r+1], m=0..10*d)]:
	GuessRec(A):
end: