In this section, we will derive some basic results concerning the problems of existence and uniqueness of recursion formulae for given number sequences. For this purpose we refer to the theory of linear equation systems, that provides several useful theorems on the existence, uniqueness and structure of solutions of a given system of linear equations. Let us first introduce some notation.
4.1 Notation.
Recall that, according to 2.2/2.4, a (non-constant) number sequence
is -recursive with some
if and only if the linear equation system (LES)
0
of n-r equations in r+1 variables is satisfied.
Equivalently (1) can be represented by the matrix equation
If we denote the -matrix on the left-hand side of (2)
(which is usually called the coefficient matrix of (2)) by A\
and the vector on the right-hand side of (2) by , then the LES
(1) can briefly be represented by the augmented matrix
4.2 Example. Given the 5-term sequence . Is this sequence linear-recursive of some degree r=2 or r=3 ?
The approach for r=2 and
leads to the LES
with the augmented-matrix representation
The approach for r=3 and
yields the LES
with the augmented-matrix representation
We leave the solution to our example task for later analysis.
Now let be given a number sequence task of the general type 3.1 including some non-constant number sequence and some fixed recursion degree . Our purpose is to derive some general statements about existence and uniqueness of recursion formulae for within the domain .
From the theory of LESs several useful results are available about existence and type of solution to (1) based on the ranks of the coefficient matrix and the augmented matrix in (3) of the LES (1). We summarize some useful statements from the theory of LESs in the following lemma (for the theory of LES see e.g. Kowalsky, 1974; Kuiper, 1962). However observe, that the statements refer to solutions of (1) within ; thus, an important step will be to modify the statements such that they apply to the domain for recursion formulae of degree r.
4.3 Lemma. Consider for a given number sequence the LES (1) and the corresponding augmented-matrix representation (3). For solvability and solutions of (1) in the following statements hold:
We transfer the statements of 4.3 to the problems of existence and uniqueness of solution formulae for (1) within the domain . The essential point hereby is the condition that by Definition 2.2 the recursion coefficient in each considered solution formula must not be equal to 0.
4.4 Theorem. Let be given a non-constant n-term number sequence of rational numbers and some fixed recursion degree . For the existence and uniqueness of recursion formulae in the domain satisfying the LES (1), the following statements hold:
PROOF.
(a) The LES (1) is unsolvable in if and only if it is either
unsolvable in or there only exist(s) (one or infinitely
many) solution(s) of (1) in ; therefore
from the equivalence 4.3 (a) remains only a necessary condition
for the existence of a recursion formula for a given sequence
within . The contraposition yields (a).
(b) The LES (1) is uniquely solvable with some if and only if is a unique solution of (1) in with ; but if there exists a solution formula for (1), then 4.3 (b) includes a necessary and sufficient condition for the uniqueness of .
(c) The LES (1) is non-uniquely solvable with formulae of type if and only if there exist infinitely many solutions of type to (1) in where either is fixed or arbitrarily choosable in . Therefore, if a solution formula for (1) exists at all, then 4.3 (c) reveals conditions and structure of an infinitely large solution set.
4.5 Examples.
From 4.4 (b) we derive an immediate consequence. If in (3) holds , then we can conclude from that , and arrive at a useful necessary condition for the uniqueness of a recursion formula.
4.6 Corollary. Given an n-term number sequence . A necessary condition for the uniqueness of a recursion formula for is the condition .
The statement of 4.6 expressed in another way: If for a recursion degree there exist recursion formulae at all, then in fact infinitely many, the structure of which is described in 4.4 (c). Observe, however, that the condition given in 4.6 is not sufficient as is verified by the following example.
4.7 Example. The 6-term sequence is linear-recursive of degree r=2 with infinitely many recursion formulae of type with arbitrary, although the necessary condition in 4.6 is fulfilled.
4.8 Remark.
Transform for the augmented matrix (3) of the
LES (1) equivalently by subtracting each row from the preceding
one (and leaving the last row unchanged), and set as an abbreviation
() for the difference
of each two succeeding members of the sequence; then we obtain the
matrix
Now, Theorem 4.4 can be applied to (D).
For instance, one obtains the statement:
If the sequence is -recursive for some , then the formula is uniquely determined if and only if in (6) holds .This consideration is interesting insofar as it shows that the problems of existence and uniqueness of a recursion formula for a given number sequence can be decided solely by referring to the sequence of differences and hence do not depend on the recursion constant. We will refer back to this in Section 5.
Up to now we have derived several statements on the existence, uniqueness, and structure of a solution set for (1) in under the precondition of a fixed degree of recursion. Suppose now we had a certain result for a fixed recursion degree r. What can we conclude for solutions of recursion degrees s<r and s>r ? For s>r the following theorem is provable.
4.9 Theorem. Assume the n-term sequence is -recursive for some with r<n-1. Then for each recursion degree s with r<s<n there exist infinitely many other recursion formulae such that is -recursive.
PROOF.
Let be -recursive with ,
that is, the following equations are satisfied:
Let r=1.
For each and
we can transform in the following way:
Let .
For each and
we transform the following way:
Because can be arbitrarily chosen,
there exist infinitely many recursion formulae
in
.
This argument can be iterated for higher recursion degrees until
inclusively.
4.10 Example. Given the (uniquely) -recursive 6-term sequence . Using the procedure from the proof of Theorem 4.9, this sequence turns out to be also -recursive with arbitrary . Fixing, for instance, z:= -1 one obtains the recursion formula where the constant is 0.
The example in 4.10 may demonstrate that recursion formulae of a
higher degree need not necessarily be more complicated in a psychological
sense than the recursion formulae of a lower degree. For instance,
fixing the introduced parameter z:=-1 in the proof to Theorem 4.9
(see 4.10) leads to the constant ; thus, the
inhomogeneous difference equation
transforms into a homogeneous difference equation
We document this consideration in the following corollary.
4.11 Corollary. Each -recursive sequence of degree r<n-1 with is also -recursive of degree r+1 with constant .
If one knows the solution structure for the LES (1) in the domain \ for some fixed r, then there are also conclusions for the existence and uniqueness of solution formulae of degree s<r available. From Theorem 4.9 we obtain by contraposition the following theorem.
4.12 Theorem. If for some n-term sequence there exists either none or only exactly one recursion formula of some degree r, then there exist no recursion formulae for of some degree s<r.
Note that the condition in Theorem 4.12 is sufficient but not necessary. For a sequence there may exist infinitely many recursion formulae of some degree r, but no recursion formula of degree . This is exemplified by the 5-term sequence from example 4.2. In 4.5 (a) this sequence has been proven not to be linear-recursive of degree 2; in 4.5 (c), however, it turned out that for this sequence there exist infinitely many recursion formulae of degree 3. Nevertheless, under certain specific conditions the conclusion from infinitely many recursion formulae of some degree r to recursion formulae of lower degree is valid. This is stated by the easily comprehensible theorem in 4.13.
4.13 Theorem. Assume for the sequence and some fixed recursion degree r there exist infinitely many recursion formulae of the type , and let be the number of arbitrary parameters in . Then there exists a recursion formula for s<r such that is -recursive, when the following two conditions are satisfied:
4.14 Examples.
4.15 Consequences.
The results concerning the problems of solvability and (non-)uniqueness of solutions to the general type of number sequence task in 3.1 do not depend on the domain for the members of a number sequence. Instead, the investigated solvability and uniqueness problems are caused decisively by the fact that neither for the recursion degree r nor for the domain of permitted recursion formulae essential restrictions have been introduced. This is in accordance with the usual formulation of number sequence tasks in psychological applications.
In order to avoid uncontrolled non-uniqueness, three (nonexclusive) approaches seem suggested: