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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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]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

Examples

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

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.
• 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.

Crossrefs

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

Cf. A209927, A356033.

Programs

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

Magma

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

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 *)

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

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

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)

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)