Abstract:
We give a combinatorial interpretation of a classical meta-Fibonacci sequence
dened by $G(n) = n - G(G(n - 1))$ with the initial condition $G(1) = 1$, which
appears in Hofstadter's "Godel, Escher, Bach: An Eternal Golden Braid". The interpretation
is in terms of an infinite labelled tree. We then show a couple of corollaries about
the behaviour of the sequence $G(n)$ directly from the interpretation.