arXiv:1105.1718 [math.CO]AbstractReferencesReviewsResources
A Combinatorial interpretation of Hofstadter's G-sequence
Published 2011-05-09, updated 2013-06-16Version 3
We give a combinatorial interpretation of a classical meta-Fibonacci sequence defined 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 few corollaries about the behaviour of the sequence G(n) directly from the interpretation.
Comments: 7 pages, 1 figure. Version 3 has some crucial typos fixed
Categories: math.CO
Related articles: Most relevant | Search more
A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence
arXiv:1907.06517 [math.CO] (Published 2019-07-15)
A new combinatorial interpretation of the Fibonacci numbers squared
A combinatorial interpretation of the $κ^{\star}_{g}(n)$ coefficients