#OK to post homework
#Tianyi Liu, Oct 4, 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.
#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]

#Yes, they are identical. Both procedures are about fibonacci numbers but presented in different ways. SeqRec uses Rec which get inputs of a second order reocurrence relation and calculate recursively.
#GFseq gets a generating function as input. The input in this case is exactly the function of fibonacci numbers which derives from the recurrence euqation. Then it returns the taylor coefficients of the first 30 terms.
#Hence, they are essentially equivalent.

3.
#f(x)=1/(1-3*x+5*x^2)
#(1-3*x+5*x^2)f(x)=1
#Let a0=1, a1=3,
#f(x)=a0+a1*x+3*x*(f(x)-a0)-5*x^2*f(x)
#f(x)=a0+a1*x+3*x*(a(1)*x+a(2)*x^2...)-5*x^2*(a(0)+a(1)*x...)
#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*a(1)-5*a(0))*x^2+...(3*a(n-1)-5*a(n-2))*x^n
#Hence, a(n)=3*a(n-1)-5*a(n-2)

#f(x)=1/(1-c1*x-... -ck*x^k)
#(1-c1*x-... -ck*x^k)f(x)=1
#Let a0=1,a1=-c1,...a[k-1]=c[k-1]
#f(x)=a0+a1*x...+a[k-1]*x^(k-1)-c1*x*(f(x)-a0)-c2*x^2(f(x)-a1*x-a0)...-ck*x^k*(f(x)-a[k-1]*x^(k-1)...a0)
#f(x)=a0+a1*x...+a[k-1]*x^(k-1)-c1*x*(a(k-1)*x^(k-1)+a(k)*x^k...)-c2*x^2*(a(k-2)*x^(k-2)+a(k-1)*x^(k-1)...)...-ck*x^k*(a(0)+a(1)*x...)
#f(x)=a0+a1*x...+a[k-1]*x^(k-1)+(-c1*a(k-1)*x*x(k-1)-c2*a(k-2)*x^2*x^(k-2)...-ck*a(0)*x^k)...+(-c1*a(n-1)*x*x^(n-1)-c2*a(n-2)*x^2*x^(n-2)...-ck*a(n-k)*x^(n-k)*x^k)
#f(x)=a0+a1*x...+a[k-1]*x^(k-1)+(-c1*a(k-1)-c2*a(k-2)...-ck*a(0))*x^k+(-c1*a(k)-c2*a(k-1)...-ck*a(1))*x^(k+1)...+(-c1*a(n-1)-c2*a(n-2)...-ck*a(n-k))*x^n
#Hence, a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k)