A046717 a(n) = 2*a(n-1) + 3*a(n-2), a(0) = a(1) = 1.

1, 1, 5, 13, 41, 121, 365, 1093, 3281, 9841, 29525, 88573, 265721, 797161, 2391485, 7174453, 21523361, 64570081, 193710245, 581130733, 1743392201, 5230176601, 15690529805, 47071589413, 141214768241, 423644304721, 1270932914165, 3812798742493, 11438396227481

Offset

0,3

Comments

Form the digraph with matrix A = [0,1,1,1;1,0,1,1;1,1,0,1;1,0,1,1]. Then the sequence 0,1,1,5,... or (3^(n-1)-(-1)^n)/2+0^n/3 with g.f. x(1-x)/(1-2x-3x^2) corresponds to the (1,2) term of A^n. - Paul Barry, Oct 02 2004

3*a(n+1) + a(n) = 4*A060925(n); a(n+1) = A015518(n) + A060925(n); a(n+1) - 6*A015518(n) = (-1)^n. - Creighton Dement, Nov 15 2004

The sequence corresponds to the (1,1) term of the matrix [1,2;2,1]^n. - Simone Severini, Dec 04 2004

The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 4 times the bottom to get the new top. The limit of the sequence of fractions is 2. - Cino Hilliard, Sep 25 2005

a(n)^2 + (2*A015518(n))^2 = a(2n). E.g., a(3) = 13, 2*A015518(3) = 14, A046717(6) = 365. 13^2 + 14^2 = 365. - Gary W. Adamson, Jun 17 2006

Equals INVERTi transform of A104934: (1, 2, 8, 28, 100, 356, 1268, ...). - Gary W. Adamson, Jul 21 2010

a(n) is the number of compositions of n when there are 1 type of 1 and 4 types of other natural numbers. - Milan Janjic, Aug 13 2010

An elephant sequence, see A175655. For the central square just one A[5] vector, with decimal value 341, leads to this sequence (without the first leading 1). For the corner squares this vector leads to the companion sequence A015518 (without the leading 0). - Johannes W. Meijer, Aug 15 2010

Pisano period lengths: 1, 1, 2, 1, 4, 2, 6, 4, 2, 4, 10, 2, 6, 6, 4, 8, 16, 2, 18, 4, ... - R. J. Mathar, Aug 10 2012

a(n) is the number of words of length n over a ternary alphabet whose position in the lexicographic order is a multiple of two. - Alois P. Heinz, Apr 13 2022

References

John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

C. Banderier and D. Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.

P. D. Jarvis and J. G. Sumner, Matrix group structure and Markov invariants in the strand symmetric phylogenetic substitution model, arXiv preprint arXiv:1307.5574 [q-bio.PE], 2013.

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

Formula

G.f.: (1-x)/((1+x)*(1-3*x)).

a(n) = (3^n + (-1)^n)/2.

a(n) = Sum_{k=0..n} binomial(n, 2k)2^(2k). - Paul Barry, Feb 26 2003

Binomial transform of A000302 (powers of 4) with interpolated zeros. Inverse binomial transform of A081294. - Paul Barry, Mar 17 2003

E.g.f.: exp(x)cosh(2x). - Paul Barry, Mar 17 2003

a(n) = ceiling(3^n/4) + floor(3^n/4) = ceiling(3^n/4)^2 - floor(3^n/4)^2. - Paul Barry, Jan 17 2005

a(n) = Sum_{k=0..n} Sum_{j=0..n} C(n,j)C(n-j,k)*(1+(-1)^(j-k))/2. - Paul Barry, May 21 2006

a(n) = Sum_{k=0..n} A098158(n,k)*4^(n-k). - Philippe Deléham, Dec 26 2007

a(n) = (3^n + (-1)^n)/2. - M. F. Hasler, Mar 20 2008

a(n) = 2 A015518(n) + (-1)^n; for n > 0, a(n) = A080925(n). - M. F. Hasler, Mar 20 2008

((1 + sqrt4)^n + (1 - sqrt4)^n)/2. The offset is 0. a(3)=13. - Al Hakanson (hawkuu(AT)gmail.com), Nov 22 2008

If p[1]=1 and p[i]=4 (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.: G(0)/2, where G(k) = 1 + 1/(1 - x*(4*k-1)/(x*(4*k+3) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013

G.f.: G(0)/2, where G(k) = 1 + (-1)^k/(3^k - 3*9^k*x/(3*3^k*x + (-1)^k/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Oct 17 2013

Maple

a[0]:=1:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+3*a[n-2] od: seq(a[n], n=0..33); # Zerinvary Lajos, Dec 14 2008
seq(denom(((-2)^(2*n)+6^(2*n))/((-2)^n+6^n)), n=0..26)

Mathematica

Table[(3^n + (-1)^n)/2, {n, 0, 30}] (* Artur Jasinski, Dec 10 2006 *)
CoefficientList[ Series[(1 - x)/(1 - 2x - 3x^2), {x, 0, 30}], x]  (* Robert G. Wilson v, Apr 04 2011 *)
Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* Robert G. Wilson v, Apr 04 2011 *)

Prog

(PARI) {a(n) = (3^n+(-1)^n)/2};
for(n=0, 30, print1(a(n), ", ")) /* modified by G. C. Greubel, Jan 07 2018 */
(Sage) [lucas_number2(n, 2, -3)/2 for n in range(0, 27)] # Zerinvary Lajos, Apr 30 2009
(Magma) [n le 2 select 1 else 2*Self(n-1)+3*Self(n-2): n in [1..35]]; // Vincenzo Librandi, Jul 21 2013
(PARI) x='x+O('x^30); Vec((1-x)/((1+x)*(1-3*x))) \\ G. C. Greubel, Jan 07 2018
(Magma) [(3^n + (-1)^n)/2: n in [0..30]]; // G. C. Greubel, Jan 07 2018

Crossrefs

The first difference sequence of A015518.

Row sums of triangle A080928.

The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.

Cf. A015518.

Cf. A104934. - Gary W. Adamson, Jul 21 2010

Sequence in context: A182300 A080925 A164907 * A352916 A085601 A147718

Adjacent sequences: A046714 A046715 A046716 * A046718 A046719 A046720

Keyword

nonn,easy

Author

Gervais Deroo and M. Deroo

Extensions

Description corrected by and more terms from Michael Somos

Status

approved