next up previous
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 tex2html_wrap_inline1595 is tex2html_wrap_inline1519-recursive with some tex2html_wrap_inline1853 if and only if the linear equation system (LES)

0
equation257
of n-r equations in r+1 variables is satisfied. Equivalently (1) can be represented by the matrix equation
equation261
If we denote the tex2html_wrap_inline1859-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 tex2html_wrap_inline1861, then the LES (1) can briefly be represented by the augmented matrix
equation286

4.2 Example. Given the 5-term sequence tex2html_wrap_inline1865. Is this sequence linear-recursive of some degree r=2 or r=3 ?

The approach for r=2 and tex2html_wrap_inline1873 leads to the LES
displaymath1837
with the augmented-matrix representation
equation308

The approach for r=3 and tex2html_wrap_inline1879 yields the LES
displaymath1838
with the augmented-matrix representation
equation317
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 tex2html_wrap_inline1595 and some fixed recursion degree tex2html_wrap_inline1703. Our purpose is to derive some general statements about existence and uniqueness of recursion formulae for tex2html_wrap_inline1591 within the domain tex2html_wrap_inline1889.

From the theory of LESs several useful results are available about existence and type of solution to (1) based on the ranksgif 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 tex2html_wrap_inline1893; thus, an important step will be to modify the statements such that they apply to the domain tex2html_wrap_inline1895 for recursion formulae of degree r.

4.3 Lemma. Consider for a given number sequence tex2html_wrap_inline1591 the LES (1) and the corresponding augmented-matrix representation (3). For solvability and solutions of (1) in tex2html_wrap_inline1893 the following statements hold:

(a)
The LES (1) is solvable with some tex2html_wrap_inline1903 if and only if tex2html_wrap_inline1905.
(b)
Assume the system (1) is solvable in tex2html_wrap_inline1893. Then the solution is uniquely determined if and only if tex2html_wrap_inline1909.
(c)
The system (1) has infinitely many solutions in tex2html_wrap_inline1893 if and only if tex2html_wrap_inline1913. Let tex2html_wrap_inline1915; 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 tex2html_wrap_inline1919. The essential point hereby is the condition that by Definition 2.2 the recursion coefficient tex2html_wrap_inline1921 in each considered solution formula must not be equal to 0.

4.4 Theorem. Let be given a non-constant n-term number sequence tex2html_wrap_inline1595 of rational numbers and some fixed recursion degree tex2html_wrap_inline1703. For the existence and uniqueness of recursion formulae in the domain tex2html_wrap_inline1529 satisfying the LES (1), the following statements hold:

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

PROOF.
(a) The LES (1) is unsolvable in tex2html_wrap_inline1529 if and only if it is either unsolvable in tex2html_wrap_inline1893 or there only exist(s) (one or infinitely many) solution(s) of (1) in tex2html_wrap_inline1977; therefore from the equivalence 4.3 (a) remains only a necessary condition for the existence of a recursion formula tex2html_wrap_inline1519 for a given sequence tex2html_wrap_inline1591 within tex2html_wrap_inline1529 . The contraposition yields (a).

(b) The LES (1) is uniquely solvable with some tex2html_wrap_inline1623 if and only if tex2html_wrap_inline1519 is a unique solution of (1) in tex2html_wrap_inline1893 with tex2html_wrap_inline1507; but if there exists a solution formula tex2html_wrap_inline1739 for (1), then 4.3 (b) includes a necessary and sufficient condition for the uniqueness of tex2html_wrap_inline1519 .

(c) The LES (1) is non-uniquely solvable with formulae of type tex2html_wrap_inline1997 tex2html_wrap_inline1999 if and only if there exist infinitely many solutions of type tex2html_wrap_inline1519 to (1) in tex2html_wrap_inline1893 where either tex2html_wrap_inline1507 is fixed or arbitrarily choosable in tex2html_wrap_inline1971. Therefore, if a solution formula tex2html_wrap_inline1739 for (1) exists at all, then 4.3 (c) reveals conditions and structure of an infinitely large solution set. tex2html_wrap_inline2011

4.5 Examples.

(a)
Given the 5-term sequence tex2html_wrap_inline2013 from 4.2. According to 4.4 (a), this sequence is not tex2html_wrap_inline2015-recursive for an tex2html_wrap_inline2017, because for the augmented matrix (4) holds tex2html_wrap_inline2019.
(b)
Given the 5-term sequence tex2html_wrap_inline2021. This sequence is easily recognized as tex2html_wrap_inline2023-recursive (with degree r=2). According to 4.4 (b), the recursion formula is unique because in the corresponding augmented-matrix representation holds tex2html_wrap_inline2027.
(c)
The 5-term sequence tex2html_wrap_inline2013 from 4.2. is for degree r=3 for instance tex2html_wrap_inline2033-recursive. The general solution approach with r=3 shows that tex2html_wrap_inline2037. Actually one obtains recursion formulae of the type tex2html_wrap_inline2039 where tex2html_wrap_inline2041 and tex2html_wrap_inline2043 are arbitrary parameters.
(d)
For the 5-term sequence tex2html_wrap_inline2045 the general solution approach with r=3 shows that tex2html_wrap_inline2037. However, one obtains only solutions of the type tex2html_wrap_inline2051 where tex2html_wrap_inline2053 and tex2html_wrap_inline2055 are arbitrary parameters, but tex2html_wrap_inline2057 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 tex2html_wrap_inline1909, then we can conclude from tex2html_wrap_inline2061 that tex2html_wrap_inline2063, and arrive at a useful necessary condition for the uniqueness of a recursion formula.

4.6 Corollary. Given an n-term number sequence tex2html_wrap_inline1591. A necessary condition for the uniqueness of a recursion formula tex2html_wrap_inline1739 for tex2html_wrap_inline1591 is the condition tex2html_wrap_inline2073.

The statement of 4.6 expressed in another way: If for a recursion degree tex2html_wrap_inline2075 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 tex2html_wrap_inline2077 is linear-recursive of degree r=2 with infinitely many recursion formulae of type tex2html_wrap_inline2081 with tex2html_wrap_inline2083 arbitrary, although the necessary condition in 4.6 is fulfilled.

4.8 Remark. Transform for tex2html_wrap_inline2085 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 tex2html_wrap_inline2087 (tex2html_wrap_inline2089) for the difference of each two succeeding members of the sequence; then we obtain the matrix
equation374
Now, Theorem 4.4 can be applied to (Dtex2html_wrap_inline2091). For instance, one obtains the statement:

If the sequence tex2html_wrap_inline1591 is tex2html_wrap_inline1519-recursive for some tex2html_wrap_inline2097, then the formula tex2html_wrap_inline1519 is uniquely determined if and only if in (6) holds tex2html_wrap_inline2101.
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 tex2html_wrap_inline1529 under the precondition of a fixed degree tex2html_wrap_inline1703 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 tex2html_wrap_inline1591 is tex2html_wrap_inline1519-recursive for some tex2html_wrap_inline1937 with r<n-1. Then for each recursion degree s with r<s<n there exist infinitely many other recursion formulae tex2html_wrap_inline2129 such that tex2html_wrap_inline1591 is tex2html_wrap_inline2133-recursive.

PROOF. Let tex2html_wrap_inline1591 be tex2html_wrap_inline1519-recursive with tex2html_wrap_inline2139, that is, the following equations are satisfied:
displaymath1839
Let r=1. For each tex2html_wrap_inline2143 and tex2html_wrap_inline2145 we can transform in the following way:
eqnarray409
Let tex2html_wrap_inline2147. For each tex2html_wrap_inline2143 and tex2html_wrap_inline2145 we transform the following way:
eqnarray423
Because tex2html_wrap_inline2143 can be arbitrarily chosen, there exist infinitely many recursion formulae tex2html_wrap_inline2155 in tex2html_wrap_inline2157. This argument can be iterated for higher recursion degrees until tex2html_wrap_inline2159 inclusively. tex2html_wrap_inline2011

4.10 Example. Given the (uniquely) tex2html_wrap_inline2163-recursive 6-term sequence tex2html_wrap_inline2165. Using the procedure from the proof of Theorem 4.9, this sequence turns out to be also tex2html_wrap_inline2167-recursive with arbitrary tex2html_wrap_inline2143. Fixing, for instance, z:= -1 one obtains the recursion formula tex2html_wrap_inline2173 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 tex2html_wrap_inline2177; thus, the inhomogeneous difference equation
displaymath1840
transforms into a homogeneous difference equation
displaymath1841
We document this consideration in the following corollary.

4.11 Corollary. Each tex2html_wrap_inline1517-recursive sequence tex2html_wrap_inline1591 of degree r<n-1 with tex2html_wrap_inline2185 is also tex2html_wrap_inline2187-recursive of degree r+1 with constant tex2html_wrap_inline2177.

If one knows the solution structure for the LES (1) in the domain tex2html_wrap_inline1529\ 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 tex2html_wrap_inline1591 there exists either none or only exactly one recursion formula of some degree r, then there exist no recursion formulae for tex2html_wrap_inline1591 of some degree s<r.

Note that the condition in Theorem 4.12 is sufficient but not necessary. For a sequence tex2html_wrap_inline1591 there may exist infinitely many recursion formulae of some degree r, but no recursion formula of degree tex2html_wrap_inline2213. This is exemplified by the 5-term sequence tex2html_wrap_inline2013 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 tex2html_wrap_inline1591 and some fixed recursion degree r there exist infinitely many recursion formulae of the type tex2html_wrap_inline2223, and let tex2html_wrap_inline2225 be the number of arbitrary parameters in tex2html_wrap_inline1519 . Then there exists a recursion formula tex2html_wrap_inline2129 for s<r such that tex2html_wrap_inline1591 is tex2html_wrap_inline2133-recursive, when the following two conditions are satisfied:

(i)
Among the formulae of type tex2html_wrap_inline1519 there exists some formula with tex2html_wrap_inline2239 and tex2html_wrap_inline2241.
(ii)
Additionally to the recursion equations for tex2html_wrap_inline2243, which are satisfied by the formulae of type tex2html_wrap_inline1519 , the linear equations
displaymath1842
are fulfilled by the formula tex2html_wrap_inline2247.

4.14 Examples.

(a)
The 5-term sequence tex2html_wrap_inline2249 is for r=3 linear-recursive with infinitely many recursion formulae of type tex2html_wrap_inline2253 with tex2html_wrap_inline2255 arbitrary. But tex2html_wrap_inline2257 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 tex2html_wrap_inline2077 was shown to be linear-recursive of degree r=2 with infinitely many recursion formulae of type tex2html_wrap_inline2265 with tex2html_wrap_inline2083 arbitrary. In tex2html_wrap_inline2015 set the parameter tex2html_wrap_inline2053 equal to 0 and obtain the formula tex2html_wrap_inline2273. The recursion equation for tex2html_wrap_inline2275, tex2html_wrap_inline2277, is fulfilled. Hence the sequence is also tex2html_wrap_inline2279-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 tex2html_wrap_inline1527 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 tex2html_wrap_inline2285, depending on the length n of the number sequence, by imposing the condition tex2html_wrap_inline2289.
b)
The restriction of the domain tex2html_wrap_inline1527 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 up previous
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
© 1998 Pabst Science Publishers