Volume 5
Summer 2012
Number 1

A Combinatorial interpretation of Hofstadter's

G-Sequence


Mustazee Rahman

Abstract: We give a combinatorial interpretation of a classical meta-Fibonacci sequence de ned 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.