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))

Find the first 10 terms of each of both the sequence \(m\left( n \right)\) and \(f\left( n \right)\) defined by the following pair of interwoven recurrence relations: \(m\left( n \right) = n - f\left( {m\left( {n - 1} \right)} \right)\) for \(n \ge 1\) \(f\left( 0 \right) = 1\) and \(m\left( 0 \right) = 0\).

Short answer

The first 10 terms of sequence\(m\left( n \right)\) are \(0,\,0,\,1,\,2,\,2,\,3,\,4,\,4,\,5,\,6\) and the first 10 terms of sequence\(f\left( n \right)\) are \(1,\,1,\,2,\,2,\,3,\,3,\,4,\,5,\,5,\,6\).

Step-by-step solution

Determine the sequence

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

Consider the sequence formula is:

\(m\left( n \right) = n - f\left( {m\left( {n - 1} \right)} \right)\)when \(n \ge 1\)

\(f\left( n \right) = n - m\left( {f\left( {n - 1} \right)} \right)\) when \(n \ge 1\)

Find the first 10 terms of each of both the sequence  \(m\left( n \right)\) and \(\,f\left( n \right)\)

Consider the initial terms shown below:

\(f\left( 0 \right) = 1\)

\(m\left( 0 \right) = 0\)

Solve for the first term for \(m\left( n \right)\) as:

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

Solve for the first term for \(f\left( n \right)\) as:

\(\begin{aligned}{c}f\left( 1 \right) = 1 - m\left( {f\left( 0 \right)} \right)\\ = 1 - m\left( 1 \right)\\ = 1 - 0\\ = 1\end{aligned}\)

Solve for the second term for \(m\left( n \right)\) as:

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

Solve for the second term for \(f\left( n \right)\) as:

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

Solve for the third term for \(m\left( n \right)\) as:

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

Solve for the third term for \(f\left( n \right)\) as:

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

Solve for the fourth term for \(m\left( n \right)\) as:

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

Solve for the fourth term for \(f\left( n \right)\) as:

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

Solve for the fifth term for \(m\left( n \right)\) as:

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

Solve for the fifth term for \(f\left( n \right)\) as:

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

Solve for the sixth term for \(m\left( n \right)\) as:

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

Solve for the sixth term for \(f\left( n \right)\) as:

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

Solve for the seventh term for \(m\left( n \right)\) as:

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

Solve for the seventh term for \(f\left( n \right)\) as:

\(\begin{aligned}{c}f\left( 7 \right) &= 7 - m\left( {f\left( 6 \right)} \right)\\ &= 7 - m\left( 4 \right)\\ &= 7 - 2\\ &= 5\end{aligned}\)

Solve for the eighth term for \(m\left( n \right)\) as:

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

Solve for the eighth term for \(f\left( n \right)\) as:

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

Solve for the ninth term for \(m\left( n \right)\) as:

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

Solve for the ninth term for \(f\left( n \right)\) as:

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

Hence, the first 10 terms of sequence\(m\left( n \right)\) are \(0,\,0,\,1,\,2,\,2,\,3,\,4,\,4,\,5,\,6\) and the first 10 terms of sequence\(f\left( n \right)\) are \(1,\,1,\,2,\,2,\,3,\,3,\,4,\,5,\,5,\,6\).