#OK to post homework 
#Zhizhang Deng, 09/29/2020, Assignment 7
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]

2. Yes they are identical. Because SeqRec is trying to get a sequence from the recursive formula f(n)=f(n-1)+f(n-2). with the initial condition of f(0)=0, f(1)=1 While the GFseq is trying to get the sequence from the generating function which is generating the same sequence.

3. 
1). 
By expanding the generating functions using taylor, we can see that a[0]=1, a[1]=3, a[2]=4. 
let f be the generating function of a[n]. 
f(x)=a[0] + a[1]x + a[2]x^2 + a[3]x^3 ... +a[n]x^n
Because of the existence of a[n] = 3*a[n-1]-5*a[n-2], we can change f(x) into following
f(x)=a[0] + a[1]x + (3*a[1] - 5 * a[0])x^2 + (3*a[2] - 5 * a[1])x^3 + ... 
f(x)=a[0] + a[1]x + x*( 3*a[1]*x - 5*a[0]*x + 3*a[2]x^2 - 5 * a[1]x^2 + ... )
grouping 3* and 5 * x then we get
f(x)=a[0] + a[1]x + x*( 3*(a[1]*x + a[2]*x^2 + a[3]*x^3...) - 5*x(a[0] + a[1]*x + a[2]*x^2...) )
f(x)=a[0] + a[1]x + x*( 3*(f(x) - a[0]) - 5*x*(f(x))    #### QUESTION????? why this is f(x)-a[0] instead of f(x)-a[0]-a[n]*x^n ??? The last term is missing though. 
replacing a[0], a[1] with initial condition, we have 
f(x) = 1 + 3x + x*(3*(f(x) - 1) - 5x*f(x))
f(x) = 1 + 3x + x*(3f(x)-3-5x*f(x))
f(x) = 1 + 3x + 3xf(x)-3x-5x^2f(x)
simplify we have f(x)=1/(5x^2-3x+1) which is the same as the original generating function

2). 
let f be the generating function of a[n]. 
f(x) = a[0] + a[1]x + a[2]x^2 + a[3]x^3 + ... 
starting from kth term [0-index], we can use the recurrence relation a[n] = c1*a[n-1]+c2*a[n-2]... to expand the equation

f(x) = a[0] + a[1]x + ... + (c1*a[n-1] + c2*a[n-2] + c3*a[n-3] + ... + ck*a[n-k])x^k + ...
starting from the term that got expanded, we can further group c1, c2, c3 ... 
f(x) = a[0] + a[1]x + ... + (c1*(a[k - 1]x^(k-1) + a[k]x^k + ...) + ...+ ck*x(a[0] + ...)
f(x) = a[0] + a[1]x + ... + c1 * (f(x) - (a[0] + a[1]x + ... a[k - 2]x^(k-2)) + c2 * (f(x) - (a[0] + a[1]x + ... a[k - 1]x^(k-1)) + ... ck * f(x))
f(x) = a[0] + a[1]x + ... a[k - 1]x^(k - 1) + c1 * f(x) - c1*(a[0] + a[1]x + ... a[k - 2]x^(k-2)) + c2*f(x) - c2*(a[0] + a[1]x + ... a[k - 3]x^(k-3)) + ck*f(x) - ck * (a[0] + a[1] + ... a[k - (k + 1)])
f(x) - c1*f(x) - c2*f(x) - .. ck*f(x) = a[0] + a[1]x + ... a[k - 1]x ^ (k - 1) - c1*(a[0] + a[1]x + ... a[k - 1]x^(k -2)) - ... 

// NOT SUREHOW TO PROCEED AFTER THIS, but it has a similar pattern as above. 
But this should be able to simplify