> #Weiji Zheng, 09/27/2020, Assignment 7
;
> #OK to post homework
;
> 
;
> #Q1
;
> 
;
> #Codes
;
> Rec:=proc(P,n)  local L, INI,k,i:
> option remember:
> 
> #We first unpack P
> L:=P[1]:
> INI:=P[2]:
> 
> k:=nops(L):
> 
> if nops(INI)<>k then
>  print(INI, `should have`, k, `entries `):
>  RETURN(FAIL):
> fi:
> 
> 
> if n<k then
> #For this case we use the initial condition, since list in Maple start at index 1, we need to access INI[n+1]
>  RETURN(INI[n+1]):
> else
> #We use the definig recurrence
> add(L[i]*Rec(P,n-i),i=1..k):
> fi:
> 
> end:
> SeqRec:=proc(P,N) local n:
> [seq(Rec(P,n),n=0..N)]:
> end:
> GFseq:=proc(f,x,N) local  f1,i:
> f1:=taylor(f,x=0,N+1):
> [seq(coeff(f1,x,i),i=0..N)]:
> end:
> 
;
> GFseq(1/(1-x-x^2-x^3),x,30);
[1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080]
;
> GFseq(1/(1-x+x^2-x^3),x,30);
[1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0]
;
> GFseq(exp(-x)/(1-x),x,30);
[1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I, 1.+0.273949338633639e-115*I]
;
> 
;
> #Q2
;
> 
;
> GFseq(x/(1-x-x^2),x,30)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
;
> SeqRec([[1,1],[0,1]],30)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040]
;
> 
;
> #They are identical. The 2 results are the same. SeqRec([[1,1],[0,1]],30) is the first 31 terms of the sequence "defined by the recurrence
> #x(n)=a1*x(n-1)+ ...+ ak*x(n-k), for n>=k with the INITIAL CONDITIONS x(i)=e_{i} for i=0..k-1", while GFseq(x/(1-x-x^2),x,30) is a sequence of 31 Taylor coefficients of x/(1-x-x^2) staring at 0, which generates the same sequence
;
> 
;
> #Q3
;
> 
;
> #Part 1
;
> 
;
> GFseq(1/(1-3*x+5*x^2),x,30)
[1, 3, 4, -3, -29, -72, -71, 147, 796, 1653, 979, -5328, -20879, -35997, -3596, 169197, 525571, 730728, -435671, -4960653, -12703604, -13307547, 23595379, 137323872, 293994721, 195364803, -883879196, -3628461603, -6465988829, -1255658472, 28562968729]
;
> #Define a(0) = a0, a(1) = a1 for a(n)=3*a(n-1)-5*a(n-2)
;
> #f(x)=a0+a1*x+(3*a(1)-5*a(0))*x^2+(3*a(2)-5*a(1))*x^3+...+(3*a(n-1)-5*a(n-2))*x^n+...
;
> #f(x)=a0+a1*x+3*a(1)*x*x-5*a(0)*x^2+...+(3*a(n-1)*x^(n-1))*x-(5*a(n-2)*x^(n-2))*x^2
;
> #f(x)=a0+a1*x+ 3 * x * (a(1)*x+a(2)*x^2+a(3)*x^3+...) - 5 * x^2 * (a(0) + a(1) * x + a(2) * x^2 +...)
;
> #f(x)=a0+a1*x+ 3*x*(f(x)-a0) - 5*x^2*(f(x))
;
> #(1-3*x+5*x^2)f(x) = POLYNOMIAL OF DEGREE 2=P(x)
;
> #Q(x) = 1-3*x+5*x^2
;
> #Generating function of a(n) Sum(a(n)*x*n, n=0..infinity) = P(x)/(1-2*x-x^2+x^3) satisfies the linear recurrence a(n) = 3*a(n-1)-5*a(n-2)
;
> 
;
> #Part 2
;
> 
;
> #Same as above, we define a(n) = an for n = 0,1,2,...k
;
> #f(x)=a0+a1*x+...+ak*x^k+c1*x*(f(n)-a0-a1-a2-...-ak-1) +c2*x^2*(f(n)-a0-a1-...-ak-2)+...+ck*x^k*f(n)-a0)
;
> #(1-c1*x-... -ck*x^k)f(x) = POLYNOMIAL OF P(x)
;
> #Q(x) = 1-c1*x-... -ck*x^k
;
> #Generating function of a(n) Sum(a(n)*x*n, n=0..infinity) = P(x)/(1-c1*x-... -ck*x^k) satisfies the linear recurrence a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k)
;
> 
;