login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006130 a(n) = a(n-1) + 3*a(n-2) for n > 1, a(0) = a(1) = 1.
(Formerly M3314)
64
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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]_(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
REFERENCES
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.
LINKS
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.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
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.
FORMULA
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)
EXAMPLE
G.f. = 1 + x + 4*x^2 + 7*x^3 + 19*x^4 + 40*x^5 + 97*x^6 + 217*x^7 + ...
MAPLE
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
MATHEMATICA
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 *)
PROG
(Sage) 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
(Sage) [lucas_number1(n, 1, -3) for n in range(1, 31)] # Zerinvary Lajos, Apr 22 2009
(PARI) Vec(1/(1-x-3*x^2+O(x^66))) \\ Franklin T. Adams-Watters, May 26 2011
(Python)
an = an1 = 1
while an<10**5:
print(an)
an1 += an*3
an = an1 - an*3 # Alex Ratushnyak, Apr 20 2012
(Magma) [n le 2 select 1 else Self(n-1) + 3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Oct 17 2012
(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
CROSSREFS
Cf. A006131, A015440, A049310, A052533, A140167, A175291 (Pisano periods), A099232 (partial sums), A274977.
Sequence in context: A323655 A062306 A323105 * A140167 A182228 A352007
KEYWORD
nonn,easy
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)