# Matthew Russell # Experimental Math # Homework 6 # I give permission to post this. # Write a procedure RecToSeq(C,n) that inputs a C-finite sequence, # in our notation, and a pos. integer n, and outputs the list of # length n with the first n terms of the sequence. For example, # RecToSeq([[-1,-1],[1,1]],10); # Should output # [1,1,2,3,5,8,13,21,34,55] . RecToSeq:=proc(C,n) local rec, init, l, L, i, j: rec:=C[1]: init:=C[2]: l:=nops(rec): L:=[op(init)]: for i from l+1 to n do L:=[op(L),-add(rec[j]*L[i-j],j=1..l)]: od: return L: end: ######################################################################### # Using the fact that the sum of two C-finite sequences of orders a and b # is a is C-finite sequence of order ≤ a+b, use procedure RecToSeq to write # a procedure Add1(C1,C2) that inputs two C-finite sequences in our notation # and outputs a C-finite sequence that describes their sum. In our notation. # For example # Add1([[-1],[1]],[[-2],[1]]); # should output # [[-3,2],[3,5]] Add1:=proc(C1,C2) local ord1, ord2, ord, L1, L2: ord1:=nops(C1[1]): ord2:=nops(C2[1]): ord:=2*(ord1+ord2)+8: L1:=RecToSeq(C1,ord): L2:=RecToSeq(C2,ord): return GuessRec(L1+L2): end: ######################################################################### # Using the fact that the product of two C-finite sequences of orders a and b # is a C-finite sequence of order ≤ ab, use procedure RecToSeq to write a # procedure Mult1(C1,C2) that inputs two C-finite sequences in our notation # and outputs the C-finite sequence that is their product (in our notation). # For example # Mult1([[-2],[1]],[[-3],[1]]); should output # [[6],[1]] Mult1:=proc(C1,C2) local ord1, ord2, ord, L1, L2: ord1:=nops(C1[1]): ord2:=nops(C2[1]): ord:=2*ord1*ord2+8: L1:=RecToSeq(C1,ord): L2:=RecToSeq(C2,ord): return GuessRec(MultList(L1,L2)): end: MultList:=proc(L1,L2) return [seq(L1[i]*L2[i],i=1..nops(L1))]: end: ######################################################################### # Use RecToSeq to write a procedure BT(C) that inputs a C-finite sequence # and outputs its Binomial Transform. BT:=proc(C) local L1, L2: L1:=RecToSeq(C,5*nops(C[1])+8): L2:=[seq(add(binomial(j,i)*L1[i],i=1..j),j=1..nops(L1))]: return GuessRec(L2): end: ######################################################################### # Use RecToSeq to write a procedure Tsect(C,t,r) that inputs a C-finite sequence # and a positive integer t, non-negative integer r, (0 ≤ t < r) such that if C # is the C-finite description of a sequence a(n), then the output is the # C-finite description of the sequence a(tm+r), m=0,1,2,3,4 ... Tsect:=proc(C,t,r) length:=nops(C[1]): L1:=RecToSeq(C,t*(2*length+8)+r+5): L2:=[seq(L1[t*i+r],i=0..2*length+8)]: return GuessRec(L2): end: ######################################################################### # Old programs ######################################################################### # GuessRec1(L,r): inputs a sequence of numbers, L, and a positive integer # r, and tries to guess a linear recurrence equation of order r # that L satisfies # Want: L[n]+c1*L[n-1]+...+cr*L[n-r]=0 for all n within the range # Thes output would be given as a list of r numbers and a set of initial conditions # [[c1,c2,...,cr],[L[1],...,L[r]]] GuessRec1:=proc(L,r) local c,i, var,eq: if nops(L)<=2*r+5 then return `FAIL`: fi: var:={seq(c[i],i=1..r)}: eq:={seq(L[n]+add(c[i]*L[n-i],i=1..r)=0,n=r+1..nops(L))}: var:=solve(eq,var): if var=NULL then return `FAIL`: fi: return [[seq(subs(var,c[i]),i=1..r)],[seq(L[i],i=1..r)]]: end: # GuessRec(L): inputs a sequence of numbers, L, and tries to guess a linear # recurrence equation by successively trying GuessRec1(L,1), GuessRec1(L,2),..., GuessRec:=proc(L) local ans,r: for r from 1 to nops(L)/2 do ans:=GuessRec1(L,r): if ans<> `FAIL` then return ans: fi: od: return `FAIL`: end: