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

1, 1, 7, 25, 103, 409, 1639, 6553, 26215, 104857, 419431, 1677721, 6710887, 26843545, 107374183, 429496729, 1717986919, 6871947673, 27487790695, 109951162777, 439804651111, 1759218604441, 7036874417767, 28147497671065

Offset

0,3

Comments

Binomial transform of A102901.

Hankel transform is = 1,6,0,0,0,0,0,0,0,0,0,0,... - Philippe Deléham, Nov 02 2008

References

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.

Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, A Meta-Algorithm for Creating Fast Algorithms for Counting ON Cells in Odd-Rule Cellular Automata, arXiv:1503.01796 [math.CO], 2015; see also the Accompanying Maple Package.

Shalosh B. Ekhad, N. J. A. Sloane, and Doron Zeilberger, Odd-Rule Cellular Automata on the Square Grid, arXiv:1503.04249 [math.CO], 2015.

N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.

Index entries for sequences related to cellular automata

Index entries for linear recurrences with constant coefficients, signature (3,4).

Formula

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

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

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

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

a(n) = Sum_{k=0..n} binomial(2*n-k, 2*k)*2^k. - Paul Barry, Jan 20 2005

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

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

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

From Klaus Purath, Aug 02 2020: (Start)

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

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

Mathematica

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 *)
LinearRecurrence[{3, 4}, {1, 1}, 30] (* Vincenzo Librandi, Dec 28 2015 *)

Prog

(Haskell)
a102900 n = a102900_list !! n
a102900_list = 1 : 1 : zipWith (+)
               (map (* 4) a102900_list) (map (* 3) $ tail a102900_list)
-- Reinhard Zumkeller, Feb 13 2015
(Magma) [n le 2 select 1 else 3*Self(n-1)+4*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Dec 28 2015
(PARI) a(n)=([0, 1; 4, 3]^n*[1; 1])[1, 1] \\ Charles R Greathouse IV, Mar 28 2016
(SageMath)
A102900=BinaryRecurrenceSequence(3, 4, 1, 1)
[A102900(n) for n in range(51)] # G. C. Greubel, Dec 09 2022

Crossrefs

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

Sequence in context: A247173 A141627 A289606 * A155271 A200152 A255280

Adjacent sequences: A102897 A102898 A102899 * A102901 A102902 A102903

Keyword

easy,nonn

Author

Paul Barry, Jan 17 2005

Status

approved