#OK to post homework
#Karnaa Mistry, 10/04/20, Assignment HW #7

with(combinat):


# 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.  They both output the first 31 elements of the Fibonacci sequence.  By the definition of
# Rec(P,n), SeqRec([[1,1],[0,1]],30) gives the first 31 elements of the sequence directly.  As for GFseq(x/(1-x-x^2),x,30),
# this uses the generating function for the Fibonacci sequence, f(x) = x/(1-x-x^2).  By definition, the generating function
# for a sequence is the power series sum(n=0 to infinity) of (a_n * x^n).  For n >= 0, we know that the generating function
# for the Fibonacci sequence is sum(n=0 to infinity) of (F_n * x^n).  Taking out the first two terms, we have the sum(n=2 to
# infinity) of (F_(n-1)x^n) + sum(n=2 to infinity) of (F_(n-2)x^n).  By taking out the 2nd term of the first sum and the
# 1st and 2nd terms of the second sum, we can arrive at x + x(sum(n=1 to infinity) of (F_n*x^n)) + x^2(sum(n=0 to infinity).
# Since the first term is 0, we can substitute f(x) for both of these sums and arrive at x + x*f(x) + x^2*f(x) = f(x), from
# our initial expression.  We arrive at the known generating function fot the Fibonacci sequence, f(x) = x/(1-x-x^2).




# 3.

# 	a)

# Let a(n) be the sequence defined by the generating function f(x) = Sum(a(n)*x^n, n=0..infinity) = 1/(1-3*x+5*x^2)

# Prove that a(n) satisfies the linear recurrence a(n)=3*a(n-1)-5*a(n-2)

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

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

# (a(0) + a(1)*x + a(2)*x^2 + ... + a(n)*x^n)*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)) = 1

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

# 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 + ...

# a(0) = 1; a(1)-3*a(0) = 1 --> a(1) = 4;  -->  a(n) = 3*a(n-1) - 5*a(n-2) for all n >= 2

#	b)

# Let a(n) be the sequence defined by the generating function f(x) = Sum(a(n)*x^n, n=0..infinity) = 1/(1-c1*x-... -ck*x^k)

# Prove that a(n) satisfies the linear recurrence a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k)

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

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

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

# a(0) + a(1)*x + a(2)*x^2 + ... + a(n)*x^n - c1*xa(0) - c1*x^2a(1) - ... - c1*x^(n+1)a(n) - ...
#	- ckx^ka(0) - ckx^(k+1)a(1) - ... - ckx^(n+k)a(n) = 1

# 1 = a(0) + (a(1) - c1*a(0))*x + (a(2)-c1a(1)-c2a(0))x^2 + ... + (a(n)-c1a(n-1)-c2a(n-2)-...-cka(n-k))*x^n + ...

# a(0) = 1; a(1) - c1*a(0) = 1 --> a(1) = 1+c1; a(2) - c1*a(1) - c2*a(0) = 1 --> a(2) = 1+c1+(c1)^2+c2; etc.

# Since we reach the recurrence pattern, a(n) does satisfy the recurrence: a(n)=c1*a(n-1)+c2*a(n-2)+ ... + ck*a(n-k)




# 4. (Optional) [partial / attempt]

# The Taylor expansion of exp(-x) about 0 is = Sum(((-1)^n * x^n / n!),n=0 to infinity).  

# We already found d(n) = n*d(n-1)+(-1)^(n-1), d(0)=1; we want to achieve f(x)=Sum( (d(n)/n!)*x^n, n=0..infinity )

# f(x) = d(0) + d(1)*x + d(2)*x^2 + ...
# f(x) = 1 + 1*d(0)*x^1+x^1 + 2*d(1)*x^2-x^2 + ... 
# f(x) = 1 + x(d(0)+1 + 2*d(1)*x-x + ...)

# Pulling out 1-x+x^2-x^3+... would give f(x) = 1 + x*Taylor(exp(-x))*d(0) + 2*d(1)*x + 3*d(2)*x^2 + ...)

# After moving the x^n*(-1)^(n-1) out of the expression and into the partial Taylor expansion of e^(-x), I am
# unsure how the partial expansion  plays into having exp(-x) be a part of the final generating function.  We
# also get d(n-1)+(-1)^(n-1)/(n-1)!, so maybe this works into the (n-1)th term of a Taylor expansion of exp(-x),
# and might help because of the *x we have outside of our Taylor expression, making x^(n-1)*x give x^n...