#Ok to post homework
#Tifany Tong, October 4th, 2020, HW #7

# Question 1:
# 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, 1/2, 1/3, 3/8, 11/30, 53/144, 103/280, 
# 2119/5760, 16687/45360, 16481/44800, 1468457/3991680, 16019531/43545600,
# 63633137/172972800, 2467007773/6706022400, 34361893981/93405312000,
# 15549624751/42268262400, 8178130767479/22230464256000, 
# 138547156531409/376610217984000, 92079694567171/250298560512000, 
# 4282366656425369/11640679464960000, 72289643288657479/196503623737344000, 
# 6563440628747948887/17841281393295360000, 39299278806015611311/106826515449937920000, 
# 9923922230666898717143/26976017466662584320000, 79253545592131482810517/215433472824041472000000, 
# 5934505493938805432851513/16131658445064225423360000, 14006262966463963871240459/38072970106357874688000000, 
# 461572649528573755888451011/1254684545727217532928000000, 116167945043852116348068366947/315777214062132212662272000000, 
# 3364864615063302680426807870189/9146650338351415815045120000000]

# Question 2:
# 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]

# GFseq(x/(1-x-x^2),x,30) and SeqRec([[1,1],[0,1]],30) are identical because we proved that generating functions can be used 
# to derive linear recurrences based on the coefficients in the denominator. For (1-x-x^2), we the coefficients are 1 and 1 for 
# x and x^2, which correspond to the parameters we gave in SeqRec([1,1] part of the input).
# We also provided the same first two terms as the generating function, so these two are equivalent. 


# Question 3: We start from f(x) = 1/(1-3x + 5x^2), since this is the generation function we are given. 
# (1-3x+5x^2)*f(x) = 1
# f(x) - 3xf(x) + 5x^2f(x) = 1
# f(x) = 1 + 3xf(x) - 5x^2f(x)
# f(x) = a(0) + a(1)x + a(2)x^2 + a(3)x^3 + .... + a(n)x^n where a(n) is the coefficient of x^n in f(x).
# f(x) = 1 + 3x[a(0) + a(1)x + a(2)x^2 + ... + a(n)x^n] - 5x^2[a(0) + a(1)x + a(2)x^2 + ... + a(n)x^n]
# f(x) = 1 + 3x*a(0) + 3x^2a(1) + 3x^3a(2) + .... + 3x^(n+1)a(n) - 5x^2a(0) - 5x^3a(1) + ... + 5x^(n+2)a(n)
# f(x) = 1 + 3xa(0) - 5x^2a(0) + 3x^2a(1) - 5x^3a(1) + 3x^3a(2)+ ....+ 3x^(n)a(n-1) - 5x^(n)a(n-2) + 3x^(n+1)a(n) - 5x^(n+1)a(n-1) + 5x^(n+2)a(n)
# Now for deriving what a(n), which is the coefficient of x^n in f(x), from the f(x) in the above line, we see the related terms are 3x^n*a(n-1) - 5x^(n)a(n-2). From this, we see the
# coefficient is 3a(n-1) - 5a(n-2). Thus, we've derived that that a(n) = 3a(n-1) - 5a(n-2). 

# ---------------------------------

# We start from f(x) = 1/(1-c1*x - .... - ck*x^k)
# (1-c1*x - ... - ck*^k)*f(x) = 1
# f(x) - c1*x*f(x) - c2*x^2*f(x) - ..... - ck*x^k*f(x) = 1
# f(x) = 1 + c1*x*f(x) + c2*x^2*f(x) + ..... + ck*x^k*f(x) = 1
# Let's denote a(n) as the coefficient of x^n in f(x) where f(x) = a(0) + a(1)x + a(2)x^2 + a(3)x^3 + ... + a(n)*x^n
# f(x) = 1 + c1*x*[a(0) + a(1)x + ... + a(n)x^n] + c2*x^2[a(0) + a(1)x + ... + a(n)*x^n] + .... + c^k*x^k[a(0) + a(1)x + ... + a(n)*x^n)]
# Now let's derive what a(n) is based on the f(x) in the previous line by grouping all the x^n terms together: 
# c1*x^n*a(n-1) + c2*x^n*a(n-2) + c3*x^3*a(n-3) + .... ck * x^n * a(n-k). 
# Now factoring out the x^n, we get: x^n[c1*a(n-1) + c2*a(n-2) + .... + ck*a(n-k)]. 
# c1 * a(n-1) + c2 * a(n-2) + ... + ck * a(n-k) is the coefficient, so we've derived
# that a(n) = c1*a(n-1) + c2*(an-2) + ... + ck*a(n-k)