Recursive Definitions - Existence and Definitions

Mathematical Writing - Vivaldi Franco 2014

Recursive Definitions
Existence and Definitions

A recursive definition is a form of definition connected to the principle of induction. With this method it is possible to define very complex objects—sequences, typically—from minimal ingredients.

We have pointed out that a sequence $$(a_k)$$ corresponds to a function over $$\mathbb {N}$$, whereby $$a_k$$ represents the value of the function at the point $$k\in \mathbb {N}$$. The existence of such a function does not necessarily imply that its values are easily recoverable from the definition of the sequence. For example, we don’t know any ’useful’ way to express the $$k$$th prime number as an explicit function of $$k$$. In absence of an explicit formula for the elements of a sequence, we seek to represent $$a_{k+1}$$ in terms of $$a_{k}$$. These are recursive sequences, which are defined by two data: the first term of the sequence, called the initial condition, and the rule which determines a term from the previous one.

For instance, the factorial sequence $$n!=1\cdot 2\cdot 3\,\cdots \, n$$, can be defined recursively as follows:

$$\begin{aligned} 0!=1 \qquad (k+1)!=(k+1)\cdot k!\qquad k\geqslant 0. \end{aligned}$$

(9.5)

This definition, in effect, specifies the order in which the product is computed. Likewise, the $$n$$th derivative $$g^{(n)}$$ of a function $$g$$ is defined by the recursive rule

$$ g^{(0)}(x)=g(x) \qquad g^{(k+1)}(x)=\frac{\mathrm{d}}{\mathrm{d}x}g^{(k)}(x)\qquad k\geqslant 0. $$

More generally, given any set $$X$$ and any function $$f{:}\,X\rightarrow X$$, we define a recursive sequence $$(a_k)$$ of elements of $$X$$ as follows:

$$\begin{aligned} a_1\in X \quad {\mathrm{given;}} \qquad a_{k+1}=f(a_{k}),\quad k\geqslant 1. \end{aligned}$$

(9.6)

The first term of the sequence (the initial condition) is given. Because $$f$$ is a function, if $$a_k$$ is well-defined for some $$k\geqslant 1$$, then so is $$a_{k+1}$$. The induction principle then ensures that the whole sequence is well-defined. Since distinct initial conditions in $$X$$ give rise to distinct sequences, there are as many sequences as there are elements of $$X$$: plenty of sequences from just one function!

The term $$a_{k+1}$$ of a recursive sequence may depend on $$d\geqslant 1$$ preceding terms, not just the last one:

$$\begin{aligned} a_{k+1}=f(a_{k},a_{k-1},\ldots ,a_{k-d+1}). \end{aligned}$$

(9.7)

In this case we have $$f:X^d\rightarrow X$$, and $$d$$ is called the order of the sequence. In a recursive sequence of order $$d$$, the first $$d$$ terms of the sequence must be supplied explicitly because they don’t have the required number of preceding terms. These sequences have $$d$$ initial conditions and they are well-defined by virtue of strong induction.

The Fibonacci sequence 5 is a second-order sequence:

$$ a_0=1;\qquad a_1=1;\qquad a_{k+1}=f(a_{k},a_{k-1})=a_{k}+a_{k-1}, \quad k\geqslant 1. $$

We find

$$ (1,1,2,3,5,8,13,21,34,55,89,144,\ldots ). $$

Because the term $$a_{k-1}=a_{k+1}-a_{k}$$ is a well-defined function of the following two terms, we can extend the Fibonacci sequence backwards to obtain a doubly-infinite sequence:

$$ (\ldots ,-21,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,\ldots ). $$

A recursive sequence that can be extended backwards is said to be invertible. Thus the Fibonacci sequence is invertible.

Recursive sequences may be quite unpredictable, as the following example illustrates. Let

$$ f{:}\,\mathbb {N}\rightarrow \mathbb {N}\qquad \quad x\mapsto {\left\{ \begin{array}{ll} x/2 &{} \text {if}\, x\, \text {is even}\\ 3x+1&{} \text {if}\, x\, \text {is odd.}\end{array}\right. } $$

We consider the first-order recursive sequence associated with this function:

$$\begin{aligned} x_0=n \qquad x_{t+1}=f(x_t),\quad t\geqslant 0. \end{aligned}$$

(9.8)

The initial condition $$x_0=1$$ leads to a periodic sequence

$$\begin{aligned} (1,4,2,1,4,2,1,\ldots ) \end{aligned}$$

(9.9)

consisting of indefinite repetitions of the pattern $$(1,4,2)$$. If instead we start with $$x_0=7$$, we find

$$(7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,\ldots )$$

so, after an irregular initial excursion, the sequence settles down to the same periodic pattern as the previous sequence. The analysis of the sequences (9.8) for general initial condition $$n$$ presents formidable difficulties, which are distilled into a famous unsolved problem, the so-called ’3$$x$$+1’ conjecture [43] :

Conjecture For any $$n$$, the sequence (9.8) contains 1.

This conjecture states that all these sequences are eventually periodic and that they reach the same periodic pattern.

We note that any open conjecture leads to objects whose existence is at present undecidable, see Exercises 9.4 and 10.4.