%I #84 Sep 08 2022 08:44:50
%S 0,1,3,12,45,171,648,2457,9315,35316,133893,507627,1924560,7296561,
%T 27663363,104879772,397629405,1507527531,5715470808,21668995017,
%U 82153397475,311467177476,1180861724853,4476986706987,16973545295520
%N a(n) = 3*a(n-1) + 3*a(n-2), a(0)=0, a(1)=1.
%C Scaled Chebyshev U-polynomials evaluated at I*sqrt(3)/2.
%C Number of zeros in the substitution system {0 -> 1111100, 1 -> 10} at step n from initial string "1" (1 -> 10 -> 101111100 -> ...). - _Ilya Gutkovskiy_, Apr 10 2017
%C a(n+1) is the number of compositions of n having parts 1 and 2, both of three kinds. - _Gregory L. Simay_, Sep 21 2017
%C More generally, define a(n) = k*a(n-1) + k*a(n-2), a(0) = 0 and a(1) = 1. Then g.f. a(n) = 1/(1 - k*x - k*x^2) and a(n+1) is the number of compositions of n having parts 1 and 2, both of k kinds. - _Gregory L. Simay_, Sep 22 2017
%H Reinhard Zumkeller, <a href="/A030195/b030195.txt">Table of n, a(n) for n = 0..1000</a>
%H Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
%H A. F. Horadam, <a href="http://www.fq.math.ca/Scanned/5-5/horadam.pdf">Special properties of the sequence W_n(a,b; p,q)</a>, Fib. Quart., 5.5 (1967), 424-434. Case n->n+1, a=0,b=1; p=q=3.
%H Tanya Khovanova, <a href="http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html">Recursive Sequences</a>
%H W. Lang, <a href="http://www.fq.math.ca/Scanned/38-5/lang.pdf">On polynomials related to powers of the generating function of Catalan's numbers</a>, Fib. Quart. 38 (2000) 408-419. Eqs. (39), (41) and (45), rhs, m=3.
%H <a href="/index/Ch#Cheby">Index entries for sequences related to Chebyshev polynomials.</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (3,3).
%F a(n+1) = (-I*sqrt(3))^n*U(n, I*sqrt(3)/2).
%F G.f.: x / (1 - 3*x - 3*x^2).
%F a(n+1) = Sum_{k=0..floor(n/2)} 3^(n-k)*binomial(n-k, k). - _Emeric Deutsch_, Nov 14 2001
%F a(n) = (p^n - q^n)/sqrt(21); p = (3 + sqrt 21)/2, q = (3 - sqrt 21)/2. - _Gary W. Adamson_, Jul 02 2003
%F For n > 0, a(n) = Sum_{k=0..n-1} (2^k)*A063967(n-1,k). - _Gerald McGarvey_, Jul 23 2006
%F a(n+1) = Sum_{k=0..n} 2^k*A063967(n,k). - _Philippe Deléham_, Nov 03 2006
%e G.f. = x + 3*x^2 + 12*x^3 + 45*x^4 + 171*x^5 + 648*x^6 + 2457*x^7 + ...
%t CoefficientList[Series[1/(1-3x-3x^2), {x, 0, 25}], x] (* _Zerinvary Lajos_, Mar 22 2007 *)
%t LinearRecurrence[{3, 3}, {0, 1}, 24] (* Or *)
%t RecurrenceTable[{a[n] == 3 a[n - 1] + 3 a[n - 2], a[0] == 0, a[1] == 1}, a, {n, 0, 23}] (* _Robert G. Wilson v_, Aug 18 2012 *)
%o (Sage) [lucas_number1(n,3,-3) for n in range(0, 25)] # _Zerinvary Lajos_, Apr 22 2009
%o (PARI) {a(n) = n--; polchebyshev(n, 2, I*sqrt(3)/2) * (-I*sqrt(3))^n};
%o (Haskell)
%o a030195 n = a030195_list !! n
%o a030195_list =
%o 0 : 1 : map (* 3) (zipWith (+) a030195_list (tail a030195_list))
%o -- _Reinhard Zumkeller_, Oct 14 2011
%o (Magma) I:=[0,1]; [n le 2 select I[n] else 3*Self(n-1) + 3*Self(n-2): n in [1..30]]; // _G. C. Greubel_, Jan 24 2018
%Y Equals round(A085480(n)/sqrt(21)).
%Y Cf. A175290 (Pisano periods), A000045, A002605, A172010, A057088, A057089, A057090, A057091, A057092, A057093.
%Y Cf. A026150, A028859, A028860, A080040, A083337, A106435, A108898, A125145.
%K nonn,easy
%O 0,3
%A _Wolfdieter Lang_
%E Edited by _Ralf Stephan_, Aug 02 2004
%E I simplified the definition. As a result the offsets in some of the formulas may need to shifted by 1. - _N. J. A. Sloane_, Apr 01 2006
%E Formulas shifted to match offset. - _Charles R Greathouse IV_, Jan 31 2011