Example 2.20 (A Large Solution Space for a Linear Recurrence)

A linear recurrence relation with larger solution space than order.
Requirements: None

# Define the ring of shift operators to encode P-recurrence
from ore_algebra import *
Ind.<n> = PolynomialRing(QQ); Shift.<Sn> = OreAlgebra(Ind)

# The matrix M encoding the recurrence for n = 0,1,2
M = Matrix([[1,-1,0,0,0],[0,0,-1,-1,0],[0,0,-1,-1,0]])
M

[ 1 -1  0  0  0]
[ 0  0 -1 -1  0]
[ 0  0 -1 -1  0]

# The kernel of M has dimension 3
# A solution (f_n) to the recurrence is uniquely determined by its values of f_0, f_2, and f_4
M.right_kernel()

Free module of degree 5 and rank 3 over Integer Ring
Echelon basis matrix:
[ 1  1  0  0  0]
[ 0  0  1 -1  0]
[ 0  0  0  0  1]