Finding linear recurrences : reverse_rsolve

reverse_rsolve takes as argument a vector v = [v₀...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₀*v_k = 0

where the x_j are n + 1 unknowns.
reverse_rsolve returns the list x = [x_n,..., x₀] of the x_j coefficients (if x_n $\neq$ 0 it is reduced to 1).

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

x_n*v_n + ... + x₀*v₀ = 0 ...

x_n*v_n+k + ... + x₀*v_k = 0 ...

x_n*v_2*n-1 + ... + x₀*v_n-1 = 0

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

A = [[v₀, v₁...v_n],[v₁, v₂,...v_n-1],...,[v_n-1, v_n...v_2n-1]]

reverse_rsolve returns the list x = [x_n,...x₁, x₀] with x_n = 1 and x is the solution of the system A*$\tt 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₀ = - 6, x₁ = - 3, x₂ = 1 and the recurrence relation is
  v_k+2 -3v_k+1 -6v_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₀ = - 6 and x₁ = - 3 (because x₂ = 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₀ = - 1, x₁ = 1/2, x₂ = - 1/2, x₃ = 1, the recurrence relation is
  v_k+3 - $${\frac{{1}}{{2}}}$$v_k+2 + $${\frac{{1}}{{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₀ = - 1, x₁ = 1/2 and x₂ = - 1/2 because x₃ = 1),