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=[v0,…,v2n−1], a vector made of the first 2n terms
of a sequence (vn) which is supposed to verify a linear
recurrence relation of degree smaller than n
where the xj are n+1 unknowns.
- reverse_rsolve(v) 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 | = | 0 |
… |
xn*vn+k+⋯+x0*vk | = | 0 |
… |
xn*v2*n−1+⋯+x0*vn−1 | = | 0
|
|
The matrix A of the system has n rows and n+1 columns:
A= | ⎛
⎜
⎜
⎜
⎜
⎜
⎝ | vn | … | v0 | 0 |
⋮ | | | ⋮ |
vn+k | … | vk | 0 |
⋮ | | | ⋮ |
v2n−1 | v2 | vn−1 | 0
|
| ⎞
⎟
⎟
⎟
⎟
⎟
⎠ |
|
reverse_rsolve returns the list x=[xn,…,x1,x0] with xn=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:
Hence x0=−6, x1=−3, x2=1 and the recurrence relation is
- 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:
Hence, x0=−1, x1=1/2, x2=−1/2, x3=1, the recurrence
relation is
vk+3 − | | vk+2 + | | vk+1 −vk =0
|