cp's OEIS Frontend

A003688 a(n) = 3*a(n-1) + a(n-2), with a(1)=1 and a(2)=4.

%I A003688 #129 Jul 26 2024 15:02:10
%S A003688 1,4,13,43,142,469,1549,5116,16897,55807,184318,608761,2010601,
%T A003688 6640564,21932293,72437443,239244622,790171309,2609758549,8619446956,
%U A003688 28468099417,94023745207,310539335038,1025641750321,3387464586001,11188035508324,36951571110973
%N A003688 a(n) = 3*a(n-1) + a(n-2), with a(1)=1 and a(2)=4.
%C A003688 Number of 2-factors in K_3 X P_n.
%C A003688 Form the graph with matrix [1,1,1,1;1,1,1,0;1,1,0,1;1,0,1,1]. The sequence 1,1,4,13,... with g.f. (1-2*x)/(1-3*x-x^2) counts closed walks of length n at the vertex of degree 5. - _Paul Barry_, Oct 02 2004
%C A003688 a(n) is term (1,1) in M^n, where M is the 3x3 matrix [1,1,2; 1,1,1; 1,1,1]. - _Gary W. Adamson_, Mar 12 2009
%C A003688 Starting with 1, INVERT transform of A003945: (1, 3, 6, 12, 24, ...). - _Gary W. Adamson_, Aug 05 2010
%C A003688 Row sums of triangle
%C A003688 m/k.|..0.....1.....2.....3.....4.....5.....6.....7
%C A003688 ==================================================
%C A003688 .0..|..1
%C A003688 .1..|..1.....3
%C A003688 .2..|..1.....3.....9
%C A003688 .3..|..1.....6.....9.....27
%C A003688 .4..|..1.....6....27.....27...81
%C A003688 .5..|..1.....9....27....108...81...243
%C A003688 .6..|..1.....9....54....108..405...243...729
%C A003688 .7..|..1....12....54....270..405..1458...729..2187
%C A003688 which is the triangle for numbers 3^k*C(m,k) with duplicated diagonals. - _Vladimir Shevelev_, Apr 12 2012
%C A003688 Pisano period lengths: 1, 3, 1, 6, 12, 3, 16, 12, 6, 12, 8, 6, 52, 48, 12, 24, 16, 6, 40, 12, ... - _R. J. Mathar_, Aug 10 2012
%C A003688 a(n-1) is the number of length-n strings of 4 letters {0,1,2,3} with no two adjacent nonzero letters identical. The general case (strings of L letters) is the sequence with g.f. (1+x)/(1-(L-1)*x-x^2). - _Joerg Arndt_, Oct 11 2012
%D A003688 F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H A003688 Vincenzo Librandi, <a href="/A003688/b003688.txt">Table of n, a(n) for n = 1..1000</a>
%H A003688 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>
%H A003688 Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.
%H A003688 C. Bautista-Ramos and C. Guillen-Galvan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Bautista/bautista4.html">Fibonacci numbers of generalized Zykov sums</a>, J. Integer Seq., 15 (2012), Article 12.7.8.
%H A003688 F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H A003688 F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H A003688 F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A003688 Sergio Falcón and Ángel Plaza, <a href="http://dx.doi.org/10.1016/j.chaos.2006.09.022">On the Fibonacci k-numbers</a>, Chaos, Solitons & Fractals 2007; 32(5): 1615-24.
%H A003688 Taras Goy and Mark Shattuck, <a href="https://doi.org/10.2478/amsil-2023-0027">Determinants of Toeplitz-Hessenberg Matrices with Generalized Leonardo Number Entries</a>, Ann. Math. Silesianae (2023). See p. 15.
%H A003688 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=419">Encyclopedia of Combinatorial Structures 419</a>
%H A003688 Milan Janjic, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html">On Linear Recurrence Equations Arising from Compositions of Positive Integers</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.
%H A003688 Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H A003688 <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,1).
%F A003688 a(n) = ((13 - sqrt(13))/26)*((3 + sqrt(13))/2)^n + ((13 + sqrt(13))/26)*((3 - sqrt(13))/2)^n. - _Paul Barry_, Oct 02 2004
%F A003688 a(n) = Sum_{k=0..n} 2^k*A055830(n,k). - _Philippe Deléham_, Oct 18 2006
%F A003688 Starting (1, 1, 4, 13, 43, 142, 469, ...), row sums (unsigned) of triangle A136159. - _Gary W. Adamson_, Dec 16 2007
%F A003688 G.f.: x*(1+x)/(1-3*x-x^2). - _Philippe Deléham_, Nov 03 2008
%F A003688 a(n) = A006190(n) + A006190(n-1). - _Sergio Falcon_, Nov 26 2009
%F A003688 For n>=2, a(n) = F_n(3) + F_(n+1)(3), where F_n(x) is Fibonacci polynomial (cf. A049310): F_n(x) = Sum_{i=0..floor((n-1)/2)} binomial(n-i-1,i) * x^(n-2*i-1). - _Vladimir Shevelev_, Apr 13 2012
%F A003688 G.f.: G(0)*(1+x)/(2-3*x), where G(k) = 1 + 1/(1 - (x*(13*k-9))/( x*(13*k+4) - 6/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Jun 15 2013
%F A003688 a(n)^2 is the denominator of continued fraction [3,3,...,3, 5, 3,3,...,3], which has n-1 3's before, and n-1 3's after, the middle 5. - _Greg Dresden_, Sep 18 2019
%F A003688 a(n) = Sum_{k=0..n} A046854(n-1,k)*3^k. - _R. J. Mathar_, Feb 10 2024
%F A003688 a(n) = 3^n*Sum_{k=0..n} A374439(n, k)*(-1/3)^k. - _Peter Luschny_, Jul 26 2024
%e A003688 G.f. = x + 4*x^2 + 13*x^3 + 43*x^4 + 142*x^5 + 469*x^6 + 1549*x^7 + 5116*x^8 + ...
%p A003688 with(combinat): a:=n->fibonacci(n,3)-2*fibonacci(n-1,3): seq(a(n), n=2..25); # _Zerinvary Lajos_, Apr 04 2008
%t A003688 a[n_] := (MatrixPower[{{1, 3}, {1, 2}}, n].{{1}, {1}})[[1, 1]]; Table[ a[n], {n, 0, 23}] (* _Robert G. Wilson v_, Jan 13 2005 *)
%t A003688 LinearRecurrence[{3,1},{1,4},30] (* _Harvey P. Dale_, Mar 15 2015 *)
%o A003688 (Magma) [n le 2 select 4^(n-1) else 3*Self(n-1)+Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Aug 19 2011
%o A003688 (PARI) a(n)=([0,1; 1,3]^(n-1)*[1;4])[1,1] \\ _Charles R Greathouse IV_, Aug 14 2017
%o A003688 (SageMath)
%o A003688 @CachedFunction
%o A003688 def a(n): # a = A003688
%o A003688     if (n<3): return 4^(n-1)
%o A003688     else: return 3*a(n-1) + a(n-2)
%o A003688 [a(n) for n in range(1,41)] # _G. C. Greubel_, Dec 26 2023
%Y A003688 Partial sums of A052906. Pairwise sums of A006190.
%Y A003688 Cf. A003945, A006190, A049310, A055830, A136159, A290948.
%Y A003688 Cf. A374439.
%K A003688 nonn,easy
%O A003688 1,2
%A A003688 _Frans J. Faase_
%E A003688 Formula added by _Olivier Gérard_, Aug 15 1997
%E A003688 Name clarified by _Michel Marcus_, Oct 16 2016