Question

Exercises 70-77 deal with some unusual informally called self-generating sequences, produced by simple recurrence relations or rules. In particular, exercises 70-75 deal with the sequence \(\left\{ {a\left( n \right)} \right\}\) defined by \(a\left( n \right) = n - a\left( {a\left( {n - 1} \right)} \right)\) for \(n \ge 1\) and \(a\left( 0 \right) = 0\). (This sequence, as well as those in exercise 74 and 75, are defined in Douglas Hofstadter’s fascinating book Gödel, Escher, Bach ((Ho99))

Prove that this sequence is well defined. That is show that \(\left\{ {a\left( n \right)} \right\}\) is uniquely defined for all nonnegative integers \(n\).

Short answer

It is proved that the given sequence is well defined.

Step-by-step solution

Define Basis step and Recursive step

The recursive definition comprises of the two steps first is basis step and the second is the recursive step. The basis step consists of grouping of components initially. The recursive stage consists of the rules that forms the new elements from the previous known set.

Consider the recursive rule states the exclusion rule that shows that the set is recursive only and have the elements that are generated with the help of recursive step.

Determine Basis part \(\left( {a = 0} \right)\)

Consider the sequence\(a\left( n \right) = n - a\left( {a\left( {n - 1} \right)} \right)\)

Consider the initial term as \(a\left( 0 \right) = 0\) and hence \(\left\{ {a\left( n \right)} \right\}\) is well defined.

Moreover, \(0 \le a\left( 0 \right) = 0 \le 0\)

Hence, the statement is true for basis part.

Determine Recursive part \(\left( {a\left( n \right)} \right)\)

Now, suppose that\(a\left( 0 \right),\,a\left( 1 \right),\,...,\,a\left( {n - 1} \right)\)is well defined and

For \(0 \le a\left( i \right) \le i\), here \(i = 0,\,1,\,2,\,...,\,\left( {n - 1} \right)\).

Now, \(a\left( n \right) = n - a\left( {a\left( {n - 1} \right)} \right)\)

Here, \(a\left( {n - 1} \right)\) is well defined and \(a\left( {n - 1} \right) \le n - 1\).

Alos, \(a\left( {a\left( {n - 1} \right)} \right)\) is also well defined as \(a\left( 0 \right),\,a\left( 1 \right),\,...,\,a\left( {n - 1} \right)\) is well defined.

Consider \(a\left( {a\left( {n - 1} \right)} \right)\) is well defined, \(a\left( n \right) = n - a\left( {a\left( {n - 1} \right)} \right)\)is also well defined.

Consider the calculation as follows:

\(\begin{aligned}{l}0 \le a\left( {a\left( {n - 1} \right)} \right) \le n - 1\\ - 0 \ge - a\left( {a\left( {n - 1} \right)} \right) \ge - n + 1\\n - 0 \ge n - a\left( {a\left( {n - 1} \right)} \right) \ge n - n + 1\\1 \le n - a\left( {a\left( {n - 1} \right)} \right) \le n\end{aligned}\)

So, the statement is true for recursive part also.

Therefore the statement is true for both basis and recursive part.

Hence proved.