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

%I #108 Mar 18 2024 13:34:17

%S 1,1,5,13,41,121,365,1093,3281,9841,29525,88573,265721,797161,2391485,

%T 7174453,21523361,64570081,193710245,581130733,1743392201,5230176601,

%U 15690529805,47071589413,141214768241,423644304721,1270932914165,3812798742493,11438396227481

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

%C 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

%C 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

%C The sequence corresponds to the (1,1) term of the matrix [1,2;2,1]^n. - _Simone Severini_, Dec 04 2004

%C 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

%C 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

%C Equals INVERTi transform of A104934: (1, 2, 8, 28, 100, 356, 1268, ...). - _Gary W. Adamson_, Jul 21 2010

%C 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

%C 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

%C 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

%C 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

%C a(n) is the sum, for k=0..3, of the number of walks of length n between two vertices at distance k of the cube graph. - _Miquel A. Fiol_, Mar 09 2024

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

%H Vincenzo Librandi, <a href="/A046717/b046717.txt">Table of n, a(n) for n = 0..1000</a>

%H C. Banderier and D. Merlini, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/fpsac02.pdf">Lattice paths with an infinite set of jumps</a>, FPSAC02, Melbourne, 2002.

%H P. D. Jarvis and J. G. Sumner, <a href="http://arxiv.org/abs/1307.5574">Matrix group structure and Markov invariants in the strand symmetric phylogenetic substitution model</a>, arXiv preprint arXiv:1307.5574 [q-bio.PE], 2013.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (2,3).

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

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

%F a(n) = Sum_{k=0..n} binomial(n, 2k)2^(2k). - _Paul Barry_, Feb 26 2003

%F Binomial transform of A000302 (powers of 4) with interpolated zeros. Inverse binomial transform of A081294. - _Paul Barry_, Mar 17 2003

%F E.g.f.: exp(x)cosh(2x). - _Paul Barry_, Mar 17 2003

%F 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

%F 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

%F a(n) = Sum_{k=0..n} A098158(n,k)*4^(n-k). - _Philippe Deléham_, Dec 26 2007

%F a(n) = (3^n + (-1)^n)/2. - _M. F. Hasler_, Mar 20 2008

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

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

%F 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

%F 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

%F 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

%p 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

%p seq(denom(((-2)^(2*n)+6^(2*n))/((-2)^n+6^n)),n=0..26)

%t Table[(3^n + (-1)^n)/2, {n, 0, 30}] (* _Artur Jasinski_, Dec 10 2006 *)

%t CoefficientList[ Series[(1 - x)/(1 - 2x - 3x^2), {x, 0, 30}], x] (* _Robert G. Wilson v_, Apr 04 2011 *)

%t Table[ MatrixPower[{{1, 2}, {1, 1}}, n][[1, 1]], {n, 0, 30}] (* _Robert G. Wilson v_, Apr 04 2011 *)

%o (PARI) {a(n) = (3^n+(-1)^n)/2};

%o for(n=0,30, print1(a(n), ", ")) /* modified by _G. C. Greubel_, Jan 07 2018 */

%o (Sage) [lucas_number2(n,2,-3)/2 for n in range(0, 27)] # _Zerinvary Lajos_, Apr 30 2009

%o (Magma) [n le 2 select 1 else 2*Self(n-1)+3*Self(n-2): n in [1..35]]; // _Vincenzo Librandi_, Jul 21 2013

%o (PARI) x='x+O('x^30); Vec((1-x)/((1+x)*(1-3*x))) \\ _G. C. Greubel_, Jan 07 2018

%o (Magma) [(3^n + (-1)^n)/2: n in [0..30]]; // _G. C. Greubel_, Jan 07 2018

%Y The first difference sequence of A015518.

%Y Row sums of triangle A080928.

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

%Y Cf. A015518.

%Y Cf. A104934. - _Gary W. Adamson_, Jul 21 2010

%K nonn,easy

%O 0,3

%A _Gervais Deroo_ and M. Deroo

%E Description corrected by and more terms from _Michael Somos_