# C7.txt , Feb. 11, 2016; The C-finite ansatz Help:=proc(): print(` GRc(L), GRc1(L,k), AddC(R1,R2) `): end: ###stuff from C6.txt #C6.txt, Feb. 8, 2016, Dr. Z.'s ExpMath class RU (Spring 2016) #c=introducing Dr. Z.'s second-most favorite "ansatz" Help6:=proc() print(` RecToSeq(R,N), RecToSeqW(R,N,w)`): end: #RecToSeq(R,N): inputs a C-finite sequence [ini,rec] where ini is a list #of numbers of length k say, and rec is a list of coefficients of the #C-finite sequence defined UNIQELY by #x(n)=ini[n+1], for n=0..k-1, #and rec is a list of numbers [c1,c2,...,ck] #and for n>=k defined recursively by #x(n)=c1*x(n-1)+c2*x(n-2)+...+ck*x(n-k). #For example the sequence 2^n is coded as #[[1],[2]], and the sequence of Fib. numbers are given by #[[0,1],[1,1]] #It outputs the list consisting of the first N terms of that sequence starting at n=0 RecToSeq:=proc(R,N) local ini,rec,Se,k,n,nt: ini:=R[1]: rec:=R[2]: k:=nops(ini): if nops(rec)<>k then RETURN(FAIL): fi: Se:=ini: for n from k+1 to N do #nt:=c1*Se[n]+c2*Se[n-1]+...+ ck*se[n-k+1] nt:=add(rec[i]*Se[n-i],i=1..k): Se:=[op(Se),nt]: od: Se: end: #RecToSeqW(R,N,w): inputs a C-finite sequence [ini,rec] where ini is a list #of numbers of length k say, and rec is a list of coefficients of the #C-finite sequence defined UNIQELY by #x(n)=ini[n+1], for n=0..k-1, #and rec is a list of numbers [c1,c2,...,ck] #and for n>=k defined recursively by #x(n)=c1*x(n-1)+c2*x(n-2)+...+ck*x(n-k). #For example the sequence 2^n is coded as #[[1],[2]], and the sequence of Fib. numbers are given by #[[0,1],[1,1]] #It outputs the list consisting of the terms N-w+1 through w of that sequence starting at n=N-w+1 RecToSeqW:=proc(R,N,w) local ini,rec,Se,k,n,nt: ini:=R[1]: rec:=R[2]: k:=nops(ini): if nops(rec)<>k then RETURN(FAIL): fi: if w(nops(L)-4)/2 then print(`Not enough data`): RETURN(FAIL): fi: ini:=[op(1..k,L)]: rec:=[seq(c[i],i=1..k)]: var:={seq(c[i],i=1..k)}: #L[n]=c1*L[n-1]+ ... + ck*L[n-k] eq:={ seq(L[n]-add(c[i]*L[n-i],i=1..k),n=k+1..2*k+4)}: var1:=solve(eq,var): if var1=NULL then RETURN(FAIL): fi: R:=[ini,subs(var1,rec)]: if RecToSeq(R,nops(L))<>L then RETURN(FAIL): fi: R: end: #GRc(L): inputs a list of rational numbers L and tries to find a linear #recurrence equation with constant coefficient in the form [ini,rec] #where rec=[c1,..., ck], and the recurrence is #x(n)=c1*x(n-1)+...+ck*x(n-k) GRc:=proc(L) local k,R: for k from 1 to (nops(L)-4)/2 do R:=GRc1(L,k): if R<>FAIL then RETURN(R): fi: od: FAIL: end: #AddC(R1,R2): inputs two C-finite sequences R1 and R2 and outputs their sum AddC:=proc(R1,R2) local L1,L2,N,k1,k2,L,i: k1:=nops(R1[1]): k2:=nops(R2[2]): L1:=RecToSeq(R1,2*(k1+k2+4)): L2:=RecToSeq(R2,2*(k1+k2+4)): L:=[seq(L1[i]+L2[i],i=1..2*(k1+k2+4))]: GRc(L): end: #MulC(R1,R2): inputs two C-finite sequences R1 and R2 and outputs their product MulC:=proc(R1,R2) local L1,L2,N,k1,k2,L,i: k1:=nops(R1[1]): k2:=nops(R2[2]): L1:=RecToSeq(R1,2*(k1*k2+4)): L2:=RecToSeq(R2,2*(k1*k2+4)): L:=[seq(L1[i]*L2[i],i=1..2*(k1*k2+4))]: GRc(L): end: