A140167 -id:A140167 - 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)

A140165 a(n) = -a(n-1) + 3*a(n-2), starting a(1)=1, a(2)=2.

Original entry on oeis.org

1, 2, 1, 5, -2, 17, -23, 74, -143, 365, -794, 1889, -4271, 9938, -22751, 52565, -120818, 278513, -640967, 1476506, -3399407, 7828925, -18027146, 41513921, -95595359, 220137122, -506923199, 1167334565

Offset: 1

Gary W. Adamson, May 10 2008

Row sums of triangle A140166.

Equals eigensequence of triangle A112555. - Gary W. Adamson, Jan 30 2009

			a(6) = 17 = (-1)*a(5) + 3*a(4) = (-1)*(-2) + 3*5.
a(4) = 5 = term (1,1) of X^5, where X^5 = [5,7; 7,26].

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (-1,3).

Cf. A140166, A140167, A112555.

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

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( x*(1+3*x)/(1+x-3*x^2) )); // G. C. Greubel, Dec 26 2019

a:=[1,2]; [n le 2 select a[n] else -Self(n-1) + 3*Self(n-2): n in [1..30]]; // Marius A. Burtea, Jan 02 2020

seq(coeff(series(x*(1+3*x)/(1+x-3*x^2), x, n+1), x, n), n = 1..30); # G. C. Greubel, Dec 26 2019

Table[Round[(-Sqrt[3])^n*(LucasL[n, 1/Sqrt[3]] - 5*Fibonacci[n, 1/Sqrt[3]]/Sqrt[3])/2], {n,0,30}] (* G. C. Greubel, Dec 26 2019 *)
LinearRecurrence[{-1,3},{1,2},40] (* Harvey P. Dale, Jun 11 2024 *)

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

def A140165_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( x*(1+3*x)/(1+x-3*x^2) ).list()
a=A140165_list(30); a[1:] # G. C. Greubel, Dec 26 2019

a(n) = term (1,1) of X^n, where X = the 2 X 2 matrix [1,-1; -1,-2].
G.f.: x*(1+3*x)/(1+x-3*x^2). - Philippe Deléham, Dec 18 2011
a(n) = -(3*A140167(n-1) + A140167(n)). - R. J. Mathar, Apr 22 2013
a(n) = (-sqrt(3))^n*( Lucas(n, 1/sqrt(3)) - 5*Fibonacci(n, 1/sqrt(3))/sqrt(3) )/2. - G. C. Greubel, Dec 26 2019
E.g.f.: (1/13)*exp(-x/2)*(13*cosh(sqrt(13)*x/2) + 5*sqrt(13)*sinh(sqrt(13)*x/2)) - 1. - Stefano Spezia, Jan 02 2020

A274977 a(n) = a(n-1) + 3*a(n-2) with n>1, a(0)=1, a(1)=6.

Original entry on oeis.org

1, 6, 9, 27, 54, 135, 297, 702, 1593, 3699, 8478, 19575, 45009, 103734, 238761, 549963, 1266246, 2916135, 6714873, 15463278, 35607897, 81997731, 188821422, 434814615, 1001278881, 2305722726, 5309559369, 12226727547, 28155405654, 64835588295, 149301805257, 343808570142

Offset: 0

Bruno Berselli, Sep 13 2016

a(n)/a(n+1) converges to 1/A209927 as n approaches infinity.

			Table of similar sequences (not extendable on the left side) where this recurrence can be applied to the first two terms:
----------------------------------------------------------------------
(*)      -  -  1, -1,  2, -1,  5,   2,  17,  23,   74,  143,  365, ...
A052533: -  -  1,  0,  3,  3, 12,  21,  57, 120,  291,  651, 1524, ...
(^)      -  0, 1,  1,  4,  7, 19,  40,  97, 217,  508, 1159, 2683, ...
A006138: -  -  1,  2,  5, 11, 26,  59, 137, 314,  725, 1667, 3842, ...
A105476: -  -  1,  3,  6, 15, 33,  78, 177, 411,  942, 2175, 5001, ...
(^)      0, 1, 1,  4,  7, 19, 40,  97, 217, 508, 1159, 2683, 6160, ...
A105963: -  -  1,  5,  8, 23, 47, 116, 257, 605, 1376, 3191, 7319, ...
A274977: -  -  1,  6,  9, 27, 54, 135, 297, 702, 1593, 3699, 8478, ...
A075118: -  2, 1,  7, 10, 31, 61, 154, 337, 799, 1810, 4207, 9637, ...
----------------------------------------------------------------------
(*) see version A140165.
(^) see A006130 and the signed versions A140167, A182228.

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

Cf. A006130, A006138, A052533, A075118, A105476, A105963.

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

[n le 2 select 5*n-4 else Self(n-1)+3*Self(n-2): n in [1..40]];

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

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

RecurrenceTable[{a[n]==a[n-1] +3a[n-2], a[0]==1, a[1]==6}, a, {n,0,40}]
Table[Round[Sqrt[3]^(n-1)*(Sqrt[3]*Fibonacci[n+1, 1/Sqrt[3]] + 5*Fibonacci[n, 1/Sqrt[3]])], {n,0,40}] (* G. C. Greubel, Jan 15 2020 *)
LinearRecurrence[{1,3},{1,6},40] (* Harvey P. Dale, Jul 11 2023 *)

v=vector(40); v[1]=1; v[2]=6; for(n=3, #v, v[n]=v[n-1]+3*v[n-2]); v

from sage.combinat.sloane_functions import recur_gen2
a = recur_gen2(1, 6, 1, 3)
[next(a) for n in range(40)]

G.f.: (1 + 5*x)/(1 - x - 3*x^2).
a(n) = ((13 + 11*sqrt(13))*(1 + sqrt(13))^n + (13 - 11*sqrt(13))*(1 - sqrt(13))^n)/(26*2^n).
3*a(n) + a(n+1) =  9*A105476(n+1).
3*a(n) - a(n+1) = 27*A006130(n-3) with n>1, A006130(-1) = 0.
a(n+1) - a(n)   = 27*A105476(n-3) with n>2.
a(n) = 3^((n-1)/2)*( sqrt(3)*Fibonacci(n+1, 1/sqrt(3)) + 5*Fibonacci(n, 1/sqrt(3)) ). - G. C. Greubel, Jan 15 2020
E.g.f.: (1/13)*exp(x/2)*(13*cosh((sqrt(13)*x)/2) + 11*sqrt(13)*sinh((sqrt(13)*x)/2)). - Stefano Spezia, 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

A140165 a(n) = -a(n-1) + 3*a(n-2), starting a(1)=1, a(2)=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

A274977 a(n) = a(n-1) + 3*a(n-2) with n>1, a(0)=1, a(1)=6.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Python

Formula

A099579 a(n) = Sum_{k=0..floor(n/2)} binomial(n-k, k-1) * 3^(k-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A140166 Triangle read by rows, iterates of X * [1,0,0,0,...]; where X = an infinite bidiagonal matrix with [1,-2,1,-2,1,...] in the main diagonal, [1,1,1,...] in the subdiagonal and the rest zeros.

Views