Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In his book Gödel, Escher, Bach Douglas Hofstadter defines the following two integer sequences:
Hofstadter G-sequence: $a(n)=n-a(a(n-1))$
Hofstadter H-sequence: $a(n)=n-a(a(a(n-1)))$
He says recursively built tree structures can be obtained from these sequences by connecting each node $n$ to the node $a(n)$ below it (the procedure is described in detail in the given links). According to Hofstadter, these sequences are a part of a family of sequences $a(n) = n−a(a^k(n−1))$, all of which have the described property. What recursively defined sequences with similar properties are there? Has there been any research on recursively defined trees whose structure can be described by similar recursive functions?
The only relevant research paper I find is A Combinatorial interpretation of Hofstadter's G-sequence by Mustazee Rahman. Do you know any other articles/books/papers on the subject? Any help will be greatly appreciated.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.