Chapter 5: Q70SE (page 379)

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))
Find the first 10 terms of the sequence \(\left\{ {a\left( n \right)} \right\}\) defined in the preamble to this exercise.

Expert verified

The first 10 terms of the given sequence are \(0,\;1,\;1,\;2,\;3,\;3,\;4,\;4,\;5,\;6\).

Step by step solution

The sequence is defined as the set of numbers that follows a specific relation between the initial and the next number.

Consider the formula for the sequence is\(a\left( n \right) = n - a\left( {a\left( {n - 1} \right)} \right)\).

Consider the initial term is \(a\left( 0 \right) = 0\).

Determine the first term of the sequence as:

\(\begin{aligned}{c}a\left( 1 \right) &= 1 - a\left( {a\left( 0 \right)} \right)\\ &= 1 - a\left( 0 \right)\\ &= 1 - 0\\ &= 1\end{aligned}\)

Determine the second term of the sequence as:

\(\begin{aligned}{c}a\left( 2 \right) &= 2 - a\left( {a\left( 1 \right)} \right)\\ &= 2 - a\left( 1 \right)\\ &= 2 - 1\\ &= 1\end{aligned}\)

Determine the third term of the sequence as:

\(\begin{aligned}{c}a\left( 3 \right) &= 3 - a\left( {a\left( 2 \right)} \right)\\ &= 3 - a\left( 2 \right)\\ &= 3 - 1\\ &= 2\end{aligned}\)

Determine the fourth term of the sequence as:

\(\begin{aligned}{c}a\left( 4 \right) &= 4 - a\left( {a\left( 3 \right)} \right)\\ &= 4 - a\left( 2 \right)\\ &= 4 - 1\\ &= 3\end{aligned}\)

Determine the fifth term of the sequence as:

\(\begin{aligned}{c}a\left( 5 \right) &= 5 - a\left( {a\left( 4 \right)} \right)\\ &= 5 - a\left( 3 \right)\\ &= 5 - 2\\ &= 3\end{aligned}\)

Determine the sixth term of the sequence as:

\(\begin{aligned}{c}a\left( 6 \right) &= 6 - a\left( {a\left( 5 \right)} \right)\\ &= 6 - a\left( 3 \right)\\ &= 6 - 2\\ &= 4\end{aligned}\)

Determine the seventh term of the sequence as:

\(\begin{aligned}{c}a\left( 7 \right) &= 7 - a\left( {a\left( 6 \right)} \right)\\ &= 7 - a\left( 4 \right)\\ &= 7 - 3\\ &= 4\end{aligned}\)

Determine the eight term of the sequence as:

\(\begin{aligned}{c}a\left( 8 \right) &= 8 - a\left( {a\left( 7 \right)} \right)\\ &= 8 - a\left( 4 \right)\\ &= 8 - 3\\ &= 5\end{aligned}\)

Determine the ninth term of the sequence as:

\(\begin{aligned}{c}a\left( 9 \right) &= 9 - a\left( {a\left( 8 \right)} \right)\\ &= 9 - a\left( 5 \right)\\ &= 9 - 3\\ &= 6\end{aligned}\)

So, the first 10 terms of the given sequence are \(0,\;1,\;1,\;2,\;3,\;3,\;4,\;4,\;5,\;6\).