%I #74 Dec 10 2022 01:44:06

%S 1,1,7,25,103,409,1639,6553,26215,104857,419431,1677721,6710887,

%T 26843545,107374183,429496729,1717986919,6871947673,27487790695,

%U 109951162777,439804651111,1759218604441,7036874417767,28147497671065

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

%C Binomial transform of A102901.

%C Hankel transform is = 1,6,0,0,0,0,0,0,0,0,0,0,... - _Philippe Deléham_, Nov 02 2008

%D Maria Paola Bonacina and Nachum Dershowitz, Canonical Inference for Implicational Systems, in Automated Reasoning, Lecture Notes in Computer Science, Volume 5195/2008, Springer-Verlag.

%H Reinhard Zumkeller, <a href="/A102900/b102900.txt">Table of n, a(n) for n = 0..1000</a>

%H A. Abdurrahman, <a href="https://arxiv.org/abs/1909.10889">CM Method and Expansion of Numbers</a>, arXiv:1909.10889 [math.NT], 2019.

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.01796">A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata</a>, arXiv:1503.01796 [math.CO], 2015; see also the <a href="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/CAcount.html">Accompanying Maple Package</a>.

%H Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1503.04249">Odd-Rule Cellular Automata on the Square Grid</a>, arXiv:1503.04249 [math.CO], 2015.

%H N. J. A. Sloane, <a href="http://arxiv.org/abs/1503.01168">On the Number of ON Cells in Cellular Automata</a>, arXiv:1503.01168 [math.CO], 2015.

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

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

%F G.f.: (1-2*x)/(1-3*x-4*x^2).

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

%F a(n) = ceiling(4^n/5) + floor(4^n/5) = (ceiling(4^n/5))^2 - (floor(4^n/5))^2.

%F a(n) + a(n+1) = 2^(2*n+1) = A004171(n).

%F a(n) = Sum_{k=0..n} binomial(2*n-k, 2*k)*2^k. - _Paul Barry_, Jan 20 2005

%F a(n) = upper left term in the 2 X 2 matrix [1,3; 2,2]^n. - _Gary W. Adamson_, Mar 14 2008

%F G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x*(8*4^k-3*(-1)^k)/(x*(8*4^k-3*(-1)^k) + (2*4^k+3*(-1)^k)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, May 28 2013

%F a(n) = 2^(2*n-1) - a(n-1), a(1)=1. - _Ben Paul Thurston_, Dec 27 2015; corrected by _Klaus Purath_, Aug 02 2020

%F From _Klaus Purath_, Aug 02 2020: (Start)

%F a(n) = 4*a(n-1) + 3*(-1)^n.

%F a(n) = 6*4^(n-2) + a(n-2), n>=2. (End)

%t a[n_]:=(MatrixPower[{{2,2},{3,1}},n].{{2},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* _Vladimir Joseph Stephan Orlovsky_, Feb 20 2010 *)

%t LinearRecurrence[{3, 4}, {1, 1}, 30] (* _Vincenzo Librandi_, Dec 28 2015 *)

%o (Haskell)

%o a102900 n = a102900_list !! n

%o a102900_list = 1 : 1 : zipWith (+)

%o (map (* 4) a102900_list) (map (* 3) $ tail a102900_list)

%o -- _Reinhard Zumkeller_, Feb 13 2015

%o (Magma) [n le 2 select 1 else 3*Self(n-1)+4*Self(n-2): n in [1..30]]; // _Vincenzo Librandi_, Dec 28 2015

%o (PARI) a(n)=([0,1; 4,3]^n*[1;1])[1,1] \\ _Charles R Greathouse IV_, Mar 28 2016

%o (SageMath)

%o A102900=BinaryRecurrenceSequence(3,4,1,1)

%o [A102900(n) for n in range(51)] # _G. C. Greubel_, Dec 09 2022

%Y Cf. A001045, A004171, A046717, A086901, A102901, A247666 (which appears to be the run length transform of this sequence).

%K easy,nonn

%O 0,3

%A _Paul Barry_, Jan 17 2005