#OK to post homework 

#Zhizhang Deng, 11/28/2020, Assignment 16



1. 

    p_3(n) = 

          p_3(n - 1) # length 1

        + (n - 1) * p_3(n - 2) # length 2

        + (n - 1)P2 * p_3(n - 3) # length 3



    For the length 3, can be simplified into (n - 1)! / (n - 3)! * p_3(n - 3) 

    = (n - 1) * (n - 2) * p_3(n - 3)



    So 

    p_3(n) = p_3(n - 1) + (n - 1) * p_3(n - 2) + (n - 1) * (n - 2) * p_3(n - 3)



    Convert to plus sign, we have: 

    p_3(n + 3) = p_3(n + 2) + (n + 2) * p_3(n + 1) + (n + 2) * (n + 1) * p_3(n)



    Move 0 to one side we have: 



    -1 * p_3(n + 3) + p_3(n + 2) + (n + 2) * p_3(n + 1) + (n + 2) * (n + 1) * p_3(n) = 0



    Let N be the operator such that Np_3(n) = p_3(n - 1)



    ope(n, N) = -N^3 + N^2 + (n + 2) * N + (n + 1) * (n + 2)



    Order of this recurrence is 3. 



    SeqFromRec(-N^3+N^2+(n+2)*N+(n+1)*(n+2), n, N, [1, 2, 6], 200)[200] = 1235537739494407586650546438672364079145075087043344177939726573885448731683868083543225680429365559313918818143059602933273136821039217983508358005191683227373604250736322487950063766412201151455790542790393051794133976081480109115439664124797121023312920576



3. 

    S6 := proc(n): 

        return add(binomial(n, k) ^ 6, k=0..n)

    end:



    S6seq := proc(N): return [seq(S6(n), n=1..N)]; end:



    # get recurrence 

    rec := Findrec(S6seq(60), n, N, 12)



    # notice that the order of the recurrence is 4, so we use S6seq(4) in our initial condition in SeqFromRec



    S6seqClever := proc(input) local n, N;  return SeqFromRec(Findrec(S6seq(60), n, N, 12), n, N, S6seq(4), input); end;



    time(S6seq(1000)) = 12.352

    time(S6seqClever(1000)) = 0.380