OFFSET
0,2
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.
Comments from A. N. W. 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
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
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 *)
CROSSREFS
KEYWORD
nonn,base
AUTHOR
STATUS
approved