next up previous
Next: Summary and general discussion Up: MPR-online 1998Vol.3, No.1 Previous: Analysis of the uniqueness

Decidability of the uniqueness problem for the special type of number sequence task

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 tex2html_wrap_inline2325 one takes into consideration the domains tex2html_wrap_inline2815 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 tex2html_wrap_inline2347,
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 tex2html_wrap_inline2429 of natural numbers there exists a uniquely determined recursion formula tex2html_wrap_inline2433 such that tex2html_wrap_inline2303 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.

For the sequence tex2html_wrap_inline2839 only the LES (II.2) is solvable. The sequence is uniquely tex2html_wrap_inline2841-recursive with tex2html_wrap_inline2843.
For the sequence tex2html_wrap_inline2845 each of the LESs from (I), (II), and (III) are solvable with
tex2html_wrap_inline2847; tex2html_wrap_inline2849; tex2html_wrap_inline2851; tex2html_wrap_inline2853; tex2html_wrap_inline2855; tex2html_wrap_inline2857;
each formula leads to tex2html_wrap_inline2859.
For the sequence tex2html_wrap_inline2861 only the LES (III.3) is solvable with tex2html_wrap_inline2863 and tex2html_wrap_inline2865. (Note that (III.1) is satisfied with tex2html_wrap_inline2867, however, by definition of tex2html_wrap_inline2341, tex2html_wrap_inline2871; accordingly with (III.2).)
For the sequence tex2html_wrap_inline2873 only (III.3) is solvable. The solution, however, is not unique, because there are infinitely many solutions of type tex2html_wrap_inline2875 with tex2html_wrap_inline2655 arbitrary, and with tex2html_wrap_inline2879 for each tex2html_wrap_inline2655 (see Proposition 6.3(c)).

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.

next up previous
Next: Summary and general discussion Up: MPR-online 1998Vol.3, No.1 Previous: Analysis of the uniqueness

Methods of Psychological Research 1998 Vol.3 No.1
© 1998 Pabst Science Publishers