A053602 - OEIS

%I #71 Jan 05 2025 19:51:36

%S 0,1,1,2,1,3,2,5,3,8,5,13,8,21,13,34,21,55,34,89,55,144,89,233,144,

%T 377,233,610,377,987,610,1597,987,2584,1597,4181,2584,6765,4181,10946,

%U 6765,17711,10946,28657,17711,46368,28657,75025,46368,121393,75025

%N a(n) = a(n-1) - (-1)^n*a(n-2), a(0)=0, a(1)=1.

%C If b(0)=0, b(1)=1 and b(n) = b(n-1) + (-1)^n*b(n-2), then a(n) = b(n+3). - _Jaume Oliver Lafont_, Oct 03 2009

%C a(n) is the number of palindromic compositions of n-1 into parts of 1 and 2. a(7) = 5 because we have 2+2+2, 2+1+1+2, 1+2+2+1, 1+1+2+1+1, 1+1+1+1+1+1. - _Geoffrey Critzer_, Mar 17 2014

%C a(n) is the number of palindromic compositions of n into odd parts (the corresponding generating function follows easily from Theorem 1.2 of the Hoggatt et al. reference). Example: a(7) = 5 because we have 7, 1+5+1, 3+1+3, 1+1+3+1+1, 1+1+1+1+1+1+1. - _Emeric Deutsch_, Aug 16 2016

%C The ratio of a(n)/a(n-1) oscillates between phi-1 and phi+1 as n tends to infinity, where phi is golden ratio (A001622). - _Waldemar Puszkarz_, Oct 10 2017

%H Vincenzo Librandi, <a href="/A053602/b053602.txt">Table of n, a(n) for n = 0..1000</a>

%H Krithnaswami Alladi and V. E. Hoggatt, Jr. <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/13-3/alladi1.pdf">Compositions with Ones and Twos</a>, Fibonacci Quarterly, 13 (1975), 233-239. - _Ron Knott_, Oct 29 2010

%H A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, et al., <a href="http://www.fmf.uni-lj.si/~klavzar/preprints/Fib-Luc-orbits-August-11-2014.pdf">Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings</a>, 2014.

%H V. E. Hoggatt, Jr., and Marjorie Bicknell, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/13-4/hoggatt1.pdf">Palindromic compositions</a>, Fibonacci Quart., Vol. 13(4), 1975, pp. 350-356.

%H M. A. Nyblom, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL16/Nyblom/nyblom13.html">Counting Palindromic Binary Strings Without r-Runs of Ones</a>, J. Int. Seq. 16 (2013) #13.8.7

%H <a href="/index/Tu#2wis">Index entries for two-way infinite sequences</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,0,1)

%F G.f.: x*(1 + x + x^2)/(1 - x^2 - x^4).

%F a(n) = a(n-2) + a(n-4).

%F a(2n) = F(n), a(2n-1) = F(n+1) where F() is Fibonacci sequence.

%F a(3-n) = A051792(n).

%F a(3)=1, a(4)=2, a(n+2) = a(n+1) + sign(a(n) - a(n+1))*a(n), n > 4. - _Benoit Cloitre_, Apr 08 2002

%F a(n) = A079977(n-1) + A079977(n-2) + A079977(n-3), n > 2. - _Ralf Stephan_, Apr 26 2003

%F a(0) = 0, a(1) = 1; a(2n) = a(2n-1) - a(2n-2); a(2n+1) = a(2n) + a(2n-1). - _Amarnath Murthy_, Jul 21 2005

%p a[0] := 0: a[1] := 1: for n from 2 to 60 do a[n] := a[n-1]-(-1)^n*a[n-2] end do: seq(a[n], n = 0 .. 50); # _Emeric Deutsch_, Oct 09 2017

%t nn=50;CoefficientList[Series[x (1+x+x^2)/(1-x^2-x^4),{x,0,nn}],x] (* _Geoffrey Critzer_, Mar 17 2014 *)

%t LinearRecurrence[{0,1,0,1},{0,1,1,2},60] (* _Harvey P. Dale_, Nov 07 2016 *)

%t RecurrenceTable[{a[0]==0, a[1]==1, a[n]==a[n-1]-(-1)^n a[n-2]}, a, {n, 50}] (* _Vincenzo Librandi_, Oct 10 2017 *)

%o (PARI) a(n)=fibonacci(n\2+n%2*2)

%o (Magma) I:=[0,1,1,2]; [n le 4 select I[n] else Self(n-2)+Self(n-4): n in [1..50]]; // _Vincenzo Librandi_ Oct 10 2017

%o (SageMath) [fibonacci(n//2 + 2*(n%2)) for n in range(61)] # _G. C. Greubel_, Dec 06 2022

%Y Cf. A000045, A001622, A051792, A079977.

%K nonn,easy

%O 0,4

%A _Michael Somos_, Jan 17 2000