#OK to post homework
#Tianyi Liu, Nov1, Assignment 16

1.
p3(n)=p3(n-1)+(n-1)*p3(n-2)+(n-1)*(n-2)/2*p3(n-3)  p3(0)=1 p3(1)=1 p3(2)=3
ope=N^3-N^2-(n-1)*N-(n-1)*(n-2)/2
Order=3
p3(200)=24835289575723399532387086497978720521502123578390249661745457415171165008792606321759626960707661367018063766519861960100646792912158798656125173033516680149569077377257482825494229763075608562542699143826047784793555688809888035190603776

2.
pk(n)=pk(n-1)+(n-1)*pk(n-2)+binomial(n-1,2)*pk(n-3)....+binomial(n-1,k-1)*pk(n-k)
ope=N^k-N^(k-1)-(n-1)*N^(k-2)+binomial(n-1,2)*N^(k-3)...binomial(n-1,k-1)
Order=k

3.
S6:=proc(n) local k,s:
s:=0:
for k from 0 to n do
 s:=s+binomial(n,k)^6:
od:
s:
end:

S6seq:=proc(N)
seq(S6(n),n=0..N-1):
end:

S6seqClever:=proc(k) local ope,n,N,Ini:
Ini:=[1, 2, 66, 1460]:
ope:=-8*n^3*(6*n-1)*(2*n+1)*(510578*n+701841)*(6*n+1)/((n+2)*(68821*n+89555)*(n+3)^5)+(1/3)*(1220155462*n^7+7630525053*n^6+24102407415*n^5+48083389345*n^4+61153339323*n^3+47245035102*n^2+20060238220*n+3581016180)*N/((n+2)*(68821*n+89555)*(n+3)^5)-(1/3)*(329726969*n^7+4510478951*n^6+25961601810*n^5+81977886100*n^4+153836556389*n^3+171830219751*n^2+105853624100*n+27749509650)*N^2/((n+2)*(68821*n+89555)*(n+3)^5)-(2/3)*(4178086*n^6+56022252*n^5+315184056*n^4+947849628*n^3+1599524688*n^2+1429257735*n+525439145)*N^3/((68821*n+89555)*(n+3)^5)+N^4:

SeqFromRec(ope,n,N,Ini,k):
end:

time(S6seq(1000))
11.343
time(S6seqClever(1000))
.203