The LREtools package for linear recurrence equations has been enhanced with the addition of several commands related to recurrence factorization and recognition:
GCRD, GeneralizedExponents, GuessRecurrence, LCLM, MinimalRecurrence, MultiplyOperators, OperatorToRecurrence, RecurrenceToOperator, RightDivision, RightFactors, SumDecompose
As an example consider the well known Fibonacci sequence:
The GuessRecurrence command can be used to algorithmically determine the underlying recurrence under the assumption that it is holonomic:
Consider the following recurrence written in operator form:
We can obtain all order 1 right factors as follows:
and order 2 right factors as follows.