zbMATH — the first resource for mathematics

Intertwined infinite binary words. (English) Zbl 0856.68117
Summary: In [\((*)\) “Gödel, Escher, Bach. An Eternal Golden Braid” (New York, 1979)] D. Hofstadter defines the sequence \(h(n)\) by \[ h(n)= n- h(h(n- 1)),\quad n> 1,\tag{1} \] with \(h(1)= 1\) and remarks on its close relation to the sequence \(F_n\) of Fibonacci numbers given by the well-known formula \[ F_n= F_{n- 1}+ F_{n- 2},\quad n> 2,\tag{2} \] with \(F_1= F_2= 1\). As it was proved by P. J. Downey and R. E. Griswold [“On a family of nested recurrences”, Fibonacci Q. 22, 310-317 (1984; Zbl 0547.10009)], \[ h(n)= F_{r- 1}+ F_{s- 1}+\cdots+ F_{t- 1},\quad n> 1,\tag{3} \] if \(n= F_r+ F_s+\cdots+ F_t\) is the Zeckendorf expansion of \(n\). Moreover, an explicit formula \[ h(n)= [\mu(n+ 1)],\quad n> 0,\tag{4} \] was found there, where \([.]\) denotes the greatest integer function and \(\mu= (- 1+ \sqrt 5)/2\) is the golden ratio. Similar but less known “married” sequences \(f(n)\) and \(g(n)\) defined by \[ f(n)= n- g(f(n- 1)),\quad g(n)= n- f(g(n- 1)),\quad n> 0,\tag{5} \] with \(f(0)= 1\), \(g(0)= 0\) are introduced also in \((*)\).
In this note, we generalize sequences (1) and (5) and derive an asymptotic result for new sequences. However, we shall come to our generalization from quite a different side, namely, from cryptography and symbolic dynamics.

68R15 Combinatorics on words
11B83 Special sequences and polynomials
Full Text: DOI
[1] Andrasiu, M; Paun, G; Dassow, J; Salomaa, A, Language-theoretic problems arising from richelieu cryptosystems, Theoret. comput. sci., 116, 339-357, (1993) · Zbl 0797.68094
[2] K. Dilcher, On a class of iterative recurrence relations, Fibonacci Quart., to appear. · Zbl 0804.11009
[3] Downey, P.J; Griswold, R.E, On a family of nested recurrences, Fibonacci quart., 22, 310-317, (1984) · Zbl 0547.10009
[4] Fürstenberg, H, Recurrence in ergodic theory and combinatorial number theory, (1981), Princeton Univ. Press Princeton, NJ · Zbl 0459.28023
[5] Fürstenberg, H, Poincaré recurrence and number theory, Bull. amer. math. soc. (new series), 5, 211-234, (1981) · Zbl 0481.28013
[6] Fürstenberg, H; Katznelson, Y, A density version of the hales-jewett theorem for k = 3, Discrete math., 75, 227-241, (1989) · Zbl 0697.05006
[7] Granville, V; Rasson, J.P, A strange recursive relation, J. number theory, 30, 238-241, (1988) · Zbl 0653.10008
[8] Grytczuk, J, Self-similar words and meta-Fibonacci sequences, ()
[9] J. Grytczuk, Self-similar words, Discrete Math., to appear. · Zbl 0873.68172
[10] Hofstadter, D, Gödel, escher, bach. an eternal Golden braid, (1979), Basic Books New York · Zbl 1014.03005
[11] Leveque, W.J, Fundamentals of number theory, (1977), Addison-Wesley Reading, MA · Zbl 0368.10001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.