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

Author

Paul Barry, Jan 17 2005

Keywords

• easy
• nonn

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).

Crossrefs

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

Programs

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

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 *)

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

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)