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

Use the formula from exercise 72 to show that \(a\left( n \right) = a\left( {n - 1} \right)\) if \(\mu n - \left\lfloor {\mu n} \right\rfloor < 1 - \mu \) and \(a\left( n \right) = a\left( {n - 1} \right) + 1\) otherwise.

Short answer

It is proved that\(a\left( n \right) = a\left( {n - 1} \right)\)for \(\mu n - \left\lfloor {\mu n} \right\rfloor < 1 - \mu \)

It is proved that \(a\left( n \right) = a\left( {n - 1} \right) + 1\) for \(\mu n - \left\lfloor {\mu n} \right\rfloor \ge 1 - \mu \)

Step-by-step solution

Formula obtained in exercise 72

Consider the formula for the sequence as:

\(a\left( n \right) = \left\lfloor {\left( {n + 1} \right)\mu } \right\rfloor \)where\(\mu = {{\left( { - 1 + \sqrt 5 } \right)} \mathord{\left/

{\vphantom {{\left( { - 1 + \sqrt 5 } \right)} 2}} \right.

\kern-\nulldelimiterspace} 2}\)

Showing that \(a\left( n \right) = a\left( {n - 1} \right)\) if \(\mu n - \left\lfloor {\mu n} \right\rfloor  < 1 - \mu \)

Here we have,\(a\left( n \right) = n - a\left( {a\left( {n - 1} \right)} \right)\)when \(n \ge 0\) and \(a\left( 0 \right) = 0\)

Also, \(a\left( n \right) = \left\lfloor {\left( {n + 1} \right)\mu } \right\rfloor \) for \(\mu = \frac{{ - 1 + \sqrt 5 }}{2}\)

Consider the relation:

\(\begin{aligned}{l}\mu n - \left\lfloor {\mu n} \right\rfloor < 1 - \mu \\\mu n + \mu < 1 + \left\lfloor {\mu n} \right\rfloor \\\left\lfloor {\mu n + \mu } \right\rfloor = \left\lfloor {\mu n} \right\rfloor \end{aligned}\)

Now:

\(\begin{aligned}{c}a\left( n \right) &= \left\lfloor {\left( {n + 1} \right)\mu } \right\rfloor \\ &= \left\lfloor {n\mu + \mu } \right\rfloor \\ &= \left\lfloor {n\mu } \right\rfloor \\ &= a\left( {n - 1} \right)\end{aligned}\)

So, \(a\left( n \right) = a\left( {n - 1} \right)\) for \(\mu n - \left\lfloor {\mu n} \right\rfloor < 1 - \mu \)

Hence proved.

Showing that \(a\left( n \right) = a\left( {n - 1} \right) + 1\) if \(\mu n - \left\lfloor {\mu n} \right\rfloor  \ge 1 - \mu \)

Consider the relation:

\(\begin{aligned}{l}\mu n - \left\lfloor {\mu n} \right\rfloor \ge 1 - \mu \\\mu n + \mu \ge 1 + \left\lfloor {\mu n} \right\rfloor \\\left\lfloor {\mu n + \mu } \right\rfloor = \left\lfloor {\mu n} \right\rfloor + 1\end{aligned}\)

Solve for the sequence as:

\(\begin{aligned}{c}a\left( n \right) &= \left\lfloor {\left( {n + 1} \right)\mu } \right\rfloor \\ &= \left\lfloor {n\mu + \mu } \right\rfloor \\ &= \left\lfloor {n\mu } \right\rfloor + 1\\ &= a\left( {n - 1} \right) + 1\end{aligned}\)

So, \(a\left( n \right) = a\left( {n - 1} \right) + 1\) for \(\mu n - \left\lfloor {\mu n} \right\rfloor \ge 1 - \mu \)

Hence proved.