2.52.7 Finding linear recurrences : reverse_rsolve
reverse_rsolve takes as argument a vector
v=[v_{0}...v_{2n−1}] made of the first 2n terms of a sequence (v_{n})
which is supposed to verify a linear recurrence relation of
degree smaller than n
x_{n}*v_{n+k}+...+x_{0}*v_{k}=0 
where the x_{j} are n+1 unknowns.
reverse_rsolve returns the list x=[x_{n},...,x_{0}]
of the x_{j} coefficients (if x_{n}≠ 0 it is reduced to 1).
In other words reverse_rsolve solves the linear system of
n equations :
x_{n}*v_{n}+...+x_{0}*v_{0}  =  0 
... 
x_{n}*v_{n+k}+...+x_{0}*v_{k}  =  0 
... 
x_{n}*v_{2*n−1}+...+x_{0}*v_{n−1}  =  0 

The matrix A of the system has n rows and n+1 columns :
A=[[v_{0},v_{1}...v_{n}],[v_{1},v_{2},...v_{n−1}],...,[v_{n−1},v_{n}...v_{2n−1}]] 
reverse_rsolve returns the list x=[x_{n},...x_{1},x_{0}] with x_{n}=1
and x is the solution of the system A*revlist(x).
Examples

Find a sequence verifying a linear recurrence of degree at
most 2 whose first elements 1, 1, 3, 3.
Input :
reverse_rsolve([1,1,3,3])
Output :
[1,3,6]
Hence x_{0}=−6, x_{1}=−3, x_{2}=1 and the recurrence relation is
v_{k+2} −3v_{k+1} −6 v_{k} =0 
Without reverse_rsolve, we would write the matrix of the system :
[[1,1,3],[1,3,3]] and use the rref command :
rref([[1,1,3],[1,3,3]])
Output is [[1,0,6],[0,1,3]] hence x_{0}=−6 and x_{1}=−3
(because x_{2}=1).  Find a sequence verifying a linear recurrence of degree at
most 3 whose first elements are 1, 1, 3, 3,1, 1.
Input :
reverse_rsolve([1,1,3,3,1,1])
Output :
[1,(1)/2,1/2,1]
Hence so, x_{0}=−1, x_{1}=1/2, x_{2}=−1/2, x_{3}=1, the recurrence
relation is
v_{k+3} −   v_{k+2} +   v_{k+1} −v_{k} =0 
Without reverse_rsolve, we would write the matrix of the system :
[[1,1,3,3],[1,3,3,1],[3,3,1,1]].
Using rref command, we would input :
rref([[1,1,3,3],[1,3,3,1],[3,3,1,1]])
Output is [1,0,0,1],[0,1,0,1/2],[0,0,1,1/2]]
hence x_{0}=−1, x_{1}=1/2 and x_{2}=−1/2 because x_{3}=1),