#OK to post
#Michael Yen, 10/4/20, Assignment 7

#1. Examine the Maple code of
#Maple code for Lecture 7.
#especially the last procedures that I did not have a chance to discuss,
#GFseq(f,x,N)
#What are

#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,7555476,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.Are GFseq(x/(1-x-x^2),x,30) and SeqRec([[1,1],[0,1],30) identical? Why?
#Yes. The first one uses the generating function of the Fibonacci sequence and the second one uses the recurrence
#x(n)=1*x(n-1)+1*x(n-2) for initial conditions x(0)=0 and x(1)=1 which also the Fibonacci sequence

#3.In the lecture we started with a sequence that is known to satisfy a linear recurrence equation with constant 
#coefficients and showed how to derive an explicit expression for the generating function
#Sum(a(n)*x^n, n=0..infinity)
#as a certain rational function whose denominator ONLY depends on the coefficients of the recurrence (c1,c2,..., ck) 
#and whose numerator also depends on the initial conditions. Show how to go the other way.

#Define a(n) In terms of the generating function
#Sum(a(n)*x^n, n=0..infinity) = 1/(1-3*x+5*x^2)
#In other words a(n) is the coefficient of x^n in the Taylor expansion (around x=0) of 1/(1-3*x+5*x^2)
#[In Maple, you can do coeff(taylor(1/(1-3*x+5*x^2),x=0,n+1),x,n) to compute it.]
#Prove that the sequence a(n) satisfies the linear recurrence
#a(n)=3*a(n-1)-5*a(n-2)

#1 = (1-3*x+5*x^2) * (a(0)*x^0+a(1)*x^1+a(2)*x^2+...+a(n)*x^n+...)
#  = (a(0)*x^0-3*a(0)*x+5*a(0)*x^2) + (a(1)*x^1-3*a(1)*x^2+5*a(1)*x^3) + (a(2)*x^2-3*a(2)*x^3+5*a(2)*x^4) + (a(3)*x^3-3*a(2)*x^4+5*a(1)*x^5) + ... + a(n)*x^n-3*a(n)*x^(n+1)+5*a(n)*x^(n+2)
#  = a(0) + (a(1)-3*a(0))*x + (a(2)-3*a(1)+5*a(0))*x^2 + ... + (a(n)-3*a(n-1)+5*a(n-2)) * x^n

#a(0)=1
#a(n) (a(n)-3*a(n-1)+5*a(n-2))=0 a(n)=3*a(n-1)-5*a(n-2) n>=1

#[Typo corrected Oct. 2, 2020, spotted by Tifany Tong who won a dollar.]

#More generally, prove that for any numbers c1, c2, ..., ck, if you define a(n) In terms of the generating function
#Sum(a(n)*x^n, n=0..infinity) = 1/(1-c1*x-... -ck*x^k)
#In other words a(n) is the coefficient of x^n in the Taylor expansion (around x=0) of 1/(1-c1*x-...-ck*x^k)
#Prove that the sequence a(n) satisfies the linear recurrence
#a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k)

# 1 = (a(0)*x^0+a(1)*x^1+a(2)*x^2+...+a(n)*x^n)(1-c1*x-c2*x^2-...-ck*x^k)
# 1 = (a(0)*x^0-c1*a(0)*x^1-...-ck*a(0)*x^k) + (a(1)*x^1-c1*a(1)*x^2-...-ck*a(1)*x^(k+1)) + (a(2)*x^2-c1*a(2)*x^3-...-ck*a(2)*x^(k+2)) + ... + (a(n)*x^n-c1*a(n)*x^n+1-...-ck*a(n)*x^(k+n) + ...
# 1 = a(0) + (a(1)-c1*a(0))*x^1 + (a(2)-c1*a(1)-c2*a(0))*x^2 + ... + (a(n)-c1*a(n-1)-c2*a(n-2)-...-ck*a(n-k))*x^n

#a(n)-c1*a(n-1)-c2*a(n-2)-...-ck*a(n-k)=0   (When n is greater than k)
#a(n)=c1*a(n-1)+c2*a(n-2)+...+ck*a(n-k)