cp's OEIS Frontend

A006130 a(n) = a(n-1) + 3*a(n-2) for n > 1, a(0) = a(1) = 1.

%I A006130 M3314 #302 Jul 13 2025 11:06:32
%S A006130 1,1,4,7,19,40,97,217,508,1159,2683,6160,14209,32689,75316,173383,
%T A006130 399331,919480,2117473,4875913,11228332,25856071,59541067,137109280,
%U A006130 315732481,727060321,1674257764,3855438727,8878212019,20444528200,47079164257,108412748857
%N A006130 a(n) = a(n-1) + 3*a(n-2) for n > 1, a(0) = a(1) = 1.
%C A006130 Counts walks of length n at the vertex of degree five in the graph with adjacency matrix A = [1,1,1,1;1,0,0,0;1,0,0,0;1,0,0,0]. - _Paul Barry_, Oct 02 2004
%C A006130 Form the graph with matrix A = [0,1,1,1;1,1,0,0;1,0,1,0;1,0,0,1]. The sequence 0,1,1,4,... counts walks of length n between the vertex without loop and another vertex. - _Paul Barry_, Oct 02 2004
%C A006130 Length-n words with letters {0,1,2,3} where no two consecutive letters are nonzero, see fxtbook link below. - _Joerg Arndt_, Apr 08 2011
%C A006130 Hankel transform is the sequence [1,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...]. - _Philippe Deléham_, Nov 10 2007
%C A006130 Let M = [1, sqrt(3); sqrt(3), 0] be a 2 X 2 matrix. Then A006130(n)={[M^n]_(1,1)}. Note that A006130-A052533 = A006130 (shifted to the right one place, with first term = 0). - _L. Edson Jeffery_, Nov 25 2011 [Any matrix M = [1, y; 3/y, 0], with y not 0, will do it. - _Wolfdieter Lang_, Feb 18 2018]
%C A006130 The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=2, 4*a(n-2) equals the number of 4-colored compositions of n with all parts >=2, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 26 2011
%C A006130 a(n) is the number of compositions (ordered partitions) of n into parts 1 and 2 where there are three sorts of part 2 (see the g.f.). - _Joerg Arndt_, Jan 16 2024
%C A006130 Number of pairs of rabbits when there are 3 pairs per litter and offspring reach parenthood after 2 gestation periods. - _Robert FERREOL_, Oct 28 2018
%C A006130 Numerators of stationary probabilities sequence for number of customers in steady state of M2/M/1 queue, whose g.f. is (1-z)/(3-3z-z(1-z^2)). - _Igor Kleiner_, Nov 03 2018
%C A006130 INVERT transform of (1, 0, 3, 0, 9, 0, 27, ...). - _Gary W. Adamson_, Jul 15 2019
%C A006130 Number of 3-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - _Brian Hopkins_, Aug 17 2020
%C A006130 Number of ways to tile a strip of length n with 3 colors of dominoes and 1 color of squares. - _Greg Dresden_, Sep 01 2021
%C A006130 Number of 3-permutations of n elements avoiding the patterns 231, 312, 321. See Bonichon and Sun. - _Michel Marcus_, Aug 20 2022
%C A006130 a(n-1), with a(-1) = 0, appears in the formula for the powers of the fundamental (integer) algebraic number c = (1 + sqrt(13))/2 = A209927: c^n = A052533(n) + a(n-1)*c. With the formulas given below, and also in A052533, in terms of S-Chebyshev polynomials this is valid also for the powers of 1/c = (-1 + sqrt(13))/6 = A356033. - _Wolfdieter Lang_, Nov 26 2023
%D A006130 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A006130 Stephen Wolfram, 'The Mathematica Book,' Fourth Edition, Wolfram Media or Cambridge University Press, 1999, p. 96.
%H A006130 Vincenzo Librandi, G. C. Greubel and Robert Israel, <a href="/A006130/b006130.txt">Table of n, a(n) for n = 0..2485</a> (n = 0..149 from Vincenzo Librandi, n = 150..300 from G. C. Greubel)
%H A006130 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.317-318.
%H A006130 Nicolas Bonichon and Pierre-Jean Morel, <a href="https://arxiv.org/abs/2202.12677">Baxter d-permutations and other pattern avoiding classes</a>, arXiv:2202.12677 [math.CO], 2022.
%H A006130 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 A006130 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=436">Encyclopedia of Combinatorial Structures 436</a>
%H A006130 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 A006130 Thor Martinsen, <a href="https://doi.org/10.7546/nntdm.2025.31.2.370-389">Non-Fisherian generalized Fibonacci numbers</a>, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 387-389.
%H A006130 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 A006130 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%H A006130 Arulalan Rajan, R. Vittal Rao, Ashok Rao and H. S. Jamadagni, <a href="http://arxiv.org/abs/1205.5398">Fibonacci Sequence, Recurrence Relations, Discrete Probability Distributions and Linear Convolution</a>, arXiv preprint arXiv:1205.5398 [math.PR], 2012.
%H A006130 A. G. Shannon and J. V. Leyendekkers, <a href="http://nntdm.net/volume-21-2015/number-2/35-42/">The Golden Ratio family and the Binet equation</a>, Notes on Number Theory and Discrete Mathematics, Vol. 21, 2015, No. 2, 35-42.
%H A006130 Nathan Sun, <a href="https://arxiv.org/abs/2208.08506">On d-permutations and Pattern Avoidance Classes</a>, arXiv:2208.08506 [math.CO], 2022.
%H A006130 A. K. Whitford, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/15-1/whitford-a.pdf">Binet's formula generalized</a>, Fib. Quart., 15 (1977), pp. 21, 24, 29.
%H A006130 Fatih Yılmaz and Mustafa Özkan, <a href="https://doi.org/10.3390/axioms11060255">On the Generalized Gaussian Fibonacci Numbers and Horadam Hybrid Numbers: A Unified Approach</a>, Axioms (2022) Vol. 11, No. 6, 255.
%H A006130 Paul Thomas Young, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/32-1/young.pdf">p-adic congruences for generalized Fibonacci sequences</a>, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
%H A006130 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,3).
%H A006130 <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials</a>.
%F A006130 O.g.f.: 1/(1 - x - 3*x^2). - _Simon Plouffe_ in his 1992 dissertation.
%F A006130 a(n) = (( (1 + sqrt(13))/2 )^(n+1) - ( (1 - sqrt(13))/2 )^(n+1))/sqrt(13).
%F A006130 a(n) = Sum_{k = 0..ceiling(n/2)} 3^k*C(n-k, k). - _Benoit Cloitre_, _Philippe Deléham_, Mar 07 2004
%F A006130 a(0) = 1; a(1) = 1; for n >= 1, a(n+1) = (a(n)^2 - (-3)^n) / a(n-1). - _Philippe Deléham_, Mar 07 2004
%F A006130 The i-th term of the sequence is the (1, 2) entry in the i-th power of the 2 X 2 matrix M = ((-1, 1), (1, 2)). - _Simone Severini_, Oct 15 2005
%F A006130 a(n) = lower right term in the 2 X 2 matrix [0,3; 1,1]^n. - _Gary W. Adamson_, Mar 02 2008
%F A006130 a(n) = Sum_{k = 0..n} A109466(n,k)*(-3)^(n-k). - _Philippe Deléham_, Oct 26 2008
%F A006130 a(n) = Product_{k = 1..floor((n - 1)/2)} (1 + 12*cos(k*Pi/n)^2). - _Roger L. Bagula_ and _Gary W. Adamson_, Nov 21 2008
%F A006130 Limiting ratio = (1 + sqrt(13))/2 = 2.30277563.. = A098316 - 1. - _Roger L. Bagula_ and _Gary W. Adamson_, Nov 21 2008
%F A006130 G.f.: G(0)/(2-x), where G(k)= 1 + 1/(1 - x*(13*k - 1)/(x*(13*k + 12) - 2/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 18 2013
%F A006130 G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + 3*x)/( x*(4*k+3 + 3*x) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 08 2013
%F A006130 a(n) = ( Sum_{1 <= k <= n+1, k odd} C(n+1,k)*13^((k-1)/2) )/2^n. - _Vladimir Shevelev_, Feb 05 2014
%F A006130 E.g.f.: (1/(a - b))*(a*exp(a*x) - b*exp(b*x)), where 2*a = 1 + sqrt(13) and 2*b = 1 - sqrt(13). - _G. C. Greubel_, Aug 30 2015
%F A006130 a(n) = ((i*sqrt(3))^n)*S(n, (-i/sqrt(3))), with the imaginary unit i and the Chebyshev S polynomials (coefficients in A049310). - _Wolfdieter Lang_, Feb 18 2018
%F A006130 a(n) = hypergeom([(1-n)/2, -n/2], [-n], -12) for n >= 1. - _Peter Luschny_, Feb 18 2018
%F A006130 a(n) = 3 * (-3)^n * a(-2-n) for all n in Z. - _Michael Somos_, Nov 04 2018
%F A006130 a(n) = ( sqrt(3) )^n * Fibonacci(n+1, 1/sqrt(3)). - _G. C. Greubel_, Dec 26 2019
%F A006130 a(n) = numerator of the continued fraction 1 + 3/(1 + 3/(1 + 3/ ... + 3/1)) with exactly n 1's, for n>0. - _Greg Dresden_ and _Alexander Mark_, Aug 16 2020
%F A006130 With an initial 0 prepended, the sequence [0, 1, 1, 4, 7, 19, 40, ...] satisfies the congruences a(n*p^k) == e*a(n*p^(k-1)) (mod p^k) for positive integers k and n and all primes p, where e = +1 for the primes p listed in A296937, e = 0 if p = 13, otherwise e = -1. See Young, Theorem 1, Corollary 1 (i). - _Peter Bala_, Dec 28 2022
%F A006130 From _Wolfdieter Lang_, Nov 27 2023: (Start)
%F A006130 a(n) = sqrt(-3)^n*S(n, 1/sqrt(-3)) with the S-Chebyshev polynomials (see A049310), also valid for negative n, using S(-n, x) = -S(n-2, x), for n >= 2, and S(-1, x) = 0. See above the formula in terms of Fibonacci polynomials).
%F A006130 a(n) = A052533(n+2)/3, for n >= 0. (End)
%F A006130 From _Peter Bala_, Jun 27 2025: (Start)
%F A006130 G.f.: Sum_{n >= 0} x^n * Product_{k = 1..n} (k + 3*x)/(1 + k*x) = Sum_{n >= 0} x^n * Product_{k = 1..n} (1 + 3*k*x)/(1 + 3*k*x^2).
%F A006130 The following products telescope:
%F A006130 Product_{k >= 0} (1 + 3^k/a(2*k+1)) = 1 + sqrt(13).
%F A006130 Product_{k >= 1} (1 - 3^k/a(2*k+1)) = 1/14 * (1 + sqrt(13)).
%F A006130 Product_{k >= 0} (1 + (-3)^k/a(2*k+1)) = (1/13) * (13 + sqrt(13)).
%F A006130 Product_{k >= 1} (1 - (-3)^k/a(2*k+1)) = (1/14) * (13 + sqrt(13)). (End)
%e A006130 G.f. = 1 + x + 4*x^2 + 7*x^3 + 19*x^4 + 40*x^5 + 97*x^6 + 217*x^7 + ...
%p A006130 a := n -> add(binomial(n-k, k)*3^k, k=0..n): seq(a(n), n=0..29); # _Zerinvary Lajos_, Sep 30 2006
%p A006130 f:= gfun:-rectoproc({a(n) = a(n-1) + 3*a(n-2), a(0) = 1, a(1) = 1},a(n),remember):
%p A006130 map(f, [$0..100]); # _Robert Israel_, Aug 31 2015
%t A006130 a[0] = a[1] = 1; a[n_] := a[n] = a[n - 1] + 3a[n - 2]; Table[ a[n], {n, 0, 30}]
%t A006130 LinearRecurrence[{1, 3}, {1, 1}, 30] (* _Vincenzo Librandi_, Oct 17 2012 *)
%t A006130 RecurrenceTable[{a[n]== a[n-1] + 3*a[n-2], a[0]== 1, a[1]== 1}, a, {n,0,30}] (* _G. C. Greubel_, Aug 30 2015 *)
%t A006130 a[0] := 1; a[n_] := Hypergeometric2F1[1/2-n/2, -n/2, -n, -12]; Table[a[n], {n, 0, 29}] (* _Peter Luschny_, Feb 18 2018 *)
%t A006130 a[ n_] := With[{s = Sqrt[-1/3]}, ChebyshevU[n, s/2] / s^n] // Simplify; (* _Michael Somos_, Nov 04 2018 *)
%o A006130 (Sage) from sage.combinat.sloane_functions import recur_gen2
%o A006130 it = recur_gen2(1,1,1,3)
%o A006130 [next(it) for i in range(30)] # _Zerinvary Lajos_, Jun 25 2008
%o A006130 (Sage) [lucas_number1(n,1,-3) for n in range(1, 31)] # _Zerinvary Lajos_, Apr 22 2009
%o A006130 (PARI) Vec(1/(1-x-3*x^2+O(x^66))) \\ _Franklin T. Adams-Watters_, May 26 2011
%o A006130 (Python)
%o A006130 an = an1 = 1
%o A006130 while an<10**5:
%o A006130    print(an)
%o A006130    an1 += an*3
%o A006130    an = an1 - an*3   # _Alex Ratushnyak_, Apr 20 2012
%o A006130 (Magma) [n le 2 select 1 else Self(n-1) + 3*Self(n-2): n in [1..40]]; // _Vincenzo Librandi_, Oct 17 2012
%o A006130 (GAP) a := [1, 1];; for n in [3..30] do a[n] := a[n-1] + 3*a[n-2]; od; a; # _Muniru A Asiru_, Feb 18 2018
%Y A006130 Cf. A006131, A015440, A049310, A052533, A140167, A175291 (Pisano periods), A099232 (partial sums), A274977.
%Y A006130 Cf. A209927, A356033.
%K A006130 nonn,easy
%O A006130 0,3
%A A006130 _N. J. A. Sloane_