#OK to post
# Soham Palande, Assignment 7, 10/04/2020





#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]

# Yes the sequences are identical because both the functions return the first N+1 terms corresponding
# to the Taylor coefficients of the input function 
# In this case the input functions to GFseq and SeqRec are identical since [[1,1],[0,1]] is a compact
# form of denoting x/(1-x-x^2). In, [[c1,c2],[i1,i2]], c1 and c2 denote the coefficients of the 
# c-recursive function of the form 1-c1x-c2x^2-...ckx^k and i1,i2 denote the initial values of the 
# function at x=0, x=1.


#PART 3


# Let a(n) in terms of the generating function 
# Sum(a(n)*x^n, n=0..infinity) = 1/(1-3*x+5*x^2)

# Looking at the coefficients of the first n+1 terms of the Taylor series expansion (around x=0) of
# 1/(1-3*x+5*x^2, we get 

seq(coeff(taylor(1/(1-3*x+5*x^2),x=0,n+1),x,n),n=0..20)
	1, 3, 4, -3, -29, -72, -71, 147, 796, 1653, 979, -5328, -20879, -35997, -3596, 169197, 	525571, 730728, -435671, -4960653, -12703604


# This sequence satisfies the recurrence relation a(n)=3a(n-1)-5a(n-2)
# 



#PART 4

# d(n)=n*d(n-1)+(-1)^(n-1), with initial condition d(0)=1
# f(x)=Sum( ( d(n)/n! ) *x^n , n=0..infinity)
# Expanding f(x)
# f(x) = (d(0)/0!) + (d(1)/1!)x + (d(2)/2!)x^2 + (d(3)/3!)x^3 +...+ (d(n)/n!)x^n + ...
#      = 1 + [(1*d(0)+(-1)^(0))/1!]x + [(2*d(1)+(-1)^(1))/2!]x^2 + [(3*d(2)+(-1)^(2))/3!]x^3 + ...
#      = 1 + [d(0)x/1!] + [x/1!] + [2d(1)x^2/2!] - [x^2/2!] + [3d(2)x^3/3!] + [x^3/3!] +...
#      = 1 - [(e^(-x)-1) - [d(0)x/1!] - [2d(1)x^2/2!] - [3d(2)x^3/3!] - ...]        (using the taylor series expansion of e^-x)
#      = 1 - [(e^(-x)-1) - x[[d(0)/1!] + [2d(1)x/2!] + [3d(2)x^2/3!] + ...]]    (factoring out x)
#      = 1 - [(e^(-x)-1) - x[f(x)]]
# f(x) = 1 - e^-x + 1 + xf(x) 
# f(x) = [2 - e^(-x)] / (1-x)


#COMMENT FROM Dr. Z. : RIGHT WAY, BUT SOMETHING WENT WRONG, THE ANSWER IS exp(-x)/(1-x)