Lecture 7: Due Oct. 4, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment
hw7FirstLast.txt
OK to Post
1)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, 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)Are GFseq(x/(1-x-x^2),x,30) and SeqRec([[1,1],[0,1],30) identical? Why?
	
`	GFseq(x/(1-x-x^2),x,30) and SeqRec([[1,1],[0,1],30) are identical because one uses the  taylor expansion of the generating function to find the answer while the other uses the recurrence function to directly find the answer. Since the generating function is derived from the recurrence function, they result in the same answer.

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)

        [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) 



	for the first 20 coeff of  sum(a(n) * x^n n=0...infinity) = 1/(1-3*x+5*x^2), we get
	1, 3, 4, -3, -29, -72, -71, 147, 796, 1653, 979, -5328, -20879, -35997, -3596, 169197, 525571, 730728, -435671, -4960653, -12703604. 
	This also is satisfying a(n) = 3 *a(n-1) -5 * a(n-2) recurrence relation.