Next: A special type of Up: MPR-online 1998Vol.3, No.1 Previous: General type of task

# Existence and uniqueness of solution formulae

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:

(a)
The LES (1) is solvable with some if and only if .
(b)
Assume the system (1) is solvable in . Then the solution is uniquely determined if and only if .
(c)
The system (1) has infinitely many solutions in if and only if . Let ; then in the solution formulae d parameters can be chosen arbitrarily.

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:

(a)
If in the augmented-matrix representation (3) of the LES (1) holds , then the sequence is not -recursive for any (i.e. not linear-recursive of degree r).
(b)
Assume the sequence is -recursive for some . Then the formula is unique for if and only if in (3) holds .
(c)
Assume the sequence is -recursive for some . Then there exist even infinitely many recursion formulae for in \ if and only if . Let ; then in the recursion formulae d elements can be chosen arbitrarily (with the restriction that if is an arbitrary parameter, then it only can be chosen from ).

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.

(a)
Given the 5-term sequence from 4.2. According to 4.4 (a), this sequence is not -recursive for an , because for the augmented matrix (4) holds .
(b)
Given the 5-term sequence . This sequence is easily recognized as -recursive (with degree r=2). According to 4.4 (b), the recursion formula is unique because in the corresponding augmented-matrix representation holds .
(c)
The 5-term sequence from 4.2. is for degree r=3 for instance -recursive. The general solution approach with r=3 shows that . Actually one obtains recursion formulae of the type where and are arbitrary parameters.
(d)
For the 5-term sequence the general solution approach with r=3 shows that . However, one obtains only solutions of the type where and are arbitrary parameters, but is fixed. Thus the given sequence is according to Definition 2.2 not linear-recursive of degree 3. This example proves that in 4.4 (c) the existence of some permissible recursion formula is a necessary precondition.

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:

(i)
Among the formulae of type there exists some formula with and .
(ii)
Additionally to the recursion equations for , which are satisfied by the formulae of type , the linear equations

are fulfilled by the formula .

4.14 Examples.

(a)
The 5-term sequence is for r=3 linear-recursive with infinitely many recursion formulae of type with arbitrary. But is fixed and cannot be set equal to 0. Thus condition (i) of Theorem 4.13 is not fulfilled. In fact, the sequence is not linear-recursive of degree r=2.
(b)
In 4.7 the 6-term sequence was shown to be linear-recursive of degree r=2 with infinitely many recursion formulae of type with arbitrary. In set the parameter equal to 0 and obtain the formula . The recursion equation for , , is fulfilled. Hence the sequence is also -recursive.

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:

a)
The restriction of the maximal permissible recursion degree , depending on the length n of the number sequence, by imposing the condition .
b)
The restriction of the domain of permissible recursion formulae for each permitted r.
c)
The very careful construction of each number sequence task and analysis of the solution formulae for the sequence by means of a LES (1).

Next: A special type of Up: MPR-online 1998Vol.3, No.1 Previous: General type of task

Methods of Psychological Research 1998 Vol.3 No.1