#!/usr/local/bin/maple
# -*- maplev -*-

# Nathaniel Shar
# HW 6
# Experimental Mathematics

# It is okay to link to this assignment on the course webpage.

# Stuff from class 6:

# Guesses homogeneous linear recurrence of the specified order with
# constant coefficients for the sequence L.
# L(n) + c_1L(n-1) + ... + c_rL(n-r) = 0.
# Output:
# [[c_1, c_2, ..., c_r], InitialConditions]

Help := proc(): print(`GuessRec1(L, order), GuessRec(L), RecToSeq(seq, n), Add1(C1, C2), Mult1(C1, C2), BT(C), Tsect(C, t, r)`):

GuessRec1 := proc(L, order) local eqns, c, vars:
    if (nops(L) < 2*order+4) then return FAIL: fi:
    eqns := [seq(L[n] + sum(c[i]*L[n-i], i=1..order), n=order+1..nops(L))]:
    vars := solve(eqns):
    if (vars = NULL) then return FAIL: fi:
    [subs(vars, [seq(c[i], i=1..order)]), L[1..order]]:
end:

# Guesses homogeneous linear recurrence of the smallest possible order with
# constant coefficients for the sequence L.
# L(n) + c_1L(n-1) + ... + c_rL(n-r) = 0.
# Output:
# [[c_1, c_2, ..., c_r], InitialConditions]
GuessRec := proc(L) local i, answer:
    for i from 1 to floor((nops(L)-4)/2) do:
        answer := GuessRec1(L, i):
        if answer <> FAIL then: break: fi:
    od:
    return answer:
end:

#############
# Problem 2 #
#############

RecToSeq := proc(Seq, n) local ini, co, out, i, j:
    ini := Seq[2]:
    co := Seq[1]:
    out := ini:
    for i from nops(ini)+1 to n do:
        out := [op(out), add(-co[j]*out[i-j], j=1..nops(co))]:
    od:
    return out:
end:

#############
# Problem 3 #
#############

Add1 := proc(C1, C2) local L1, L2:
    L1 := RecToSeq(C1, 2*nops(C1[1]) + 2*nops(C2[1]) + 7):
    L2 := RecToSeq(C2, 2*nops(C1[1]) + 2*nops(C2[1]) + 7):
    GuessRec(L1 + L2):
end:

#############
# Problem 4 #
#############

Mult1 := proc(C1, C2) local L1, L2:
    L1 := RecToSeq(C1, 2*nops(C1[1]) + 2*nops(C2[1]) + 7):
    L2 := RecToSeq(C2, 2*nops(C1[1]) + 2*nops(C2[1]) + 7):
    GuessRec([seq(L1[i]*L2[i], i=1..nops(L1))]):
end:

#############
# Problem 5 #
#############

BT := proc(C) local L, BTL:
    L := RecToSeq(C, 2*nops(C[1]) + 4):
    BTL := [seq(add(L[i]*binomial(n,i), i=1..n), n=1..nops(L))]:
    GuessRec(BTL):
end:

#############
# Problem 6 #
#############

Tsect := proc(C, t, r) local L:
    if not(t > 0 and r >= 0 and r < t) then:
        FAIL:
    else:
        L := RecToSeq(C, r + 4*t + 2*t*nops(C[1])):
        GuessRec([seq(L[t*i+r], i=0..2*nops(C[1]) + 4)]):
    fi:
end: