login
This site is supported by donations 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)
54
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 strings 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={[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

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

REFERENCES

A. G. Shannon, 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.

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 436

M. Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, 2014; http://matinf.pmfbl.org/wp-content/uploads/2015/01/za-arhiv-18.-1.pdf

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 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, 2012. - From N. J. A. Sloane, Oct 23 2012

A. K. Whitford, Binet's formula generalized, Fib. Quart., 15 (1977), pp. 21, 24, 29.

Index entries for linear recurrences with constant coefficients, signature (1,3).

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 2a = 1+sqrt(13), 2b = 1-sqrt(13). - G. C. Greubel, Aug 30 2015

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->sum(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}]

f[n_] = Product[(1 + 12*Cos[k*Pi/n]^2), {k, 1, Floor[(n - 1)/2]}]; Table[FullSimplify[ExpandAll[f[n]]], {n, 0, 15}] N[%] (* Roger L. Bagula and Gary W. Adamson, Nov 21 2008 *)

LinearRecurrence[{1, 3}, {1, 1}, 100] (* Vincenzo Librandi, Oct 17 2012 *)

RecurrenceTable[{a[n]== a[n-1] + 3*a[n-2], a[0]== 1, a[1]== 1}, a, {n, 0, 100}] (* G. C. Greubel, Aug 30 2015 *)

PROG

(Sage)

from sage.combinat.sloane_functions import recur_gen2

it = recur_gen2(1, 1, 1, 3)

[it.next() for i in range(30)] # Zerinvary Lajos, Jun 25 2008

(Sage) [lucas_number1(n, 1, -3) for n in xrange(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**15:

. 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

CROSSREFS

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

Sequence in context: A102991 A062306 * A140167 A182228 A182646 A190646

Adjacent sequences:  A006127 A006128 A006129 * A006131 A006132 A006133

KEYWORD

nonn,easy,changed

AUTHOR

N. J. A. Sloane

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified April 26 15:40 EDT 2017. Contains 285446 sequences.