#OK to post homework
#Sam Minkin, 10/04, Assignment 7

Problem 1:

GFseq(1/(1-x-x^2-x^3),x,30);
Ans: [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);
Ans: [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);
Ans: [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]


Problem 2:

According to Maple, they are equal:
evalb(GFseq(x/(-x^2 - x + 1), x, 30) = SeqRec([[1, 1], [0, 1]], 30));
                              true

In SeqRec, we have the first 31 terms (from n=0 to n=30) of the recurrence:
a(n) = a(n-1) + a(n-2), a(0) = 0, a(1) = 1.

The generating function associated to this recursive sequence is:
f(x) = x / (1 - x - x^2), which we derived in class.

This is the same rational function which is inputted into GFSeq. Hence, we would expect that the coefficients of the power series for the given rational function would match the values of the sequence.


Problem 3:

Given the generating function, f(x) = 1/(1 - 3*x + 5*x^2), we want to come up with a recurrence that corresponds to this generating function.

We have that Sum(a(n)*x^n, n=0..infinity) = f(x), so we can find a(0),a(1),a(2),... by finding the Taylor series around x = 0, using GFseq(1/(1 - 3*x + 5*x^2), x, 30).

The first 31 terms are:
[1, 3, 4, -3, -29, -72, -71, 147, 796, 1653, 979, -5328, -20879, -35997, -3596, 169197, 525571, 730728, -435671, -4960653, -12703604, -13307547, 23595379, 137323872, 293994721, 195364803, -883879196, -3628461603, -6465988829, -1255658472, 28562968729]

We see that that these values so far satisfy a(n) = 3*a(n-1) - 5*a(n-2).

Proof that this recurrence generates f(x):

We have, f(x) = Sum(a(n)*x^n, n=0..infinity) = 1 + 3*x + Sum(a(n)*x^n, n=2..infinity) =
1 + 3*x + Sum(3*a(n-1)*x^n, n=2..infinity) - Sum(5*a(n-2)*x^n, n=2..infinity) =
1 + 3*x + 3x*Sum(a(n-1)*x^{n-1}, n=2..infinity) - 5x^2*Sum(a(n-2)*x^{n-2}, n=2..infinity) = 1 + 3x + 3x(f(x) - 1) - 5x^2(f(x)) = 1 + 3xf(x) - 5x^2f(x) = f(x) =>

f(x)(1 - 3*x + 5*x^2) = 1 => f(x) = 1/(1 - 3*x + 5*x^2), as we wanted to show.

In general, if we have:
f(x) = 1/(1-c1*x-...-ck*x^k) = Sum(a(n)*x^n, n=0..infinity).
Then, the sequence a(n)=c1*a(n-1) + c2*a(n-2) + ... + ck*a(n-k) should be associated to this generating function.

Proof:

f(x) = Sum(a(n)*x^n, n=0..infinity) = e_0 + e_1 + e_2 + ... + e_{k-1} + Sum(a(n)*x^n, n=k..infinity) = e_0 + e_1 + e_2 + ... + e_{k-1} + Sum(c1*a(n-1)*x^n, x=k..infinity) + Sum(c2*a(n-2)*x^n, x=k..infinity) + ... + Sum(ck*a(n-k)*x^n, x=k..infinity) =
e_0 + e_1 + e_2 + ... + e_{k-1} + c1*x*Sum(a(n-1)*x^{n-1}, n=k..infinity) + c2*x^2*Sum(a(n-2)*x^{n-2}, n=k..infinity) + ... + ck*x^k*Sum(a(n-k)*x^{n-k}, n=k..infinity) =>
f(x) = e_0 + e_1 + e_2 + ... + e_{k-1} + c1*x*(f(x) - a(k-2)*x^{k-2} - a(k-3)*x^{k-3} - ... - a(0)) + c2*x^2*(f(x) - a(k-3)*x^{k-3} - a(k-4)*x^{k-4} - ... - a(0)) + ... + ck*x^k*f(x) =>

f(x) = 1 + c1 + c1^2 + c2 + c1*c2 + c3 - (-c1^2 - c2)*c1, c1*c3 - (-c1^2 - c2)*c2 - (-c1^3 - 2*c1*c2 - c3)*c1 + ... + c1*x*(f(x) - a(k-2)*x^{k-2} - a(k-3)*x^{k-3} - ... - a(0)) + c2*x^2*(f(x) - a(k-3)*x^{k-3} - a(k-4)*x^{k-4} - ... - a(0)) + ... + ck*x^k*f(x) =>

f(x) = 1 + c1*x*f(x) + c2*x^2*f(x) + c3*x^3*f(x) + ... + ck*x^k*f(x) =>
f(x)*(1 - c1*x - ... - ck*x^k) = 1 =>
f(x) = 1 / (1 - c1*x - ... - ck*x^k), as we desired to show.