15.7.10 Finding linear recurrences
The reverse_rsolve
command finds a linear recurrence relation given the first few terms.
-
reverse_rsolve takes
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 xnvn+k+⋯+x0vk=0 of degree smaller
than n, where the xj are n+1 unknowns.
- reverse_rsolve(v) returns the list
x=[xn,…,x0] (if xn≠ 0 then xn is reduced to 1).
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= | ⎡
⎢
⎢
⎢
⎢
⎢
⎣ | | vn | ⋯ | v0 | 0 |
| ⋮ | | ⋮ | ⋮ |
| vn+k | ⋯ | vk | 0 |
| ⋮ | | ⋮ | ⋮ |
| v2n−1 | ⋯ | vn−1 | 0
|
| ⎤
⎥
⎥
⎥
⎥
⎥
⎦ |
|
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]) |
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]) |
Hence, x0=−1, x1=1/2, x2=−1/2, x3=1, and the recurrence
relation is
| vk+3 − | | vk+2 + | | vk+1 −vk=0.
|