A274977 -id:A274977 - cp's OEIS frontend

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

1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, 32689, 75316, 173383, 399331, 919480, 2117473, 4875913, 11228332, 25856071, 59541067, 137109280, 315732481, 727060321, 1674257764, 3855438727, 8878212019, 20444528200, 47079164257, 108412748857

Offset: 0

N. J. A. Sloane

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
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
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
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
Let M = [1, sqrt(3); sqrt(3), 0] be a 2 X 2 matrix. Then A006130(n)={[M^n]A006130-A052533%20=%20A006130%20(shifted%20to%20the%20right%20one%20place,%20with%20first%20term%20=%200).%20-%20_L.%20Edson%20Jeffery">(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]
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
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
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
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
INVERT transform of (1, 0, 3, 0, 9, 0, 27, ...). - Gary W. Adamson, Jul 15 2019
Number of 3-compositions of n+2 with 1 not allowed as a part; see Hopkins & Ouvry reference. - Brian Hopkins, Aug 17 2020
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
Number of 3-permutations of n elements avoiding the patterns 231, 312, 321. See Bonichon and Sun. - Michel Marcus, Aug 20 2022
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

			G.f. = 1 + x + 4*x^2 + 7*x^3 + 19*x^4 + 40*x^5 + 97*x^6 + 217*x^7 + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Stephen Wolfram, 'The Mathematica Book,' Fourth Edition, Wolfram Media or Cambridge University Press, 1999, p. 96.

Vincenzo Librandi, G. C. Greubel and Robert Israel, Table of n, a(n) for n = 0..2485 (n = 0..149 from Vincenzo Librandi, n = 150..300 from G. C. Greubel)
Joerg Arndt, Matters Computational (The Fxtbook), pp.317-318.
Nicolas Bonichon and Pierre-Jean Morel, Baxter d-permutations and other pattern avoiding classes, arXiv:2202.12677 [math.CO], 2022.
Brian Hopkins and Stéphane Ouvry, Combinatorics of Multicompositions, arXiv:2008.04937 [math.CO], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 436
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 387-389.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Arulalan Rajan, R. Vittal Rao, Ashok Rao and H. S. Jamadagni, Fibonacci Sequence, Recurrence Relations, Discrete Probability Distributions and Linear Convolution, arXiv preprint arXiv:1205.5398 [math.PR], 2012.
A. G. Shannon and J. V. Leyendekkers, The Golden Ratio family and the Binet equation, Notes on Number Theory and Discrete Mathematics, Vol. 21, 2015, No. 2, 35-42.
Nathan Sun, On d-permutations and Pattern Avoidance Classes, arXiv:2208.08506 [math.CO], 2022.
A. K. Whitford, Binet's formula generalized, Fib. Quart., 15 (1977), pp. 21, 24, 29.
Fatih Yılmaz and Mustafa Özkan, On the Generalized Gaussian Fibonacci Numbers and Horadam Hybrid Numbers: A Unified Approach, Axioms (2022) Vol. 11, No. 6, 255.
Paul Thomas Young, p-adic congruences for generalized Fibonacci sequences, The Fibonacci Quarterly, Vol. 32, No. 1, 1994.
Index entries for linear recurrences with constant coefficients, signature (1,3).
Index entries for sequences related to Chebyshev polynomials.

Cf. A006131, A015440, A049310, A052533, A140167, A175291 (Pisano periods), A099232 (partial sums), A274977.

Cf. A209927, A356033.

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

[n le 2 select 1 else Self(n-1) + 3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Oct 17 2012

a := n -> add(binomial(n-k, k)*3^k, k=0..n): seq(a(n), n=0..29); # Zerinvary Lajos, Sep 30 2006
f:= gfun:-rectoproc({a(n) = a(n-1) + 3*a(n-2), a(0) = 1, a(1) = 1},a(n),remember):
map(f, [$0..100]); # Robert Israel, Aug 31 2015

a[0] = a[1] = 1; a[n_] := a[n] = a[n - 1] + 3a[n - 2]; Table[ a[n], {n, 0, 30}]
LinearRecurrence[{1, 3}, {1, 1}, 30] (* Vincenzo Librandi, Oct 17 2012 *)
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 *)
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 *)
a[ n_] := With[{s = Sqrt[-1/3]}, ChebyshevU[n, s/2] / s^n] // Simplify; (* Michael Somos, Nov 04 2018 *)

Vec(1/(1-x-3*x^2+O(x^66))) \\ Franklin T. Adams-Watters, May 26 2011

an = an1 = 1
while an<10**5:
   print(an)
   an1 += an*3
   an = an1 - an*3   # Alex Ratushnyak, Apr 20 2012

from sage.combinat.sloane_functions import recur_gen2
it = recur_gen2(1,1,1,3)
[next(it) for i in range(30)] # Zerinvary Lajos, Jun 25 2008

[lucas_number1(n,1,-3) for n in range(1, 31)] # Zerinvary Lajos, Apr 22 2009

O.g.f.: 1/(1 - x - 3*x^2). - Simon Plouffe in his 1992 dissertation.
a(n) = (( (1 + sqrt(13))/2 )^(n+1) - ( (1 - sqrt(13))/2 )^(n+1))/sqrt(13).
a(n) = Sum_{k = 0..ceiling(n/2)} 3^k*C(n-k, k). - Benoit Cloitre, Philippe Deléham, Mar 07 2004
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
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
a(n) = lower right term in the 2 X 2 matrix [0,3; 1,1]^n. - Gary W. Adamson, Mar 02 2008
a(n) = Sum_{k = 0..n} A109466(n,k)*(-3)^(n-k). - Philippe Deléham, Oct 26 2008
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
Limiting ratio = (1 + sqrt(13))/2 = 2.30277563.. = A098316 - 1. - Roger L. Bagula and Gary W. Adamson, Nov 21 2008
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
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
a(n) = ( Sum_{1 <= k <= n+1, k odd} C(n+1,k)*13^((k-1)/2) )/2^n. - Vladimir Shevelev, Feb 05 2014
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
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
a(n) = hypergeom([(1-n)/2, -n/2], [-n], -12) for n >= 1. - Peter Luschny, Feb 18 2018
a(n) = 3 * (-3)^n * a(-2-n) for all n in Z. - Michael Somos, Nov 04 2018
a(n) = ( sqrt(3) )^n * Fibonacci(n+1, 1/sqrt(3)). - G. C. Greubel, Dec 26 2019
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
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
From Wolfdieter Lang, Nov 27 2023: (Start)
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).
a(n) = A052533(n+2)/3, for n >= 0. (End)
From Peter Bala, Jun 27 2025: (Start)
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).
The following products telescope:
Product_{k >= 0} (1 + 3^k/a(2*k+1)) = 1 + sqrt(13).
Product_{k >= 1} (1 - 3^k/a(2*k+1)) = 1/14 * (1 + sqrt(13)).
Product_{k >= 0} (1 + (-3)^k/a(2*k+1)) = (1/13) * (13 + sqrt(13)).
Product_{k >= 1} (1 - (-3)^k/a(2*k+1)) = (1/14) * (13 + sqrt(13)). (End)

A105476 Number of compositions of n when each even part can be of two kinds.

Original entry on oeis.org

1, 1, 3, 6, 15, 33, 78, 177, 411, 942, 2175, 5001, 11526, 26529, 61107, 140694, 324015, 746097, 1718142, 3956433, 9110859, 20980158, 48312735, 111253209, 256191414, 589951041, 1358525283, 3128378406, 7203954255, 16589089473, 38200952238, 87968220657

Offset: 0

Emeric Deutsch, Apr 09 2005

Row sums of A105475.
Starting (1, 3, 6, 15, ...) = sum of (n-1)-th row terms of triangle A140168. - Gary W. Adamson, May 10 2008
a(n) is also the number of compositions of n using 1's and 2's such that each run of like numbers can be grouped arbitrarily. For example, a(4) = 15 because 4 = (1)+(1)+(1)+(1) = (1+1)+(1)+(1) = (1)+(1+1)+(1) = (1)+(1)+(1+1) = (1+1)+(1+1) = (1+1+1)+(1) = (1)+(1+1+1) = (1+1+1+1) = (2)+(1)+(1) = (1)+(2)+(1) = (1)+(1)+(2) = (2)+(1+1) = (1+1)+(2) = (2)+(2) = (2+2). - Martin J. Erickson (erickson(AT)truman.edu), Dec 09 2008
An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 69, 261, 321 and 324, lead to this sequence (without the first leading 1). For the corner squares these vectors lead to the companion sequence A006138. - Johannes W. Meijer, Aug 15 2010
Inverse INVERT transform of the left shifted sequence gives A000034.
Eigensequence of the triangle
  1,
  2, 1,
  1, 2, 1,
  2, 1, 2, 1,
  1, 2, 1, 2, 1,
  2, 1, 2, 1, 2, 1,
  1, 2, 1, 2, 1, 2, 1,
  2, 1, 2, 1, 2, 1, 2, 1 ... - Paul Barry, Feb 10 2011
Pisano period lengths: 1, 3, 1, 6, 24, 3, 24, 6, 1, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, ... - R. J. Mathar, Aug 10 2012

			a(3)=6 because we have (3),(1,2),(1,2'),(2,1),(2',1) and (1,1,1).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Sean A. Irvine, Walks on Graphs.
Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 33.
Index entries for linear recurrences with constant coefficients, signature (1,3).

Cf. A006130, A105475, A105963, A274977.

a:=[1,3];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; Concatenation([1], a); # G. C. Greubel, Jan 15 2020

I:=[1,1,3]; [n le 3 select I[n] else Self(n-1)+3*Self(n-2): n in [1..35]]; // Vincenzo Librandi, Jul 21 2013

R:=PowerSeriesRing(Integers(), 33); Coefficients(R!( 1/(1-(x/(1-x))-x^2/(1-x^2)))); // Marius A. Burtea, Jan 15 2020

G:=(1-z^2)/(1-z-3*z^2): Gser:=series(G,z=0,35): 1,seq(coeff(Gser,z^n),n=1..33);

CoefficientList[Series[(1-x^2)/(1-x-3x^2), {x,0,35}], x] (* or *) Join[{1}, LinearRecurrence[{1, 3}, {1, 3}, 50]] (* Vladimir Joseph Stephan Orlovsky, Jul 17 2011; typo fixed by Vincenzo Librandi, Jul 21 2013 *)
Table[Round[Sqrt[3]^(n-3)*(2*Sqrt[3]*Fibonacci[n+1, 1/Sqrt[3]] +Fibonacci[n, 1/Sqrt[3]])], {n, 0, 40}] (* G. C. Greubel, Jan 15 2020 *)

Vec((1-x^2)/(1-x-3*x^2)+O(x^40)) \\ Charles R Greathouse IV, Jun 13 2013

def A105476_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-x^2)/(1-x-3*x^2) ).list()
A105476_list(40) # G. C. Greubel, Jan 15 2020

G.f.: (1-x^2) / (1-x-3*x^2).
a(n) = a(n-1) + 3*a(n-2) for n>=3.
a(n) = 3*A006138(n-2), n>=2.
a(n) = ((2+sqrt(13))*(1+sqrt(13))^n - (2-sqrt(13))*(1-sqrt(13))^n)/(3*2^n*sqrt(13)) for n>0. - Bruno Berselli, May 24 2011
G.f.: 1/(1 - Sum_{k>=1} x^k*(1+x^k) ). - Joerg Arndt, Mar 09 2014
G.f.: 1/(1 - (x/(1-x)) - x^2/(1-x^2)) = 1/(1 - (x+2*x^2+x^3+2*x^4+x^5+2*x^6+...) ); in general 1/(1 - Sum_{j>=1} m(j)*x^j ) is the g.f. for compositions with m(k) sorts of part k. - Joerg Arndt, Feb 16 2015
a(n) = 3^((n-1)/2)*( 2*sqrt(3)*Fibonacci(n, 1/sqrt(3)) + Fibonacci(n, 1/sqrt(3)) ). - G. C. Greubel, Jan 15 2020
E.g.f.: 1/3 + (2/39)*exp(x/2)*(13*cosh((sqrt(13)*x)/2) + 2*sqrt(13)*sinh((sqrt(13)*x)/2)). - Stefano Spezia, Jan 15 2020

A006138 a(n) = a(n-1) + 3*a(n-2).

Original entry on oeis.org

1, 2, 5, 11, 26, 59, 137, 314, 725, 1667, 3842, 8843, 20369, 46898, 108005, 248699, 572714, 1318811, 3036953, 6993386, 16104245, 37084403, 85397138, 196650347, 452841761, 1042792802, 2401318085, 5529696491, 12733650746, 29322740219, 67523692457, 155491913114

Offset: 0

N. J. A. Sloane

The binomial transform of a(n) is b(n) = A006190(n+1), which satisfies b(n) = 3*b(n-1) + b(n-2). - Paul Barry, May 21 2006
Partial sums of A105476. - Paul Barry, Feb 02 2007
An elephant sequence, see A175654. For the corner squares four A[5] vectors, with decimal values 69, 261, 321 and 324, lead to this sequence. For the central square these vectors lead to the companion sequence A105476 (without the first leading 1). - Johannes W. Meijer, Aug 15 2010
Equals the INVERTi transform of A063782: (1, 3, 10, 32, 104, ...). - Gary W. Adamson, Aug 14 2010
Pisano period lengths: 1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, ... - R. J. Mathar, Aug 10 2012
The sequence is the INVERT transform of A016116: (1, 1, 2, 2, 4, 4, 8, 8, ...). - Gary W. Adamson, Jul 17 2015

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
N. T. Gridgeman, A new look at Fibonacci generalization, Fib,. Quart., 11 (1973), 40-55.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (1,3).

Cf. A063782. - Gary W. Adamson, Aug 14 2010

Cf. A006130, A006190, A016116, A105476, A122950, A175654, A274977.

a:=[1,2];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; a; # G. C. Greubel, Nov 19 2019

[n le 2 select n else Self(n-1)+3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Sep 15 2016

A006138:=-(1+z)/(-1+z+3*z**2); # Simon Plouffe in his 1992 dissertation

CoefficientList[Series[(1+z)/(1-z-3*z^2), {z,0,40}], z] (* Vladimir Joseph Stephan Orlovsky, Jun 11 2011 *)
Table[(I*Sqrt[3])^(n-1)*(I*Sqrt[3]*ChebyshevU[n, 1/(2*I*Sqrt[3])] + ChebyshevU[n-1, 1/(2*I*Sqrt[3])]), {n, 0, 40}]//Simplify (* G. C. Greubel, Nov 19 2019 *)
LinearRecurrence[{1,3},{1,2},40] (* Harvey P. Dale, May 29 2025 *)

main(size)={my(v=vector(size),i);v[1]=1;v[2]=2;for(i=3,size,v[i]=v[i-1]+3*v[i-2]);return(v);} /* Anders Hellström, Jul 17 2015 */

def A006138_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1+x)/(1-x-3*x^2)).list()
A006138_list(40) # G. C. Greubel, Nov 19 2019

a(n) = Sum_{k=0..n+1} A122950(n+1,k)*2^(n+1-k). - Philippe Deléham, Jan 04 2008
G.f.: (1+x)/(1-x-3*x^2). - Paul Barry, May 21 2006
a(n) = Sum_{k=0..n} C(floor((2n-k)/2),n-k)*3^floor(k/2). - Paul Barry, Feb 02 2007
a(n) = A006130(n) + A006130(n-1). - R. J. Mathar, Jun 22 2011
a(n) = (i*sqrt(3))^(n-1)*(i*sqrt(3)*ChebyshevU(n, 1/(2*i*sqrt(3))) + ChebyshevU(n-1, 1/(2*i*sqrt(3)))), where i=sqrt(-1). - G. C. Greubel, Nov 19 2019

Typo in formula corrected by Johannes W. Meijer, Aug 15 2010

A052533 Expansion of (1-x)/(1-x-3*x^2).

Original entry on oeis.org

1, 0, 3, 3, 12, 21, 57, 120, 291, 651, 1524, 3477, 8049, 18480, 42627, 98067, 225948, 520149, 1197993, 2758440, 6352419, 14627739, 33684996, 77568213, 178623201, 411327840, 947197443, 2181180963, 5022773292, 11566316181, 26634636057

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Form the graph with matrix A=[0,1,1,1;1,1,0,0;1,0,1,0;1,0,0,1]. A052533 counts closed walks of length n at the vertex without loop. - Paul Barry, Oct 02 2004
Let M = [0, sqrt(3); sqrt(3), 1] be a 2 X 2 matrix. Then A052533 = {[M^n](1,1)}. Note also that {[M^n](2,2)} = A006130. - L. Edson Jeffery, Nov 25 2011
Pisano period lengths:  1, 3, 1, 6, 24, 3, 24, 6, 1, 24,120, 6,156, 24, 24, 12, 16, 3, 90, 24, ... - R. J. Mathar, Aug 10 2012
a(n) appears in the formula for powers of the fundamental algebraic number c = (1 + sqrt(13))/2 = A209927 of the quadratic number field Q(sqrt(13)): c^n = a(n) + A006130(n-1), for n >=0, with  A006130(-1) = 0. The formulas given below and in A006130 in terms of S-Chebyshev polynomials are valid also for c^(-n), for n >= 0, with 1/c = (-1 + sqrt(13))/2 = A356033. - Wolfdieter Lang, Nov 26 2023

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 463
Index entries for linear recurrences with constant coefficients, signature (1,3).

Cf. A006130, A049310, A209927, A274977, A356033.

a:=[1,0];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; a; # G. C. Greubel, May 09 2019

I:=[1,0]; [n le 2 select I[n] else Self(n-1)+3*Self(n-2): n in [1..40]]; // G. C. Greubel, May 09 2019

R:=PowerSeriesRing(Integers(), 33); Coefficients(R!( (1-x)/(1-x-3*x^2))); // Marius A. Burtea, Jan 15 2020

spec := [S,{S=Sequence(Prod(Z,Union(Z,Z,Z),Sequence(Z)))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);
seq(coeff(series((1-x)/(1-x-3*x^2), x, n+1), x, n), n = 0..40); # G. C. Greubel, Jan 15 2020

CoefficientList[Series[(1-x)/(1-x-3x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 07 2013 *)
LinearRecurrence[{1,3}, {1,0}, 40] (* G. C. Greubel, May 09 2019 *)

my(x='x+O('x^30)); Vec((1-x)/(1-x-3*x^2)) \\ G. C. Greubel, May 09 2019

[lucas_number1(n+1,1,-3) -lucas_number1(n,1,-3) for n in (0..40)] # G. C. Greubel, May 09 2019

G.f.: (1 - x)/(1 - x - 3*x^2).
a(n) = A006130(n) - A006130(n-1).
a(n) = a(n-1) + 3*a(n-2), with a(0)=1, a(1)=0.
a(n) = Sum_{alpha = RootOf(-1+x+3*x^2)} (1/13)*(-1 + 7*alpha)* alpha^(-n-1).
a(n) = Sum_{k=0..floor(n/2)} C(n-k-1,n-2*k)*3^k. - Paul Barry, Mar 16 2010
If p[1]=0, and p[i]=3, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010
G.f.: (Q(0) -1)*(1-x)/x, where Q(k) = 1 + 3*x^2 + (k+2)*x - x*(k+1 + 3*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 07 2013
a(n) = 3^(n/2) * Fibonacci(n-1, 1/sqrt(3)). - G. C. Greubel, Jan 15 2020
From Wolfdieter Lang, Nov 27 2023: (Start)
a(n) = 3*A006130(n-2), with A006130(-2) = 1/3 and A006130(-1) = 0.
a(n) = 3*sqrt(-3)^(n-2)*S(n-2, 1/sqrt(-3)), with the S Chebyshev polynomials (see A049310), valid also for negative indices n, using S(-n, x) = - S(n-2, x), for n>= 2, and S(-1, x) = 0. (End)

More terms from James Sellers, Jun 06 2000

A075118 Variant on Lucas numbers: a(n) = a(n-1) + 3*a(n-2) with a(0)=2 and a(1)=1.

Original entry on oeis.org

2, 1, 7, 10, 31, 61, 154, 337, 799, 1810, 4207, 9637, 22258, 51169, 117943, 271450, 625279, 1439629, 3315466, 7634353, 17580751, 40483810, 93226063, 214677493, 494355682, 1138388161, 2621455207, 6036619690, 13900985311, 32010844381, 73713800314, 169746333457

Offset: 0

Henry Bottomley, Sep 02 2002

The sequence 4,1,7,.. = 2*0^n+A075118(n) is given by trace(A^n) where A=[1,1,1,1;1,0,0,0;1,0,0,0;1,0,0,0]. - Paul Barry, Oct 01 2004

For n>2, a(n) is the numerator of the value of the continued fraction 1+3/(1+3/(1+...+3/7)) where there are n-2 1's. - Alexander Mark, Aug 16 2020

			a(4) = a(3)+3*a(2) = 10+3*7 = 31.

Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", Wiley, 2001, p. 471.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Wikipedia, Lucas sequence
Index entries for linear recurrences with constant coefficients, signature (1,3).

Cf. A000032, A006130, A014551, A072265, A075117, A274977.

a:=[2,1];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; a; # G. C. Greubel, Jan 15 2020

I:=[2,1]; [n le 2 select I[n] else Self(n-1)+3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jul 20 2013

R:=PowerSeriesRing(Integers(), 33); Coefficients(R!((2-x)/(1-x-3*x^2))); // Marius A. Burtea, Jan 15 2020

a:= n-> (Matrix([[1,2]]). Matrix([[1,1], [3,0]])^n)[1,2]:
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 15 2008

a[0]=2; a[1]=1; a[n_]:= a[n]= a[n-1] +3a[n-2]; Table[a[n], {n, 0, 30}]
CoefficientList[Series[(2-x)/(1-x-3x^2), {x,0,40}], x] (* Vincenzo Librandi, Jul 20 2013 *)
LinearRecurrence[{1,3},{2,1},40] (* Harvey P. Dale, Jun 18 2017 *)
Table[Round[Sqrt[3]^n*LucasL[n, 1/Sqrt[3]]], {n,0,40}] (* G. C. Greubel, Jan 15 2020 *)

my(x='x+O('x^30)); Vec((2-x)/(1-x-3*x^2)) \\ G. C. Greubel, Dec 21 2017

polsym(x^2-x-3, 44) \\ Joerg Arndt, Jan 22 2023

[lucas_number2(n,1,-3) for n in range(0, 30)] # Zerinvary Lajos, Apr 30 2009

a(n) = ((1+sqrt(13))/2)^n + ((1-sqrt(13))/2)^n.
a(n) = 2*A006130(n) - A006130(n-1) = A075117(3, n).
G.f.: (2-x)/(1-x-3*x^2). - Philippe Deléham, Nov 15 2008
a(n) = [x^n] ( (1 + x + sqrt(1 + 2*x + 13*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
a(n) = 3^(n/2) * Lucas(n, 1/sqrt(3)). - G. C. Greubel, Jan 15 2020

A105963 Expansion of (1+4x)/(1-x-3x^2).

Original entry on oeis.org

1, 5, 8, 23, 47, 116, 257, 605, 1376, 3191, 7319, 16892, 38849, 89525, 206072, 474647, 1092863, 2516804, 5795393, 13345805, 30731984, 70769399, 162965351, 375273548, 864169601, 1989990245, 4582499048, 10552469783, 24299966927

Offset: 0

Creighton Dement, Apr 28 2005

Inversion of the periodic sequence with initial period (1,4,-1,-4). Sequence appears to have the property: for m > n, if s divides both a(n) and a(m) then s also divides a(2*m-n). E.g., 23 divides both a(3) = 23 and a(25) = 1989990245; 23 also divides a(2*25-3) = a(47) = 185518234185384428 = (2)^2*(23)*(131)*(15393149202239).

Floretion Algebra Multiplication Program, FAMP Code: 1jesforseq[.5'k + .5k' + 2'kk' + 2e]

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,3).

Cf. A006130, A105476, A274977.

a:=[1,5];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; a; # G. C. Greubel, Jan 15 2020

I:=[ 1,5]; [n le 2 select I[n] else Self(n-1)+3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Jul 20 2013

seq(coeff(series((1+4*x)/(1-x-3*x^2), x, n+1), x, n), n = 0 .. 40); # G. C. Greubel, Jan 15 2020

CoefficientList[Series[(1+4x)/(1-x-3x^2), {x,0,40}], x] (* Vincenzo Librandi, Jul 20 2013 *)
Table[Round[3^((n-1)/2)*(Sqrt[3]*Fibonacci[n+1, 1/Sqrt[3]] + 4*Fibonacci[n, 1/Sqrt[3]] )], {n,0,40}] (* G. C. Greubel, Jan 15 2020 *)

Vec((1+4*x)/(1-x-3*x^2)+O(x^40)) \\ Charles R Greathouse IV, Sep 27 2012

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+4*x)/(1-x-3*x^2) ).list()
A077952_list(30) # G. C. Greubel, Jan 15 2020

a(n) = A006130(n) + 4*A006130(n-1) = A006130(n+1) + A006130(n-1). - R. J. Mathar, Dec 12 2009
From Colin Barker, May 01 2019: (Start)
a(n) = (2^(-1-n)*((1-sqrt(13))^n*(-9+sqrt(13)) + (1+sqrt(13))^n*(9+sqrt(13)))) / sqrt(13).
a(n) = a(n-1) + 3*a(n-2) for n > 1. (End)
a(n) = 3^((n-1)/2)*( sqrt(3)*Fibonacci(n+1, 1/sqrt(3)) + 4*Fibonacci(n, 1/sqrt(3)) ). - G. C. Greubel, Jan 15 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Sage

Formula

A105476 Number of compositions of n when each even part can be of two kinds.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

A006138 a(n) = a(n-1) + 3*a(n-2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A052533 Expansion of (1-x)/(1-x-3*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A075118 Variant on Lucas numbers: a(n) = a(n-1) + 3*a(n-2) with a(0)=2 and a(1)=1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A105963 Expansion of (1+4x)/(1-x-3x^2).