6.56.10  Finding linear recurrences: reverse_rsolve

The reverse_rsolve command finds a linear recurrence relation given the first few terms.

• reverse_rsolve takes one argument:
  v=[v₀,…,v_2n−1], a vector 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

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

  where the x_j are n+1 unknowns.
• reverse_rsolve(v) returns the list x=[x_n,…,x₀] 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:

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

reverse_rsolve returns the list x=[x_n,…,x₁,x₀] with x_n=1 and x is the solution of the system Ax=0.

Examples:

• Find a sequence satisfying a linear recurrence of degree at most 2 whose first elements are 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

  vk+2 −3vk+1 −6 vk =0

• Find a sequence satisfying 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, x₀=−1, x₁=1/2, x₂=−1/2, x₃=1, the recurrence relation is

  vk+3 −

  1 2

  vk+2 +

  1 2

  vk+1 −vk =0