cp's OEIS Frontend

A005013 a(n) = 3*a(n-2) - a(n-4), a(0)=0, a(1)=1, a(2)=1, a(3)=4. Alternates Fibonacci (A000045) and Lucas (A000032) sequences for even and odd n.

%I A005013 M3214 #119 Feb 16 2025 08:32:28
%S A005013 0,1,1,4,3,11,8,29,21,76,55,199,144,521,377,1364,987,3571,2584,9349,
%T A005013 6765,24476,17711,64079,46368,167761,121393,439204,317811,1149851,
%U A005013 832040,3010349,2178309,7881196,5702887,20633239,14930352,54018521,39088169,141422324
%N A005013 a(n) = 3*a(n-2) - a(n-4), a(0)=0, a(1)=1, a(2)=1, a(3)=4. Alternates Fibonacci (A000045) and Lucas (A000032) sequences for even and odd n.
%C A005013 S(n,sqrt(5)), with the Chebyshev polynomials A049310, is an integer sequence in the real quadratic number field Q(sqrt(5)) with basis numbers <1,phi>, phi:=(1+sqrt(5))/2. S(n,sqrt(5)) = A(n) + 2*B(n)*phi, with A(n)= a(n+1)*(-1)^n and B(n)= A147600(n-1), n>=0, with A147600(-1):=0.
%C A005013 a(n) = p(n+1) where p(x) is the unique degree-(n-1) polynomial such that p(k) = Fibonacci(k) for k = 1, ..., n. - _Michael Somos_, Jan 08 2012
%C A005013 Row sums of A227431. - _Richard R. Forberg_, Jul 29 2013
%C A005013 This is the sequence of Lehmer numbers u_n(sqrt(R),Q) with the parameters R = 5 and Q = 1. It is a strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n,m)) for all natural numbers n and m. The sequence satisfies a linear recurrence of order four. - _Peter Bala_, Apr 18 2014
%C A005013 The sequence of convergents of the 2-periodic continued fraction [0; 1, -5, 1, -5, ...] = 1/(1 - 1/(5 - 1/(1 - 1/(5 - ...)))) = (1/2)*(5 - sqrt(5)) begins [0/1, 1/1, 5/4, 4/3, 15/11, 11/8, 40/29, ...]; the denominators give the present sequence. The sequence of numerators [0, 1, 5, 4, 15, 11, 40, ...] is A203976. Cf. A108412 and A026741. - _Peter Bala_, May 19 2014
%C A005013 Define a binary operation o on the real numbers by x o y = x*sqrt(1 + y^2) + y*sqrt(1 + x^2). The operation o is commutative and associative with identity 0. We have (1/2)*a(2*n + 1) = 1/2 o 1/2 o ... o 1/2 (2*n + 1 terms) and (1/2)*sqrt(5)* a(2*n) = 1/2 o 1/2 o ... o 1/2 (2*n terms). Cf. A084068 and A049629. - _Peter Bala_, Mar 23 2018
%D A005013 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005013 G. C. Greubel, <a href="/A005013/b005013.txt">Table of n, a(n) for n = 0..2000</a> (terms 0..500 from T. D. Noe)
%H A005013 A. F. Horadam, R. P. Loh and A. G. Shannon, <a href="/A005013/a005013.pdf">Divisibility properties of some Fibonacci-type sequences</a>, pp. 55-64 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979. [Annotated scanned copy]
%H A005013 Seong Ju Kim, R. Stees and L. Taalman, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Stees/stees4.html">Sequences of Spiral Knot Determinants</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.1.4.
%H A005013 D. H. Lehmer, <a href="http://www.jstor.org/stable/1968235">An extended theory of Lucas' functions</a>, Annals of Mathematics, Second Series, Vol. 31, No. 3 (Jul., 1930), pp. 419-448.
%H A005013 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A005013 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.
%H A005013 E. L. Roettger and H. C. Williams, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Roettger/roettger12.html">Appearance of Primes in Fourth-Order Odd Divisibility Sequences</a>, J. Int. Seq., Vol. 24 (2021), Article 21.7.5.
%H A005013 E. W. Weisstein, <a href="https://mathworld.wolfram.com/LehmerNumber.html">MathWorld: Lehmer Number</a>
%H A005013 H. C. Williams and R. K. Guy, <a href="https://www.emis.de/journals/INTEGERS/papers/p33/p33.Abstract.html">Odd and even linear divisibility sequences of order 4</a>, INTEGERS, 2015, #A33.
%H A005013 <a href="/index/Di#divseq">Index to divisibility sequences</a>
%H A005013 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,3,0,-1).
%F A005013 a(1) = a(2) = 1, a(3) = 4, a(n) = (a(n-1) * a(n-2) - 1) / a(n-3), unless n=3. a(-n) = -a(n).
%F A005013 a(2n) = A001906(n), a(2n+1) = A002878(n). a(n)=F(n+1)+(-1)^(n+1)F(n-1). - Mario Catalani (mario.catalani(AT)unito.it), Sep 20 2002
%F A005013 G.f.: x*(1+x+x^2)/((1-x-x^2)*(1+x-x^2)).
%F A005013 a(n) = Product_{k=1..floor((n-1)/2)} (1 + 4*sin(k*Pi/n)^2). - _Roger L. Bagula_ and _Gary W. Adamson_, Nov 26 2008
%F A005013 Binomial transform is A096140. - _Michael Somos_, Apr 13 2012
%F A005013 From _Peter Bala_, Apr 18 2014: (Start)
%F A005013 a(n) = (alpha^n - beta^n)/(alpha - beta) for n odd, and a(n) = (alpha^n - beta^n)/(alpha^2 - beta^2) for n even, where alpha = (1/2)*(sqrt(5) + 1) and beta = (1/2)*(sqrt(5) - 1). Equivalently, a(n) = U(n-1, sqrt(5)/2) for n odd and a(n) = (1/sqrt(5))*U(n-1, sqrt(5)/2) for n even, where U(n,x) is the Chebyshev polynomial of the second kind. (End)
%F A005013 E.g.f.: (Phi/sqrt(5))*exp(-Phi*x)*(exp(x)-1)*(exp(sqrt(5)*x) - 1/(Phi)^2), where Phi = (1+sqrt(5))/2. - _G. C. Greubel_, Feb 08 2016
%F A005013 a(n) = (5^floor((n-1)/2)/2^(n-1))*Sum_{k=0..n-1} binomial(n-1,k)/5^floor(k/2). - _Tony Foster III_, Oct 21 2018
%F A005013 a(n) = hypergeom([(1 - n)/2, (n + 1) mod 2 - n/2], [1 - n], -4) for n >= 2. - _Peter Luschny_, Sep 03 2019
%e A005013 G.f. = x + x^2 + 4*x^3 + 3*x^4 + 11*x^5 + 8*x^6 + 29*x^7 + 21*x^8 + 76*x^9 + ...
%e A005013 a(3) = 4 since p(x) = (x^2 - 3*x + 4) / 2 interpolates p(1) = 1, p(2) = 1, p(3) = 2, and p(4) = 4. - _Michael Somos_, Jan 08 2012
%p A005013 with(combinat): A005013 := n-> if n mod 2 = 0 then fibonacci(n) else fibonacci(n+1)+fibonacci(n-1); fi;
%p A005013 A005013:=z*(z**2+z+1)/((z**2+z-1)*(z**2-z-1)); # _Simon Plouffe_ in his 1992 dissertation
%t A005013 CoefficientList[Series[(x + x^2 + x^3)/(1 - 3x^2 + x^4), {x, 0, 40}], x]
%t A005013 f[n_] = Product[(1 + 4*Sin[k*Pi/n]^2), {k, 1, Floor[(n - 1)/2]}]; a = Table[f[n], {n, 0, 30}]; Round[a]; FullSimplify[ExpandAll[a]] (* _Roger L. Bagula_ and _Gary W. Adamson_, Nov 26 2008 *)
%t A005013 LinearRecurrence[{0, 3, 0, -1}, {0, 1, 1, 4}, 100] (* _G. C. Greubel_, Feb 08 2016 *)
%o A005013 (PARI) {a(n) = if( n%2, fibonacci(n+1) + fibonacci(n-1), fibonacci(n))}; /* _Michael Somos_, Jan 08 2012 */
%o A005013 (PARI) {a(n) = if( n<0, -a(-n), subst( polinterpolate( vector( n, k, fibonacci(k))), x, n+1))}; /* _Michael Somos_, Jan 08 2012 */
%o A005013 (Haskell)
%o A005013 a005013 n = a005013_list !! n
%o A005013 a005013_list = alt a000045_list a000032_list where
%o A005013    alt (f:_:fs) (_:l:ls) = f : l : alt fs ls
%o A005013 -- _Reinhard Zumkeller_, Jan 10 2012
%o A005013 (Magma) I:=[0,1,1,4]; [n le 4 select I[n]  else 3*Self(n-2) - Self(n-4): n in [1..40]]; // _Vincenzo Librandi_, Feb 09 2016
%o A005013 (GAP) a:=[0,1,1,4];; for n in [5..40] do a[n]:=3*a[n-2]-a[n-4]; od; a; # _Muniru A Asiru_, Oct 21 2018
%Y A005013 Cf. A000032, A000045, A001906, A002878, A005247, A096140, A026741, A108412, A084068, A049629.
%K A005013 nonn,easy
%O A005013 0,4
%A A005013 _N. J. A. Sloane_
%E A005013 Additional comments from _Michael Somos_, Jun 01 2000