A087206 a(n) = 2*a(n-1) + 4*a(n-2); with a(0)=1, a(1)=4.

1, 4, 12, 40, 128, 416, 1344, 4352, 14080, 45568, 147456, 477184, 1544192, 4997120, 16171008, 52330496, 169345024, 548012032, 1773404160, 5738856448, 18571329536, 60098084864, 194481487872, 629355315200, 2036636581888

Offset: 0

Author

Paul Barry, Aug 25 2003

Keywords

• easy
• nonn

Comments

Binomial transform of A056487. Unsigned version of A152174.

Number of words of length n over the alphabet {1,2,3,4} such that no odd letter is followed by an odd letter. - Armend Shabani, Feb 18 2017

From Sean A. Irvine, Jun 06 2025: (Start)

Also, the number of walks of length n starting at 0 in the following graph:

1---2

|\ /|

| 0 |

|/ \|

4---3. (End)

Links

• Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration, arXiv:math/0410429 [math.CO], 2004. See Table II, p. 4.
• Sean A. Irvine, Walks on Graphs.
• N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
• Index entries for linear recurrences with constant coefficients, signature (2,4).

Crossrefs

Cf. A060925, A063782, A253064.

Equals (1/2) * A063727(n-1). Cf. A006483.

Programs

Mathematica

LinearRecurrence[{2, 4}, {1, 4}, 25] (* Jean-François Alcover, Sep 21 2017 *)

Formula

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

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

a(n) = 2^n*Fibonacci(n+2). - Paul Barry, Mar 22 2004

a(n) = ((1+sqrt(5))^n-(1-sqrt(5))^n)/sqrt(80). Offset 2. a(4)=12. - Al Hakanson (hawkuu(AT)gmail.com), Apr 11 2009

G.f.: 1/(-2x-1/(-2x-1)). - Paul Barry, Mar 24 2010

Extensions

Comment corrected by Philippe Deléham, Nov 27 2008