A008352 a(n) is formed by concatenating a(n-2) and a(n-1), with a(0) = 1, a(1) = 2.

1, 2, 12, 212, 12212, 21212212, 1221221212212, 212122121221221212212, 1221221212212212122121221221212212, 2121221212212212122121221221212212212122121221221212212

Offset: 0

Author

N. J. A. Sloane and J. H. Conway

Keywords

• nonn
• base

Comments

A "non-commutative Fibonacci" (or "reverse Fibonacci") sequence. Often written as: a, b, ab, bab, abbab, bababbab, abbabbababbab, bababbababbabbababbab, abbabbababbabbababbababbabbababbab, bababbababbabbababbababbabbababbabbababbababbabbababbab, ...

Converges in the appropriate topology. - Dylan Thurston, Jan 28 2005

Do a web search on bababbababbabbababbab to get further links.

From Andrew Hone, Jan 28 2005: (Start)

Write the recurrence symbolically as g_{n+1} = g_{n-1}g_n. Then the determinant d_n = det g_n is given by d_n = d_0^{f_{n-2}} d_1^{f_{n-1}} where f_{n+1} = f_n+f_{n-1}, f_0 = f_1 = 1 are the Fibonacci numbers.

To avoid getting involved with the Baker-Campbell-Hausdorff identity, I now restrict to SL(2), or to make life easier make it SU(2) (which is isomorphic over C). Then we can explicitly write g as an exponential of Lie algebra elements:

g_n = exp (i theta_n v_n cdot sigma ), where theta_n is an angle, v_n is a unit vector and sigma = ( sigma_1, sigma_2, sigma_3)^T is a vector of Pauli spin matrices.

Moreover the adjoint action on su(2) (viewing the coordinates in su(2) as giving points in 3D space) means that g_n gives a rotation through - theta_n /2 about the v_n axis.

So from the double cover of SO(3) by SU(2), we can view the g_n as a sequence of "Fibonacci rotations."

Furthermore, in SU(2) we can write explicitly g_n = cos theta_n + i sin theta_n v_n cdot sigma so the recurrence can be decoupled as

cos theta_{n+1} = cos theta_n + cos theta_{n-1} - sin theta_{n-1} sin theta_n (v_{n-1} cdot v_n),

sin theta_{n+1} v_{n+1} = cos theta_{n-1} sin theta_n v_n + cos theta_n sin theta_{n-1} v_{n-1} - sin theta_{n-1} sin theta_n ( v_{n-1} wedge v_n ). (End)

Changing the offset to 1, the sum of the digits of a(n) is 2*Fib(n-1)+Fib(n-2), where Fib(n) means A000045(n), the n-th Fibonacci number. - Stefan Steinerberger, Feb 05 2006

Let beta be the reversed, mirrored Fibonacci morphism on the alphabet {1,2} given by beta(1)=2, beta(2)=12. Then a(n) = beta^n(1), since from the formula beta^2(1)= 12 = 1 beta(1), one sees directly that the iterates of the letter 1 under beta satisfy the defining recursion a(n) = a(n-2)a(n-1). It follows that the a(2n) converge to A189479 with 1,2 replaced by 0 and 1, and the a(2n+1) converge to A287523 with 1,2 replaced by 0 and 1. - Michel Dekking, Sep 30 2019

References

• D. E. Knuth, "The Art of Programming", Volume 1, "Fundamental Algorithms", third edition, problem 36 on page 86.

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..15
• Jean Berstel, Fibonacci words—a survey, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
• S. Brlek, E. Duchi, E. Pergola and S. Rinaldi, On the equivalence problem for succession rules, Discr. Math., 298 (2005), 142-154.
• C. Delorme, Sequence of maximal distance codes in graphs or other metric spaces, Electronic Journal of Graph Theory and Applications 1 (2) (2013), 118-124.
• K. B. Stolarsky, Beatty sequences, continued fractions, and certain shift operators, Canadian Math. Bull. 19 (1976) pp. 473-482.
• A. Vieru, Lindenmayer systems and primes, arXiv:math.NT/0803.0852 [math.NT], 2008.
• Wikipedia, Lindenmayer system

Crossrefs

See A008351 and A003849 for other versions.

Cf. A000045, A113773, A133235.

Programs

Maple

f:=proc(n) option remember; if n = 0 then return(`1`); fi; if n = 1 then return(`2`); fi; cat(f(n-2), f(n-1) ); end;

Mathematica

nxt[{a_,b_}]:={b,FromDigits[Join[IntegerDigits[a],IntegerDigits[b]]]}; NestList[ nxt,{1,2},10][[All,1]] (* Harvey P. Dale, Jul 16 2017 *)

Formula

With offset set to 1, a(1)=1 and a(2)=2, then a(n) = a(n-1)+10^A000045(n)*a(n-2). - Benoit Cloitre, Nov 24 2001

a(n) = beta^n(1), where beta is the morphism 1->2, 2->12. - Michel Dekking, Sep 30 2019