#OK to post homework
#William Wang, 9/27/2020, Assignment 7

#1.
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/(-x^3 - x^2 - x + 1), 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/(-x^3 + x^2 - x + 1), 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  1  3  11  53   103  2119  16687  16481  1468457  
[1, 0, -, -, -, --, ---, ---, ----, -----, -----, -------, 
[      2  3  8  30  144  280  5760  45360  44800  3991680  

  16019531  63633137   2467007773  34361893981  15549624751  
  --------, ---------, ----------, -----------, -----------, 
  43545600  172972800  6706022400  93405312000  42268262400  

  8178130767479   138547156531409  92079694567171   
  --------------, ---------------, ---------------, 
  22230464256000  376610217984000  250298560512000  

  4282366656425369   72289643288657479   6563440628747948887   
  -----------------, ------------------, --------------------, 
  11640679464960000  196503623737344000  17841281393295360000  

  39299278806015611311   9923922230666898717143   
  ---------------------, -----------------------, 
  106826515449937920000  26976017466662584320000  

  79253545592131482810517   5934505493938805432851513   
  ------------------------, --------------------------, 
  215433472824041472000000  16131658445064225423360000  

  14006262966463963871240459  461572649528573755888451011   
  --------------------------, ----------------------------, 
  38072970106357874688000000  1254684545727217532928000000  

  116167945043852116348068366947  3364864615063302680426807870189
  ------------------------------, -------------------------------
  315777214062132212662272000000  9146650338351415815045120000000

  ]
  ]
  ]





#2.
GFseq(x/(-x^2 - x + 1), 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]


with(combinat):

Rec := proc(P, n) local L, INI, k, i:
option remember:
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
 RETURN(INI[n + 1]):
else
 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:

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]

#Yes, GFseq(x/(1-x-x^2),x,30) and SeqRec([[1,1],[0,1]],30) are identical because (x/(1-x-x^(2))) is the generating function for a(n)=a(n-1)+a(n-2), with initial conditions a(0)=0 and a(1)=1.





#3.
#f := x -> 1/(1 - 3*x + 5*x^2)
#(1-3x+5x`^(2))f(x)=1
#f(x)-3x*f(x)+5x`^2*f(x) = 1
#1(a(0)+a(1)*x+a(2)*x^(2)+...)-3 x(a(0)+a(1)*x+a(2)*x^(2)+...)+5 x^(2)(a(0)+a(1)*x+a(2)*x^(2)+...)=1
#(a(0)+a(1)*x+a(2)*x^(2)+...)-(3 x* a(0)+3 x^(2)* a(1)+3 x^(3)* a(2)+...)+(5 x^(2)* a(0)+5 x^(3)* a(1)+5 x^(4)* a(2)+...)=1
#Line up the terms correctly, factor, and you get
#a(0)+x(a(1)-3a(0))+x^(2)(a(2)-3 a(1)+5 a(0))+...=1
#A very visible pattern is here:
#a(n) - 3*a(n - 1) + 5*a(n - 2) = 0, 2 <= n, with initial conditions a(0) = 0, a(1) = 1 + 3*a(0) = 1

#Let's program it!
a := proc(n) option remember:
if n = 0 then 0:
elif n = 1 then 1:
else 3*a(n - 1) - 5*a(n - 2):
fi:
end:

[seq(a(i), i = 1 .. 101)]:
[seq(coeff(taylor(1/(5*x^2 - 3*x + 1), x = 0, 101), x, i), i = 0 .. 100)]:
evalb(% = %%);
                              true
#Hence, we have proven that the sequence a(n) satisfies the linear recurrence a(n) = 3*a(n-1)-5*a(n-2)

#Prove for any numbers c1,c2,...,ck, if a(n) is defined in terms of the generating function Sum(a(n)*x^(n), n=0..infinity)=1/((1-c1*x-...-ck*x^(k))), then the sequence a(n) satisfies the linear recurrence a(n)=c1*a(n-1)+c2*a(n-2)+...+ck*a(n-k)

#f(x)=1/((1-c1*x-...-ck*x^(k)))
#(1-c1*x-...-ck*x^(k))f(x)=1
#f(x)-c1*x*f(x)-...-ck*x^k*f(x) = 1
#(a(0)+a(1)*x+a(2)*x^(2)+...)-c1*x(a(0)+a(1)*x+a(2)*x^(2)+...)-...-ck*x^(k)(a(0)+a(1)*x+a(2)*x^(2)+...)=1
#(a(0)+a(1)*x+a(2)*x^(2)+...)-(c1*x*a(0)+c1*x^(2)*a(1)+c1*x^(3)*a(2)+...)-...-(ck*x^(k)*a(0)+ck*x^(k+1)a(1)+ck*x^(k+2)a(2)+...)=1
#Line up the terms correctly, factor, and you get
#a(0)+x(a(1)-c1*a(0))+x^(2)(a(2)-c1*a(1)-c2*a(0))+x^(3)(a(3)-c1*a(2)-c2*a(1)-c3*a(0))+x^(4)(a(4)-c1*a(3)-c2*a(2)-c3*a(1)-c4*a(0))+...+x^(n)(a(n)-c1*a(n-1)-c2*a(n-2)-...-ck*a(n-k)) = 1
#Thus,
#a(n) satisifes the linear recurrence a(n) = c1*a(n-1)+c2*a(n-2)+...+ck*a(n-k).