Previous Up Next

2.52.7  Finding linear recurrences : reverse_rsolve

reverse_rsolve takes as argument a vector v=[v0...v2n−1] made of the first 2n terms of a sequence (vn) which is supposed to verify a linear recurrence relation of degree smaller than n

xn*vn+k+...+x0*vk=0 

where the xj are n+1 unknowns.
reverse_rsolve returns the list x=[xn,...,x0] of the xj coefficients (if xn≠ 0 it is reduced to 1).

In other words reverse_rsolve solves the linear system of n equations :

xn*vn+...+x0*v0=
...
xn*vn+k+...+x0*vk=
...
xn*v2*n−1+...+x0*vn−1=0

The matrix A of the system has n rows and n+1 columns :

A=[[v0,v1...vn],[v1,v2,...vn−1],...,[vn−1,vn...v2n−1]] 

reverse_rsolve returns the list x=[xn,...x1,x0] with xn=1 and x is the solution of the system A*revlist(x).

Examples


Previous Up Next