For each finite number sequence it can be decided on the basis of
an LES of type (1), whether the number sequence is linear-recursive
of some degree r or not,
and if so, then by which recursion formula(e) the sequence
can be represented; in doing so the domain for the recursion formulae
has to be taken into account. In the case of our special type of
task 5.2, the search for recursion formulae can be carried out in a
type-specific way: If for each permitted recursion degree
one takes into consideration the domains
that are
permitted under (R) for the possible recursion formulae (see 5.1),
then from the recursion equations for a given non-constant
6-term sequence ,
we obtain the following six LESs for determining the variable
coefficients of permissible recursion formulae:
Since the domains for the recursion formulae of some particular degree
are pairwise disjoint, one immediately obtains the following theorem.
7.1 Theorem. For a given non-constant 6-term sequence of natural numbers there exists a uniquely determined recursion formula such that is F-recursive if and only if exactly one of the above LESs has (in its respective domain) exactly one solution.
Because LESs can be treated by several efficient algorithms (for instance by Gaussian elimination), the theorem also provides a decision procedure which is always successful.
7.2 Examples.
The example sequence in 7.2 (a) confirms that in fact there exist number sequences for our special type with a unique recursion formula (and thus also with a unique extension). Actually, infinitely many such sequences exist.