#OK to post homework
#Kent Mei, 10/4/20, Assignment 7

#---------------------------------
#Part 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]
#---------------------------------
#Part 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) = SeqRec([[1,1],[0,1]],30) because they both define the same recurrence relation, specifically the Fibonacci sequence. SeqRec([[1,1],[0,1]],30) represents the first 30 terms of the recurrence relation defined by a(n) = a(n-1) + a(n-2) with a(0) = 0 and a(1) = 1. Meanwhile, it can be shown that x/(1-x-x^2) is the generating function of the sequence defined by SeqRec([[1,1],[0,1]],30). 

#f(x) = a(0) + a(1)x +        a(2)x^2 +        a(3)x^3 + ... +            a(n)x^n + ...
#f(x) = a(0) + a(1)x + (a(0)+a(1))x^2 + (a(1)+a(2))x^3 + ... + (a(n-2)+a(n-1))x^n + ...
#f(x) = a(0) + a(1)x + x^2(a(0) + a(1)x + a(2)x^2 + ...) + x(a(1)x + a(2)x^2 + a(3)x^3 + ...)
#f(x) = a(0) + a(1)x + x^2(f(x)) + x(f(x) - a(0))
#f(x) = 0 + x + (x^2 + x)f(x)
#(1 - x - x^2)f(x) = x
#f(x) = x/(1-x-x^2) as desired. 

#Since f(x) is the generating function of the sequence, the coefficients of the terms of the taylor series of this function must follow the recurrence relation defined above.


#---------------------------------
#Part 3

#We wish to show how to go from a generating function to a sequence that solves a linear recurrence equation with constant coefficients.
#First, we define a(n) in terms of the generating function:
#Sum(a(n)*x^n, n=0..infinity) = 1/(1-3*x+5*x^2).
#Note: This implies that a(n) is the coefficient of the of x^n in the Taylor expansion (around x=0) of 1/(1-3*x+5*x^2).
#Let f(x) = 1/(1-3*x+5*x^2).
#(1-3*x+5*x^2)f(x) = 1
#(1-3*x+5*x^2)(a(0) + a(1)x + a(2)x^2 + ... + a(n)x^n + ...) = 1
#a(0) + (a(1) -3a(0))x + (a(2) -3a(1) + 5a(0))x^2 + ... + (a(n) -3a(n-1) + 5a(n-2))x^n  + ... = 1
#(a(0) - 1) + (a(1) - 3a(0))x + (a(2) -3a(1) + 5a(0))x^2 + ... + (a(n) -3a(n-1) + 5a(n-2))x^n = 0
#Notice there are no terms with degree 2 or greater on the right side.
#That means a(n) - 3a(n-1) + 5a(n-2) = 0 for all n >= 2.
#This implies that a(n) = 3a(n-1)-5a(n-2) as desired.

#Now, we define a(n) in terms of the generating function:
#Sum(a(n)*x^n, n=0..infinity) = 1/(1-c1*x-... -ck*x^k)
#We wish to prove that a(n) satisfies the linear recurrence a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k).
#Let f(x) = 1/(1-c1*x-... -ck*x^k)
#(1-c1*x-... -ck*x^k)f(x) = 1
#(1-c1*x-... -ck*x^k)(a(0) + a(1)x + a(2)x^2 + ... + a(n)x^n + ...) = 1
#a(0) + (a(1) - c1a(0))x + (a(2) - c1a(1) - c2a(0))x^2 + ... + (a(k) - c1a(k-1) - ... - cka(0))x^k + ... + (a(n) - c1a(n-1) - ... - cka(n-k))x^n = 1
#(a(0) - 1) + (a(1) - c1a(0))x + (a(2) - c1a(1) - c2a(0))x^2 + ... + (a(k) - c1a(k-1) - ... - cka(0))x^k + ... + (a(n) - c1a(n-1) - ... - cka(n-k))x^n = 0
#Notice there are no terms with degree k or greater on the right side.
#That means a(n) - c1a(n-1) - ... - cka(n-k) = 0 for all n >= k
#This implies that a(n) = c1a(n-1) + c2a(n-2) + ... + cka(n-k) as desired.


#---------------------------------
#Part 4

#d(n)=n*d(n-1)+(-1)^n with d(0) = 1
#We wish to find an explicit expression for the exponential generating function f(x) = Sum((d(n)/n!) * x^n, n = 0..infinity)

#f(x) = d(0)/0! + d(1)x/1! + d(2)x^2/2! + ... + d(n)x^n/n! + ...
#f(x) = d(0)/0! + (d(0)-1)x/1! + (2*d(1)+1)x^2/2! + ... + (n*d(n-1)+(-1)^n)x^n/n! + ...
#f(x) = d(0)/0! + (d(0)x/1! + 2d(1)x^2/2! + ... + nd(n-1)x^n/n! + ...)     + (-x/1! + x^2/2! - x^3/3! + ... + (-1)^nx^n/n! + ...)
#f(x) = d(0)/0! + (d(0)x/0! + (d(1)x^2/1! + ... + (d(n-1)x^n/(n-1)! + ...) + (-x/1! + x^2/2! - x^3/3! + ... + (-1)^nx^n/n! + ...)
#f(x) = d(0)/0! + x(d(0)/0! + d(1)x/1! + d(2)x^2/2! + ... + d(n)x^n/n! + ...) + (exp(-x) - 1)
#f(x) = 1       + x(f(x)) + (exp(-x) - 1)
#(1-x)f(x) = exp(-x)
#f(x) = exp(-x)/(1-x).