|
|
A008352
|
|
a(n) is formed by concatenating a(n-2) and a(n-1), with a(0) = 1, a(1) = 2;
|
|
8
|
|
|
|
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, ...
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
|
|
|
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
|
|
|
|