# OK to post homework
# Hari Amoor, 10/07/2020, Assignment 7

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

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

# Problem 3

# Start from f(x) = 1/(1-3x+5x^2), as given.
# With some arithmetic transformations, we can see that f(x) = 1+ 3xf(x) - 5x^2f(x).
# Now, consider f(x) as a polynomial, i.e. f(x) = \sum_{i=0}^{n} a_{i}x^{i}.
# By observing the pattern shown here, we can generalize that the coordinates a_{n} are
# equal to 3a_{n-2} - 5a_{n-1}, with a_{0} = 1, a_{1} = 3, and a_{2} = -5.

# Similarly, we start with f(x) = 1/(1 - c_{1}x - c_{2}x^{2} - ... - c_{n}x^{n}) and arrive at
# f(x) = 1 + \sum_{i=1}^{n} c_{i}x^{i} = 1. From this, we can conclude that
# a_{n} = c_{1}*a_{n-1} + ... c_{k}a^{n-k} for some k.