Previous Up Next

15.7.10  Finding linear recurrences

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

In other words, reverse_rsolve solves the linear system of n equations of the form

  xnvn+k+⋯+x0vk=0,   k=0,1,…,n−1.

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

  A=






    vnv00
    ⋮ ⋮ 
    vn+kvk0
    ⋮ ⋮ 
    v2n−1vn−10






reverse_rsolve returns the solution x=[xn,…,x1,x0] of Ax=0 which satisfies xn=1.

Examples

Find a sequence satisfying a linear recurrence of degree at most 2 whose first elements are 1, −1, 3, 3.

reverse_rsolve([1,-1,3,3])
     

1,−3,−6
          

Hence x0=−6, x1=−3, x2=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.

reverse_rsolve([1,-1,3,3,-1,1])
     



1,−
1
2
,
1
2
,−1


          

Hence, x0=−1, x1=1/2, x2=−1/2, x3=1, and the recurrence relation is

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

Previous Up Next