%I #26 Sep 08 2022 08:45:00
%S 1,1,4,4,13,13,40,40,121,121,364,364,1093,1093,3280,3280,9841,9841,
%T 29524,29524,88573,88573,265720,265720,797161,797161,2391484,2391484,
%U 7174453,7174453,21523360,21523360,64570081,64570081,193710244
%N a(n) = a(n-1) + 3*a(n-2) - 3*a(n-3), with a(0)=a(1)=1, a(2)=4.
%H G. C. Greubel, <a href="/A052993/b052993.txt">Table of n, a(n) for n = 0..1000</a>
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=1069">Encyclopedia of Combinatorial Structures 1069</a>
%H László Németh and László Szalay, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Nemeth/nemeth8.html">Sequences Involving Square Zig-Zag Shapes</a>, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-3).
%F G.f.: 1/((1-3*x^2)*(1-x)).
%F a(n+2) = 3*a(n) + 1, where a(0) = a(1) = 1.
%F a(n) = -1/2 + Sum((1/4)*(1+3*_alpha)*_alpha^(-1-n), _alpha = RootOf(-1 + 3*_Z^2)).
%F a(n) = Sum{k=0..n} 3^(k/2)*(1-(-1)^k)/(2*sqrt(3)). - _Paul Barry_, Jul 28 2004
%F a(n) = (3^(1+floor((n-1)/2)) - 1)/2. - _Federico Provvedi_, Nov 22 2018
%F a(n)-a(n-1) = A254006(n). - _R. J. Mathar_, Feb 27 2019
%p spec := [S,{S=Prod(Sequence(Prod(Union(Z,Z,Z),Z)),Sequence(Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
%t (3^(1+Floor[(Range@40-1)/2])-1)/2 (* _Federico Provvedi_, Nov 22 2018 *)
%t LinearRecurrence[{1,3,-3}, {1,1,4}, 30] (* or *) RecurrenceTable[{a[n + 2] == 3*a[n] + 1, a[0] == 1, a[1] == 1}, a, {n,0,30}] (* _G. C. Greubel_, Nov 21 2018 *)
%o (PARI) x='x+O('x^30); Vec(1/((1-3*x^2)*(1-x))) \\ _G. C. Greubel_, Nov 21 2018
%o (Magma) I:=[1,1,4]; [n le 3 select I[n] else Self(n-1) +3*Self(n-2) -3*Self(n-3): n in [1..30]]; // _G. C. Greubel_, Nov 21 2018
%o (Sage) s=(1/((1-3*x^2)*(1-x))).series(x,30); s.coefficients(x, sparse=False) # _G. C. Greubel_, Nov 21 2018
%Y Cf. A062318.
%K easy,nonn
%O 0,3
%A encyclopedia(AT)pommard.inria.fr, Jan 25 2000
%E More terms from _James A. Sellers_, Jun 06 2000