|
%I M2844 #305 Jan 22 2024 05:46:14
%S 0,1,3,10,33,109,360,1189,3927,12970,42837,141481,467280,1543321,
%T 5097243,16835050,55602393,183642229,606529080,2003229469,6616217487,
%U 21851881930,72171863277,238367471761,787274278560,2600190307441
%N a(n) = 3*a(n-1) + a(n-2), with a(0)=0, a(1)=1.
%C Denominators of continued fraction convergents to (3+sqrt(13))/2. - _Benoit Cloitre_, Jun 14 2003
%C a(n) and A006497(n) occur in pairs: (a,b): (1,3), (3,11), (10,36), (33,119), (109,393), ... such that b^2 - 13a^2 = 4(-1)^n. - _Gary W. Adamson_, Jun 15 2003
%C Form the 4-node graph with matrix A = [1,1,1,1; 1,1,1,0; 1,1,0,1; 1,0,1,1]. Then this sequence counts the walks of length n from the vertex with degree 5 to one (any) of the other vertices. - _Paul Barry_, Oct 02 2004
%C a(n+1) is the binomial transform of A006138. - _Paul Barry_, May 21 2006
%C a(n+1) is the diagonal sum of the exponential Riordan array (exp(3x),x). - _Paul Barry_, Jun 03 2006
%C Number of paths in the right half-plane from (0,0) to the line x=n-1, consisting of steps U=(1,1), D=(1,-1), h=(1,0) and H=(2,0). Example: a(3)=10 because we have hh, H, UD, DU, hU, Uh, UU, hD, Dh and DD. - _Emeric Deutsch_, Sep 03 2007
%C a(p) == 13^((p-1)/2)) mod p, for odd primes p. - _Gary W. Adamson_, Feb 22 2009
%C Equals INVERT transform of A000129. Example: a(5) = 109 = (29, 12, 5, 2, 1) dot (1, 1, 3, 10, 33) = (29 + 12 + 15 + 20 + 33). - _Gary W. Adamson_, Aug 06 2010
%C For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 3's along the main diagonal, 1's along the superdiagonal and subdiagonal, and 0's everywhere else. - _John M. Campbell_, Jul 08 2011
%C These numbers could also be called "bronze Fibonacci numbers". Indeed, for n >= 1, F(n+1) = ceiling(phi*F(n)), if n is even and F(n+1) = floor(phi*F(n)), if n is odd, where phi is the golden ratio; analogously, for Pell numbers (A000129), or "silver Fibonacci numbers", P(n+1) = ceiling(delta*a(n)), if n is even and P(n+1) = floor(delta*a(n)), if n is odd, where delta = delta_S = 1 + sqrt(2) is the silver ratio. Here, for n >= 1, we have a(n+1) = ceiling(c*a(n)), if n is even and a(n+1) = floor(c*a(n)), if n is odd, where c = (3 + sqrt(13))/2 is the bronze ratio (cf. comment in A098316). - _Vladimir Shevelev_, Feb 23 2013
%C Let p(n,x) denote the Fibonacci polynomial, defined by p(1,x) = 1, p(2,x) = x, p(n,x) = x*p(n-1,x) + p(n-2,x). Let q(n,x) be the numerator polynomial of the rational function p(n, x + 1 + 1/x). Then q(n,1) = a(n). - _Clark Kimberling_, Nov 04 2013
%C The (1,1)-entry of the matrix A^n where A = [0,1,0; 1,2,1; 1,1,2]. - _David Neil McGrath_, Jul 18 2014
%C a(n+1) counts closed walks on K2, containing three loops on the other vertex. Equivalently the (1,1)-entry of A^(n+1) where the adjacency matrix of digraph is A = (0,1; 1,3). - _David Neil McGrath_, Oct 29 2014
%C For n >= 1, a(n) equals the number of words of length n-1 on alphabet {0,1,2,3} avoiding runs of zeros of odd lengths. - _Milan Janjic_, Jan 28 2015
%C With offset 1 is the INVERTi transform of A001076. - _Gary W. Adamson_, Jul 24 2015
%C Apart from the initial 0, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = 1 - 3 S. See A291219. - _Clark Kimberling_, Sep 02 2017
%C From _Rogério Serôdio_, Mar 30 2018: (Start)
%C This is a divisibility sequence (i.e., if n|m then a(n)|a(m)).
%C gcd(a(n),a(n+k)) = a(gcd(n, k)) for all positive integers n and k. (End)
%C Numbers of straight-chain fatty acids involving oxo and/or hydroxy groups, if cis-/trans isomerism and stereoisomerism are neglected. - _Stefan Schuster_, Apr 04 2018
%C Number of 3-compositions of n restricted to odd parts (and allowed zeros); see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C From _Michael A. Allen_, Jan 25 2023: (Start)
%C Also called the 3-metallonacci sequence; the g.f. 1/(1-k*x-x^2) gives the k-metallonacci sequence.
%C a(n+1) is the number of tilings of an n-board (a board with dimensions n X 1) using unit squares and dominoes (with dimensions 2 X 1) if there are 3 kinds of squares available. (End)
%C a(n) is the number of compositions of n when there are P(k) sorts of parts k, with k,n >= 1, P(k) = A000129(k) is the k-th Pell number (see example below). - _Enrique Navarrete_, Dec 15 2023
%D H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
%D A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 128.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D L.-N. Machaut, Query 3436, L'Intermédiaire des Mathématiciens, 16 (1909), 62-63. - _N. J. A. Sloane_, Mar 08 2022
%H G. C. Greubel, <a href="/A006190/b006190.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..200 from T. D. Noe)
%H H. L. Abbott and D. Hanson, <a href="/A006189/a006189.pdf">A lattice path problem</a>, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
%H Michael A. Allen and Kenneth Edwards, <a href="https://www.fq.math.ca/Papers1/60-5/allen.pdf">Fence tiling derived identities involving the metallonacci numbers squared or cubed</a>, Fib. Q. 60:5 (2022) 5-17.
%H Dorin Andrica, Ovidiu Bagdasar, and George Cătălin Tųrcąs, <a href="https://doi.org/10.2478/auom-2021-0002">On some new results for the generalised Lucas sequences</a>, An. Şt. Univ. Ovidius Constanţa (Romania, 2021) Vol. 29, No. 1, 17-36.
%H Ayoub B. Ayoub, <a href="http://www.jstor.org/stable/27646417">Fibonacci-like sequences and Pell equations</a>, The College Mathematics Journal, Vol. 38 (2007), pp. 49-53.
%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 8.
%H Henrique F. da Cruz, Ilda Inácio, and Rogério Serôdio, <a href="https://doi.org/10.26493/1855-3974.1477.1c7">Convertible subspaces that arise from different numberings of the vertices of a graph</a>, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 473-486.
%H Colin Defant, <a href="https://arxiv.org/abs/2104.03890">Meeting Covered Elements in nu-Tamari Lattices</a>, arXiv:2104.03890 [math.CO], 2021.
%H Sergio Falcon, <a href="http://saspublisher.com/wp-content/uploads/2014/06/SJET24C669-675.pdf">On The Generating Functions of the Powers of the K-Fibonacci Numbers</a>, Scholars Journal of Engineering and Technology (SJET), 2014; 2 (4C):669-675.
%H Sergio Falcon, <a href="http://dx.doi.org/10.1016/j.chaos.2016.03.038">The k-Fibonacci difference sequences</a>, Chaos, Solitons & Fractals, Volume 87, June 2016, Pages 153-157.
%H M. C. Firengiz and A. Dil, <a href="http://www.nntdm.net/papers/nntdm-20/NNTDM-20-4-21-32.pdf">Generalized Euler-Seidel method for second order recurrence relations</a>, Notes on Number Theory and Discrete Mathematics, Vol. 20, 2014, No. 4, 21-32.
%H Juan B. Gil and Aaron Worley, <a href="https://arxiv.org/abs/1901.02619">Generalized metallic means</a>, arXiv:1901.02619 [math.NT], 2019.
%H Brian Hopkins and Stéphane Ouvry, <a href="https://arxiv.org/abs/2008.04937">Combinatorics of Multicompositions</a>, arXiv:2008.04937 [math.CO], 2020.
%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/15-4/horadam.pdf">Generating identities for generalized Fibonacci and Lucas triples</a>, Fib. Quart., 15 (1977), 289-292.
%H Haruo Hosoya, <a href="http://www.hyle.org/journal/issues/19-1/hosoya.htm">What Can Mathematical Chemistry Contribute to the Development of Mathematics?</a>, HYLE--International Journal for Philosophy of Chemistry, Vol. 19, No.1 (2013), pp. 87-105.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=158">Encyclopedia of Combinatorial Structures 158</a>
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Janjic/janjic33.html">Hessenberg Matrices and Integer Sequences </a>, J. Int. Seq. 13 (2010) # 10.7.8, section 3.
%H Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H W. F. Klostermeyer, M. E. Mays, L. Soltes and G. Trapp, <a href="http://www.fq.math.ca/Scanned/35-4/klostermeyer.pdf">A Pascal rhombus</a>, Fibonacci Quarterly, 35 (1976), 318-328.
%H Pablo Lam-Estrada, Myriam Rosalía Maldonado-Ramírez, José Luis López-Bonilla, and Fausto Jarquín-Zárate, <a href="https://arxiv.org/abs/1904.13002">The sequences of Fibonacci and Lucas for each real quadratic fields Q(Sqrt(d))</a>, arXiv:1904.13002 [math.NT], 2019.
%H 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 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H S. Schuster, M. Fichtner and S. Sasso, <a href="https://www.nature.com/articles/srep39821.pdf">Use of Fibonacci numbers in lipidomics - Enumerating various classes of fatty acids</a>, Sci. Rep., 7 (2017) 39821.
%H Kai Wang, <a href="https://www.researchgate.net/publication/339487198_On_k-Fibonacci_Sequences_And_Infinite_Series_List_of_Results_and_Examples">On k-Fibonacci Sequences And Infinite Series List of Results and Examples</a>, 2020.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,1).
%F G.f.: x/(1 - 3*x - x^2).
%F From _Benoit Cloitre_, Jun 14 2003
%F a(3*n) = 2*A041019(5*n-1), a(3*n+1) = A041019(5*n), a(3*n+2) = A041019(5*n+3).
%F a(2*n) = 3*A004190(n-1); a(3*n) = 10*A041613(n-1) for n >= 1. (End)
%F From _Gary W. Adamson_, Jun 15 2003: (Start)
%F a(n-1) + a(n+1) = A006497(n).
%F A006497(n)^2 - 13*a(n)^2 = 4(-1)^n. (End)
%F a(n) = U(n-1, (3/2)i)(-i)^(n-1), i^2 = -1. - _Paul Barry_, Nov 19 2003
%F a(n) = Sum_{k=0..n-1} binomial(n-k-1,k)*3^(n-2*k-1). - _Paul Barry_, Oct 02 2004
%F a(n) = F(n, 3), the n-th Fibonacci polynomial evaluated at x=3.
%F Let M = {{0, 1}, {1, 3}}, v[1] = {0, 1}, v[n] = M.v[n - 1]; then a(n) = Abs[v[n][[1]]]. - _Roger L. Bagula_, May 29 2005 [Or a(n) = [M^(n+1)]_{1,1}. - _L. Edson Jeffery_, Aug 27 2013
%F From _Paul Barry_, May 21 2006: (Start)
%F a(n+1) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(k-j).
%F a(n) = Sum_{k=0..n} Sum_{j=0..n-k} C(k,j)*C(n-j,k)*2^(n-j-k).
%F a(n+1) = Sum_{k=0..floor(n/2)} C(n-k,k)*3^(n-2*k).
%F a(n) = Sum_{k=0..n} C(k,n-k)*3^(2*k-n). (End)
%F E.g.f.: exp(3*x/2)*sinh(sqrt(13)*x/2)/(sqrt(13)/2). - _Paul Barry_, Jun 03 2006
%F a(n) = (ap^n - am^n)/(ap - am), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2.
%F Let C = (3 + sqrt(13))/2 = exp arcsinh(3/2) = 3.3027756377... Then C^n, n > 0 = a(n)*(1/C) + a(n+1). Let X = the 2 X 2 matrix [0, 1; 1, 3]. Then X^n = [a(n-1), a(n); a(n), a(n+1)]. - _Gary W. Adamson_, Dec 21 2007
%F 1/3 = 3/(1*10) + 3/(3*33) + 3/(10*109) + 3/(33*360) + 3/(109*1189) + ... . - _Gary W. Adamson_, Mar 16 2008
%F a(n) = ((3 + sqrt(13))^n - (3 - sqrt(13))^n)/(2^n*sqrt(13)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009
%F From _Johannes W. Meijer_, Jun 12 2010: (Start)
%F Limit_{k->infinity} a(n+k)/a(k) = (A006497(n) + a(n)*sqrt(13))/2.
%F Limit_{n->infinity} A006497(n)/a(n) = sqrt(13).
%F (End)
%F Sum_{k>=1} (-1)^(k-1)/(a(k)*a(k+1)) = (sqrt(13)-3)/2. - _Vladimir Shevelev_, Feb 23 2013
%F From _Vladimir Shevelev_, Feb 24 2013: (Start)
%F (1) Expression a(n+1) via a(n): a(n+1) = (3*a(n) + sqrt(13*a^2(n) + 4*(-1)^n)/2;
%F (2) a^2(n+1) - a(n)*a(n+2) = (-1)^n;
%F (3) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
%F (4) a(n)/a(n+1) = (sqrt(13)-3)/2 + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
%F a(n) = sqrt(13*(A006497(n))^2 + (-1)^(n-1)*52)/13. - _Vladimir Shevelev_, Mar 13 2013
%F Sum_{n >= 1} 1/( a(2*n) + 1/a(2*n) ) = 1/3; Sum_{n >= 1} 1/( a(2*n + 1) - 1/a(2*n + 1) ) = 1/9. - _Peter Bala_, Mar 26 2015
%F From _Rogério Serôdio_, Mar 30 2018: (Start)
%F Some properties:
%F (1) a(n)*a(n+1) = 3*Sum_{k=1..n} a(k)^2;
%F (2) a(n)^2 + a(n+1)^2 = a(2*n+1);
%F (3) a(n)^2 - a(n-2)^2 = 3*a(n-1)*(a(n) + a(n-2));
%F (4) a(m*(p+1)) = a(m*p)*a(m+1) + a(m*p-1)*a(m);
%F (5) a(n-k)*a(n+k) = a(n)^2 + (-1)^(n+k+1)*a(k)^2;
%F (6) a(2*n) = a(n)*(3*a(n) + 2*a(n-1));
%F (7) 3*Sum_{k=2..n+1} a(k)*a(k-1) is equal to a(n+1)^2 if n odd, and is equal to a(n+1)^2 - 1 if n is even;
%F (8) a(n) - a(n-2*k+1) = alpha(k)*a(n-2*k+1) + a(n-4*k+2), where alpha(k) = (ap^(2*k-1) + am^(2*k-1), with ap = (3 + sqrt(13))/2, am = (3 - sqrt(13))/2;
%F (9) 131|Sum_{k=n..n+9} a(k), for all positive n. (End)
%F From _Kai Wang_, Feb 10 2020: (Start)
%F a(n)^2 - a(n+r)*a(n-r) = (-1)^(n-r)*a(r)^2 - Catalan's identity.
%F arctan(1/a(2n)) - arctan(1/a(2n+2)) = arctan(a(2)/a(2n+1)).
%F arctan(1/a(2n)) = Sum_{m>=n} arctan(a(2)/a(2m+1)).
%F The same formula holds for Fibonacci numbers and Pell numbers. (End)
%F a(n+2) = 3^(n+1) + Sum_{k=0..n} a(k)*3^(n-k). - _Greg Dresden_ and Gavron Campbell, Feb 22 2022
%F G.f. = 1/(1-Sum_{k>=1} P(k)*x^k), P(k)=A000129(k) (with a(0)=1). - _Enrique Navarrete_, Dec 17 2023
%e From _Enrique Navarrete_, Dec 15 2023: (Start)
%e From the comment on compositions with Pell number of parts, A000129(k), there are A000129(1)=1 type of 1, A000129(2)=2 types of 2, A000129(3)=5 types of 3, A000129(4)=12 types of 4, A000129(5)=29 types of 5 and A000129(6)=70 types of 6.
%e The following table gives the number of compositions of n=6:
%e Composition, number of such compositions, number of compositions of this type:
%e 6, 1, 70;
%e 5+1, 2, 58;
%e 4+2, 2, 48;
%e 3+3, 1, 25;
%e 4+1+1, 3, 36;
%e 3+2+1, 6, 60;
%e 2+2+2, 1, 8;
%e 3+1+1+1, 4, 20;
%e 2+2+1+1, 6, 24;
%e 2+1+1+1+1, 5, 10;
%e 1+1+1+1+1+1, 1, 1;
%e for a total of a(6)=360 compositions of n=6. (End).
%p a[0]:=0: a[1]:=1: for n from 2 to 35 do a[n]:= 3*a[n-1]+a[n-2] end do: seq(a[n],n=0..30); # _Emeric Deutsch_, Sep 03 2007
%p A006190:=-1/(-1+3*z+z**2); # _Simon Plouffe_ in his 1992 dissertation, without the leading 0
%p seq(combinat[fibonacci](n,3),n=0..30); # _R. J. Mathar_, Dec 07 2011
%t a[n_] := (MatrixPower[{{1, 3}, {1, 2}}, n].{{1}, {1}})[[2, 1]]; Table[ a[n], {n, -1, 24}] (* _Robert G. Wilson v_, Jan 13 2005 *)
%t LinearRecurrence[{3,1},{0,1},30] (* or *) CoefficientList[Series[x/ (1-3x-x^2), {x,0,30}], x] (* _Harvey P. Dale_, Apr 20 2011 *)
%t Table[If[n==0, a1=1; a0=0, a2=a1; a1=a0; a0=3*a1+a2], {n, 0, 30}] (* _Jean-François Alcover_, Apr 30 2013 *)
%t Table[Fibonacci[n, 3], {n, 0, 30}] (* _Vladimir Reshetnikov_, May 08 2016 *)
%o (PARI) a(n)=if(n<1,0,contfracpnqn(vector(n,i,2+(i>1)))[2,1])
%o (PARI) a(n)=([1,3;1,2]^n)[2,1] \\ _Charles R Greathouse IV_, Mar 06 2014
%o (Sage) [lucas_number1(n,3,-1) for n in range(0, 30)] # _Zerinvary Lajos_, Apr 22 2009
%o (Magma)[ n eq 1 select 0 else n eq 2 select 1 else 3*Self(n-1)+Self(n-2): n in [1..30] ]; // _Vincenzo Librandi_, Aug 19 2011
%o (Haskell)
%o a006190 n = a006190_list !! n
%o a006190_list = 0 : 1 : zipWith (+) (map (* 3) $ tail a006190_list) a006190_list
%o -- _Reinhard Zumkeller_, Feb 19 2011
%o (PARI) concat([0],Vec(x/(1-3*x-x^2)+O(x^30))) \\ _Joerg Arndt_, Apr 30 2013
%o (GAP) a:=[0,1];; for n in [3..30] do a[n]:=3*a[n-1]+a[n-2]; od; a; # _Muniru A Asiru_, Mar 31 2018
%Y Row sums of Pascal's rhombus (A059317). Also row sums of triangle A054456(n, m).
%Y Sequences with g.f. 1/(1-k*x-x^2) or x/(1-k*x-x^2): A000045 (k=1), A000129 (k=2), this sequence (k=3), A001076 (k=4), A052918 (k=5), A005668 (k=6), A054413 (k=7), A041025 (k=8), A099371 (k=9), A041041 (k=10), A049666 (k=11), A041061 (k=12), A140455 (k=13), A041085 (k=14), A154597 (k=15), A041113 (k=16), A178765 (k=17), A041145 (k=18), A243399 (k=19), A041181 (k=20).
%Y Cf. A006497, A052906, A175182 (Pisano periods), A201001 (prime subsequence), A092936 (squares).
%Y Cf. A243399.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E Second formula corrected by _Johannes W. Meijer_, Jun 02 2010
|
