A087206 -id:A087206 - cp's OEIS frontend

A063727 a(n) = 2a(n-1) + 4a(n-2), a(0)=1, a(1)=2.

1, 2, 8, 24, 80, 256, 832, 2688, 8704, 28160, 91136, 294912, 954368, 3088384, 9994240, 32342016, 104660992, 338690048, 1096024064, 3546808320, 11477712896, 37142659072, 120196169728, 388962975744, 1258710630400

Offset: 0

Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Aug 12 2001

Essentially the same as A085449.
Convergents to 2*golden ratio = (1+sqrt(5)).
Number of ways to tile an n-board with two types of colored squares and four types of colored dominoes.
The same sequence may be obtained by the following process. Starting a priori with the fraction 1/1, the numerators of fractions built according to the rule: add top and bottom to get the new bottom, add top and 5 times the bottom to get the new top. The limit of the sequence of fractions is sqrt(5). - Cino Hilliard, Sep 25 2005
a(n) is also the quasi-diagonal element A(i-1,i)=A(1,i-1) of matrix A(i,j) whose elements in first row A(1,k) and first column A(k,1) equal k-th Fibonacci Fib(k) and the generic element is the sum of adjacent (previous) in row and column minus the absolute value of their difference. - Carmine Suriano, May 13 2010
Equals INVERT transform of A006131: (1, 1, 5, 9, 29, 65, 181, ...). - Gary W. Adamson, Aug 12 2010
For positive n, a(n) equals the permanent of the n X n tridiagonal matrix with 2's along the three central diagonals. - John M. Campbell, Jul 19 2011
The numbers composing the denominators of the fractional limit to A134972. - Seiichi Kirikami, Mar 06 2012
Pisano period lengths:  1, 1, 8, 1, 5, 8, 48, 1, 24, 5, 10, 8, 42, 48, 40, 1, 72, 24, 18, 5, ... - R. J. Mathar, Aug 10 2012

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 235.
John Derbyshire, Prime Obsession, Joseph Henry Press, April 2004, see p. 16.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Harry J. Smith)
J. Borowska and L. Lacinska, Recurrence form of determinant of a heptadiagonal symmetric Toeplitz matrix, J. Appl. Math. Comp. Mech. 13 (2014) 19-16, remark 2 for permanent of tridiagonal Toeplitz matrices a=2, b=2.
Index entries for linear recurrences with constant coefficients, signature (2,4).
Index entries for sequences related to Chebyshev polynomials.

Cf. A006483, A103435, A006131, A269991.
Second row of A234357. Row sums of triangle A016095.
The following sequences (and others) belong to the same family: A001333, A000129, A026150, A002605, A046717, A015518, A084057, A063727, A002533, A002532, A083098, A083099, A083100, A015519.

List([0..25],n->2^n*Fibonacci(n+1)); # Muniru A Asiru, Nov 24 2018

[n le 2 select n else 2*Self(n-1) + 4*Self(n-2): n in [1..30]]; // G. C. Greubel, Jan 07 2018

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=2*a[n-1]+4*a[n-2]od: seq(a[n], n=1..33); # Zerinvary Lajos, Dec 15 2008

a[n_]:=(MatrixPower[{{1,5},{1,1}},n].{{1},{1}})[[2,1]]; Table[Abs[a[n]],{n,-1,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 19 2010 *)
CoefficientList[Series[1/(1 - 2 x - 4 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 31 2014 *)
LinearRecurrence[{2, 4}, {1, 2}, 50] (* G. C. Greubel, Jan 07 2018 *)

s(n)=if(n<2,n+1,(s(n-1)+(s(n-2)*2))*2); for(n=0,32,print(s(n)))

{ for (n=0, 200, if (n>1, a=2*a1 + 4*a2; a2=a1; a1=a, if (n, a=a1=2, a=a2=1)); write("b063727.txt", n, " ", a) ) } \\ Harry J. Smith, Aug 28 2009

[lucas_number1(n,2,-4) for n in range(1, 26)] # Zerinvary Lajos, Apr 22 2009

a(n) = 2 * A087206(n+1).
From Vladeta Jovovic, Aug 16 2001: (Start)
a(n) = sqrt(5)/10*((1+sqrt(5))^(n+1) - (1-sqrt(5))^(n+1)).
G.f.: 1/(1-2*x-4*x^2). (End)
From Mario Catalani (mario.catalani(AT)unito.it), Jun 13 2003: (Start)
a(2*n) = 4*a(n-1)^2 + a(n)^2.
A084057(n+1)/a(n) converges to sqrt(5). (End)
E.g.f.: exp(x)*(cosh(sqrt(5)*x)+sinh(sqrt(5)*x)/sqrt(5)). - Paul Barry, Sep 20 2003
a(n) = 2^n*Fibonacci(n+1). - Vladeta Jovovic, Oct 25 2003
a(n) = Sum_{k=0..floor(n/2)} C(n, 2*k+1)*5^k. - Paul Barry, Nov 15 2003
a(n) = U(n, i/2)*(-i*2)^n, i^2=-1. - Paul Barry, Nov 17 2003
Simplified formula: ((1+sqrt(5))^n-(1-sqrt(5))^n)/sqrt(20). Offset 1. a(3)=8. - Al Hakanson (hawkuu(AT)gmail.com), Jan 03 2009
First binomial transform of 1,1,5,5,25,25. - Al Hakanson (hawkuu(AT)gmail.com), Jul 20 2009
a(n) = A(n-1,n) = A(n,n-1); A(i,j) = A(i-1,j) + A(i,j-1) - abs(A(i-1,j) - A(i,j-1)). - Carmine Suriano, May 13 2010
G.f.: G(0) where G(k) = 1 + 2*x*(1+2*x)/(1 - 2*x*(1+2*x)/(2*x*(1+2*x) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 31 2013
G.f.: G(0)/(2*(1-x)), where G(k) = 1 + 1/(1 - x*(5*k-1)/(x*(5*k+4) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
G.f.: Q(0)/2 , where Q(k) = 1 + 1/(1 - x*(4*k+2 + 4*x )/( x*(4*k+4 + 4*x ) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Sep 21 2013
Sum_{n>=0} 1/a(n) = A269991. - Amiram Eldar, Feb 01 2021

Better description from Jason Earls and Vladeta Jovovic, Aug 16 2001

Incorrect comment removed by Greg Dresden, Jun 02 2020

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

Original entry on oeis.org

1, 3, 3, 5, 3, 9, 5, 11, 3, 9, 9, 15, 5, 15, 11, 21, 3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85, 3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27

Offset: 0

Hans Havermann, May 26 2002

Number of 1's in n-th row of triangle in A071036.
Number of odd coefficients in (x^2+x+1)^n. - Benoit Cloitre, Sep 05 2003. This result was given in Wolfram (1983). - N. J. A. Sloane, Feb 17 2015
This is also the odd-rule cellular automaton defined by OddRule 007 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015
This is the Run Length Transform of S(n) = Jacobsthal(n+2) (cf. A001045). The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product). - N. J. A. Sloane, Sep 05 2014

			May be arranged into blocks of sizes 1,1,2,4,8,16,...:
1,
3,
3, 5,
3, 9, 5, 11,
3, 9, 9, 15, 5, 15, 11, 21,
3, 9, 9, 15, 9, 27, 15, 33, 5, 15, 15, 25, 11, 33, 21, 43,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63, 5, 15, 15, 25, 15, 45, 25, 55, 11, 33, 33, 55, 21, 63, 43, 85,
3, 9, 9, 15, 9, 27, 15, 33, 9, 27, 27, ...
... - _N. J. A. Sloane_, Sep 05 2014
.
From _Omar E. Pol_, Mar 15 2015: (Start)
Apart from the initial 1, the sequence can be written also as an irregular tetrahedron T(s,r,k) = A001045(r+2) * a(k), s>=1, 1<=r<=s, 0<=k<=(A011782(s-r)-1) as shown below (see also _Joerg Arndt_'s equivalent program):
3;
..
3;
5;
.......
3,   9;
5;
11;
...............
3,   9,  9, 15;
5,  15;
11;
21;
...............................
3,   9,  9, 15,  9, 27, 15, 33;
5,  15, 15, 25;
11, 33;
21;
43;
..............................................................
3,   9,  9, 15,  9, 27, 15, 33, 9, 27, 27, 45, 15, 45, 33, 63;
5,  15, 15, 25, 15, 45, 25, 55;
11, 33, 33, 55;
21, 63;
43;
85;
...
Note that every row r is equal to A001045(r+2) times the beginning of the sequence itself, thus in 3D every column contains the same number.
(End)

S. Wolfram, A New Kind of Science, Wolfram Media, 2002; Chapter 3.

N. J. A. Sloane, Table of n, a(n) for n = 0..16383 (first 1024 terms from T. D. Noe)
Joerg Arndt, A071053 (number of odd terms in expansion of (1+x+x^2)^n), SeqFan Mailing List, Mar 09 2015.
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.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Janko Gravner and Alexander E. Holroyd, Percolation and Disorder-Resistance in Cellular Automata, Annals of Probability, volume 43, number 4, 2015, pages 1731-1776. Also arxiv:1304.7301 [math.PR], 2013-2015 and second author's copy. See Fig. 1.1 (left).
S. Kropf, S. Wagner, q-Quasiadditive functions, arXiv:1605.03654 [math.CO], 2016.
N. Pitsianis, P. Tsalides, G. L. Bleris, A. Thanailakis & H. C. Card, Deterministic one-dimensional cellular automata, Journal of Statistical Physics, 56(1-2), 99-112, 1989. [Discusses Rule 150]
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n
T. Sillke and Helmut Postl, Odd trinomials: t(n) = (1+x+x^2)^n [Cached copy, with permission]
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168 [math.CO], 2015.
S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55 (1983), 601--644.
Index entries for sequences related to cellular automata

Cf. A038184, A118110, A071036, A001045, A253102, A020987, A246035, A245562, A087206.

a[n_] := Total[CoefficientList[(x^2 + x + 1)^n, x, Modulus -> 2]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 05 2018 *)

b(n) = { (2^n - (-1)^n) / 3; }  \\ A001045
a(n)=
{
    if ( n==0, return(1) );
    \\ Use  a( 2^k * t ) = a(t)
    n \= 2^valuation(n,2);
    if ( n==1, return(3) );  \\ Use a(2^k) == 3
    \\ now n is odd
    my ( v1 = valuation(n+1, 2) );
    \\ Use a( 2^k - 1 ) = A001045( 2 + k ):
    if ( n == 2^v1 - 1 ,  return( b( v1 + 2 ) ) );
    my( k2 = 1, k = 0 );
    while ( k2 < n,  k2 <<= 1; k+=1 );
    if ( k2 > n, k2 >>= 1; k-=1 );
    my( t = n - k2 );
    \\ here  n == 2^k + 1 where k maximal
    \\ Use the following:
    \\ a( 2^k + t ) =  3 * a(t)  if  t <= 2^(k-1)
    \\ a( 2^k + 2^(k-1) + t ) =  5 * a(t)  if  t <= 2^(k-2)
    \\ a( 2^k + 2^(k-1) + 2^(k-2) + t ) =  11* a(t)  if  t <= 2^(k-3)
    \\  ... etc. ...
    \\ a( 2^k + ... + 2^(k-s) + t ) = A001045(s+2) * a(t)  if  t <= 2^((k-1)-s)
    my ( s=1 );
    while ( 1 ,
        k2 >>= 1;
        if ( t <= k2 ,  return(  b(s+2) * a(t) ) );
        t -= k2;
        s += 1;
    );
}
\\ Joerg Arndt, Mar 15 2015, from SeqFan Mailing List, Mar 09 2015

a(n) = Product_{i in row n of A245562} A001045(i+2) [Sillke]. For example, a(11) = A001045(3)*A001045(4) = 3*5 = 15. - N. J. A. Sloane, Aug 10 2014
Floor((a(n)-1)/4) mod 2 = A020987(n). - Ralf Stephan, Mar 18 2004
a(2*n) = a(n); a(2*n+1) = a(n) + 2*a(floor(n/2)). - Peter J. Taylor, Mar 26 2020
Sum_{k = 0..2^n-1} a(k) = A087206(n). - Linhua Zou, Jun 13 2025

Entry revised by N. J. A. Sloane, Aug 13 2014

A056487 a(n) = 5^(n/2) for n even, a(n) = 3*5^((n-1)/2) for n odd.

Original entry on oeis.org

1, 3, 5, 15, 25, 75, 125, 375, 625, 1875, 3125, 9375, 15625, 46875, 78125, 234375, 390625, 1171875, 1953125, 5859375, 9765625, 29296875, 48828125, 146484375, 244140625, 732421875, 1220703125, 3662109375, 6103515625, 18310546875, 30517578125, 91552734375

Offset: 0

Marks R. Nester

Apparently identical to A111386! Is this a theorem? - Klaus Brockhaus, Jul 21 2009

For n > 1, number of necklaces with n-1 beads and 5 colors that are the same when turned over and hence have reflection symmetry. - Herbert Kociemba, Nov 24 2016

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Index entries for linear recurrences with constant coefficients, signature (0,5).

Column 5 of A284855.

Cf. A029744, A038754, A056391, A056451, A087205, A087206, A111386.

[n le 2 select 2*n-1 else 5*Self(n-2): n in [1..28]]; // Bruno Berselli, Mar 24 2011

A056487:=n->3^((1-(-1)^n)/2)*5^((2*n+(-1)^n-1)/4): seq(A056487(n), n=0..40); # Wesley Ivan Hurt, Nov 24 2016

Table[3^((1 - (-1)^n)/2)*5^((2*n + (-1)^n - 1)/4), {n, 0, 30}] (* Wesley Ivan Hurt, Nov 24 2016 *)
CoefficientList[Series[(1 + 3 x)/(1 - 5 x^2), {x, 0, 31}], x] (* Michael De Vlieger, Nov 24 2016 *)
LinearRecurrence[{0, 5}, {1, 3}, 35] (* Vincenzo Librandi, Nov 25 2016 *)
k=5; Table[(k^Floor[(n+1)/2] + k^Ceiling[(n+1)/2]) / 2, {n, -1, 30}] (* Robert A. Russell, Sep 21 2018 *)

a(n)=if(n%2,3,1)*5^(n\2) \\ Charles R Greathouse IV, Oct 07 2015

def A056487(n): return 5**(n>>1)*(3 if n&1 else 1) # Chai Wah Wu, Oct 27 2022

a(n+2) = 5*a(n), a(0)=1, a(2)=3.
Binomial transform of A087205. Binomial transform is A087206. - Paul Barry, Aug 25 2003
G.f.: (1+3*x)/(1-5*x^2); a(n) = 5^(n/2)(1/2 + 3*sqrt(5)/10 + (1/2 - 3*sqrt(5)/10)(-1)^n). - Paul Barry, Mar 19 2004
2nd inverse binomial transform of Fibonacci(3n+2). - Paul Barry, Apr 16 2004
a(n+3) = a(n+2)*a(n+1)/a(n). - Reinhard Zumkeller, Mar 04 2011
a(n) = 3^((1 - (-1)^n)/2) * 5^((2*n + (-1)^n-1)/4). - Bruno Berselli, Mar 24 2011
a(n+1) = (k^floor((n+1)/2) + k^ceiling((n+1)/2)) / 2, where k=5 is the number of possible colors. - Robert A. Russell, Sep 22 2018
E.g.f.: cosh(sqrt(5)*x) + 3*sinh(sqrt(5)*x)/sqrt(5). - Stefano Spezia, Jun 06 2023

Changed one 'even' to 'odd' in the definition. - R. J. Mathar, Oct 06 2010

A063782 a(0) = 1, a(1) = 3; for n > 1, a(n) = 2a(n-1) + 4a(n-2).

Original entry on oeis.org

1, 3, 10, 32, 104, 336, 1088, 3520, 11392, 36864, 119296, 386048, 1249280, 4042752, 13082624, 42336256, 137003008, 443351040, 1434714112, 4642832384, 15024521216, 48620371968, 157338828800, 509159145472, 1647673606144

Offset: 0

Klaus E. Kastberg (kastberg(AT)hotkey.net.au), Aug 17 2001

Ratio of successive terms approaches sqrt(5) + 1.
From Sean A. Irvine, Jun 06 2025: (Start)
Also, number of walks of length n starting at vertex 1 in the following graph:
  1---2
  |\ /|
  | 0 |
  |/ \|
  4---3. (End)

			As the INVERT transform of A006138, (1, 2, 5, 11, 26, 59, ...); a(4) = 104 = (26, 11, 5, 2, 1) dot (1, 1, 3, 10, 32) = (26 + 11 + 15 + 20 + 32).

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..200 from Harry J. Smith)
Sean A. Irvine, Walks on Graphs.
Index entries for linear recurrences with constant coefficients, signature (2,4).

Cf. A006138. Row sums of A215244.

Cf. A000045, A049310, A087206, A319053.

a := proc(n) option remember: if n=0 then RETURN(1) fi: if n=1 then RETURN(2) fi: 2*a(n-1) + 4*a(n-2); end: for n from 1 to 50 do printf(`%d,`,a(n)+a(n-1)) od:
f:=n-> simplify(expand((1/2)*(1+sqrt(5))^n + (1/5)*(1+sqrt(5))^n*sqrt(5) - (1/5)*sqrt(5)*(1-sqrt(5))^n + (1/2)*(1 -sqrt(5))^n )); # N. J. A. Sloane, Aug 10 2012

a[n_]:=(MatrixPower[{{1,5},{1,1}},n].{{2},{1}})[[2,1]]; Table[a[n],{n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2010 *)
LinearRecurrence[{2, 4}, {1, 3}, 100] (* G. C. Greubel, Feb 18 2017 *)

{ for (n=0, 200, if (n>1, a=2*a1 + 4*a2; a2=a1; a1=a, if (n, a=a1=2, a=a2=1)); if (n, write("b063782.txt", n, " ", a + a2)) ) } \\ Harry J. Smith, Aug 31 2009

For n >= 1, a(n) = 2^(n-1)*Fibonacci(n+3). - Vladeta Jovovic, Oct 25 2003
G.f.: (1 + x)/(1 - 2*x - 4*x^2). - R. J. Mathar, Feb 06 2010
Equals INVERT transform of A006138 and INVERTi transform of A179606. - Gary W. Adamson, Aug 14 2010
a(n) = (1/2)*(1+sqrt(5))^n + (1/5)*(1+sqrt(5))^n*sqrt(5) - (1/5)*sqrt(5)*(1-sqrt(5))^n + (1/2)*(1-sqrt(5))^n. - Alexander R. Povolotsky, Aug 15 2010
It follows that a(n) is the nearest integer to (and is increasingly close to) (1/2 + 1/sqrt(5))*(1+sqrt(5))^n. - N. J. A. Sloane, Aug 10 2012
a(n) = A063727(n) + A063727(n-1).
a(n) = M^n(1, 1), with the matrix M= [[3, 1], [1, -1]]. Proof by Cayley-Hamilton, using S(n, -I) = (-I)^n*F(n+1), and S = A049310 and F = A000045. Motivated by A319053. - Wolfdieter Lang, Oct 08 2018

More terms from James Sellers, Sep 25 2001

Edited (new offset, new initial term, etc.) by N. J. A. Sloane, Aug 19 2010

A239194 T(n,k)=Number of nXk 0..4 arrays with no element equal to the sum of elements to its left or the sum of the elements above it, modulo 5.

Original entry on oeis.org

4, 12, 12, 40, 120, 40, 128, 1276, 1276, 128, 416, 13128, 43648, 13128, 416, 1344, 136684, 1436268, 1436268, 136684, 1344, 4352, 1416192, 47885992, 151351888, 47885992, 1416192, 4352, 14080, 14700364, 1588084496, 16147220164, 16147220164

Offset: 1

R. H. Hardin, Mar 11 2014

Table starts
.....4.........12.............40.................128.....................416
....12........120...........1276...............13128..................136684
....40.......1276..........43648.............1436268................47885992
...128......13128........1436268...........151351888.............16147220164
...416.....136684.......47885992.........16147220164...........5513429365240
..1344....1416192.....1588084496.......1713928533440........1872818978720764
..4352...14700364....52771184780.....182266933113924......637384123700005952
.14080..152485288..1752250223616...19369216287602148...216766214761274933980
.45568.1582134540.58199143332448.2058887399348279616.73739429314877219107168

			Some solutions for n=3 k=4
..1..2..4..3....1..2..2..1....1..2..2..3....1..2..1..1....1..2..2..3
..3..1..3..4....4..1..4..2....2..4..3..2....2..0..0..4....3..1..0..2
..2..4..3..3....2..4..0..0....2..0..3..3....1..3..3..1....2..4..4..3

R. H. Hardin, Table of n, a(n) for n = 1..144

Column 1 is A087206

Empirical for column k:
k=1: a(n) = 2*a(n-1) +4*a(n-2)
k=2: [order 7]
k=3: [order 32]

A006483 a(n) = Fibonacci(n)*2^n + 1.

Original entry on oeis.org

1, 3, 5, 17, 49, 161, 513, 1665, 5377, 17409, 56321, 182273, 589825, 1908737, 6176769, 19988481, 64684033, 209321985, 677380097, 2192048129, 7093616641, 22955425793, 74285318145, 240392339457, 777925951489, 2517421260801, 8146546327553, 26362777698305

Offset: 0

Dennis S. Kluk (mathemagician(AT)ameritech.net)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. S. Kluk and N. J. A. Sloane, Correspondence, 1979.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (3,2,-4).

Cf. A000045, A063727, A087206.

Equals A103435 + 1.

[Fibonacci(n)*2^n + 1: n in [0..50]]; // Vincenzo Librandi, Jun 09 2013

A006483:=-(-1+6*z**2)/(z-1)/(4*z**2+2*z-1); # Simon Plouffe in his 1992 dissertation

lst={};Do[AppendTo[lst, Fibonacci[n]*2^n+1], {n, 0, 5!}];lst (* Vladimir Joseph Stephan Orlovsky, Sep 19 2008 *)
CoefficientList[Series[(-(- 1 + 6 x^2)) / ((1 - x) (1 - 2 x - 4 x^2)), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 09 2013 *)
LinearRecurrence[{3,2,-4},{1,3,5},40] (* Harvey P. Dale, Aug 01 2021 *)

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

G.f. in Formula field corrected by Vincenzo Librandi, Jun 09 2013

A253064 Number of odd terms in f^n, where f = 1/x + 1 + x + y.

Original entry on oeis.org

1, 4, 4, 12, 4, 16, 12, 40, 4, 16, 16, 48, 12, 48, 40, 128, 4, 16, 16, 48, 16, 64, 48, 160, 12, 48, 48, 144, 40, 160, 128, 416, 4, 16, 16, 48, 16, 64, 48, 160, 16, 64, 64, 192, 48, 192, 160, 512, 12, 48, 48, 144, 48, 192, 144, 480, 40, 160, 160, 480, 128, 512, 416

Offset: 0

N. J. A. Sloane, Jan 26 2015

nonn

This is the number of ON cells in a certain 2-D CA in which the neighborhood of a cell is defined by f, and in which a cell is ON iff there was an odd number of ON cells in the neighborhood at the previous generation.

This is the odd-rule cellular automaton defined by OddRule 017 (see Ekhad-Sloane-Zeilberger "Odd-Rule Cellular Automata on the Square Grid" link). - N. J. A. Sloane, Feb 25 2015

			Here is the neighborhood f:
[0, X, 0]
[X, X, X]
which contains a(1) = 4 ON cells.

Alois P. Heinz, Table of n, a(n) for n = 0..8191
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, 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, 2015.
Po-Yi Huang and Wen-Fong Ke, Sequences Derived from The Symmetric Powers of {1,2,...,k}, arXiv:2307.07733 [math.CO], 2023.
N. J. A. Sloane, On the No. of ON Cells in Cellular Automata, Video of talk in Doron Zeilberger's Experimental Math Seminar at Rutgers University, Feb. 05 2015: Part 1, Part 2
N. J. A. Sloane, On the Number of ON Cells in Cellular Automata, arXiv:1503.01168, 2015
Index entries for sequences related to cellular automata

Other CA's that use the same rule but with different cell neighborhoods: A160239, A102376, A071053, A072272, A001316, A246034, A246035.

Cf. A087206.

C:=f->subs({x=1, y=1}, f);
# Find number of ON cells in CA for generations 0 thru M defined by rule
# that cell is ON iff number of ON cells in nbd at time n-1 was odd
# where nbd is defined by a polynomial or Laurent series f(x, y).
OddCA:=proc(f, M) global C; local n, a, i, f2, p;
f2:=simplify(expand(f)) mod 2;
a:=[]; p:=1;
for n from 0 to M do a:=[op(a), C(p)]; p:=expand(p*f2) mod 2; od:
lprint([seq(a[i], i=1..nops(a))]);
end;
f:=1/x+1+x+y;
OddCA(f, 130);

f[n_] := 2^n*Fibonacci[n+2]; Table[Times @@ (f[Length[#]]&) /@ Select[ Split[ IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 62}] (* Jean-François Alcover, Jul 11 2017 *)

This is the Run Length Transform of A087206.

A152174 a(n) = -2a(n-1)+4a(n-2), n>1 ; a(0) = 1, a(1) = -4.

Original entry on oeis.org

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

Offset: 0

Philippe Deléham, Nov 27 2008

Signed version of A087206.

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

Cf. A087206, A147703.

LinearRecurrence[{-2,4},{1,-4},30] (* Harvey P. Dale, Feb 13 2023 *)

Vec((1-2*x)/(1+2*x-4*x^2)+O(x^99)) \\ Charles R Greathouse IV, Jan 11 2012

G.f.: (1-2x)/(1+2x-4x^2).
a(n) = Sum_{k=0..n} A147703(n,k)*(-5)^k.
a(n) = (-1)^n * A087206(n).

A081057 E.g.f.: Sum_{n>=0} a(n)x^n/n! = {Sum_{n>=0} F(n+1)x^n/n!}^2, where F(n) is the n-th Fibonacci number.

Original entry on oeis.org

1, 2, 6, 18, 58, 186, 602, 1946, 6298, 20378, 65946, 213402, 690586, 2234778, 7231898, 23402906, 75733402, 245078426, 793090458, 2566494618, 8305351066, 26876680602, 86974765466, 281456253338, 910811568538, 2947448150426, 9538142575002, 30866077751706

Offset: 0

Paul D. Hanna, Mar 03 2003

nonn

a(n) ~ c*(sqrt(5)+1)^n, where c = (sqrt(5)+3)/10.
The inverse binomial transform is 1,1,3,5,... (1 followed by A056487). Partial sum of 1,1,4,12,..., i.e., 1 plus n-th partial sum of A087206. [R. J. Mathar, Oct 04 2010]
From R. J. Mathar, Oct 12 2010: (Start)
Apparently the row n=4 of an array which counts walks with k steps on an n X n board, starting at a corner, each step to one of the <= 4 adjacent squares:
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,
1,2,6,16,48,128,384,1024,3072,8192,24576,65536,196608,
1,2,6,18,58,186,602,1946,6298,20378,65946,213402,690586,
1,2,6,18,60,198,684,2322,8100,27702,96876,331938,1161540,
1,2,6,18,60,200,698,2432,8658,30762,110374,395428,1422916,
1,2,6,18,60,200,700,2448,8800,31552,115104,418176,1537536,
1,2,6,18,60,200,700,2450,8818,31730,116182,425172,1573416,
1,2,6,18,60,200,700,2450,8820,31750,116400,426600,1583400,
1,2,6,18,60,200,700,2450,8820,31752,116422,426862,1585246,
1,2,6,18,60,200,700,2450,8820,31752,116424,426886,1585556,
1,2,6,18,60,200,700,2450,8820,31752,116424,426888,1585582,
(End)
Decomposing rook walks of length=n on a 4 X 4 board into combinations of independent vertical and horizontal walks in 4-wide corridors leads to an exponential convolution of the Fibonacci numbers, cf. A052899. [David Scambler, Oct 17 2010]

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

a(n) = A052899(n-1) + A052899(n). a(n) - 2*a(n-1) = A014334(n).
Cf. A000032, A000045, A000204.
Row sums of A109906.

G.f.: (1-x-2x^2)/(1-3x-2x^2+4x^3). - Michael Somos, Mar 04 2003
a(n) - 2*a(n-1) = A014334(n), n > 0. - Vladeta Jovovic, Mar 05 2003
From Vladeta Jovovic, Mar 05 2003: (Start)
a(n) = 2/5 + (3/10 - 1/10*5^(1/2))*(1 - 5^(1/2))^n + (3/10 + 1/10*5^(1/2))*(1 + 5^(1/2))^n.
Recurrence: a(n) = 3*a(n-1) + 2*a(n-2) - 4*a(n-3).
G.f.: (1+x)*(1-2*x)/(1-2*x-4*x^2)/(1-x). (End)
a(n) = Sum_{k=0..n} ( F(k+1) * F(n-k+1) * C(n,k) ), where F(k) = Fibonacci(k). - David Scambler, Oct 17 2010
a(n) = (2^n*Lucas(n+2)+2)/5. - Ira M. Gessel, Mar 06 2022

Corrected and extended by Vladeta Jovovic and Michael Somos, Mar 05 2003

A231728 Triangular array read by rows: row n shows the coefficients of the polynomial u(n) = c(0) + c(1)x + ... + c(2n)x^(2n) which is the numerator of the n-th convergent of the continued fraction [k, k, k, ... ], where k = (x^2 + 1)/(x + 1).

Original entry on oeis.org

1, 0, 1, 2, 2, 3, 0, 1, 3, 4, 7, 4, 5, 0, 1, 5, 10, 19, 16, 16, 6, 7, 0, 1, 8, 20, 42, 48, 55, 36, 29, 8, 9, 0, 1, 13, 40, 94, 132, 164, 138, 119, 64, 46, 10, 11, 0, 1, 21, 76, 197, 324, 451, 464, 439, 304, 219, 100, 67, 12, 13, 0, 1, 34, 142, 405, 760, 1170

Offset: 1

Clark Kimberling, Nov 13 2013

Sum of numbers in row n: 2*A087206(n). Left edge: A000045 (Fibonacci numbers).

			First 3 rows:
1 . . . 0 . . . 1
2 . . . 2 . . . 3 . . . 0 . . . 1
3 . . . 4 . . . 7 . . . 4 . . . 5 . . . 0 . . . 1
First 3 polynomials:  1 + x^2, 2 + 2*x + 3*x^2 + x^4.

Cf. A230000, A000045, A231729.

t[n_] := t[n] = Table[(1 + x^2)/(1 + x), {k, 0, n}];
b = Table[Factor[Convergents[t[n]]], {n, 0, 10}];
p[x_, n_] := p[x, n] = Last[Expand[Numerator[b]]][[n]];
u = Table[p[x, n], {n, 1, 10}]
v = CoefficientList[u, x]; Flatten[v]

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions

A071053 Number of ON cells at n-th generation of 1-D CA defined by Rule 150, starting with a single ON cell at generation 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A056487 a(n) = 5^(n/2) for n even, a(n) = 3*5^((n-1)/2) for n odd.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A063782 a(0) = 1, a(1) = 3; for n > 1, a(n) = 2*a(n-1) + 4*a(n-2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A239194 T(n,k)=Number of nXk 0..4 arrays with no element equal to the sum of elements to its left or the sum of the elements above it, modulo 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A006483 a(n) = Fibonacci(n)*2^n + 1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

A063727 a(n) = 2a(n-1) + 4a(n-2), a(0)=1, a(1)=2.

A063782 a(0) = 1, a(1) = 3; for n > 1, a(n) = 2a(n-1) + 4a(n-2).

A152174 a(n) = -2a(n-1)+4a(n-2), n>1 ; a(0) = 1, a(1) = -4.

A081057 E.g.f.: Sum_{n>=0} a(n)x^n/n! = {Sum_{n>=0} F(n+1)x^n/n!}^2, where F(n) is the n-th Fibonacci number.

A231728 Triangular array read by rows: row n shows the coefficients of the polynomial u(n) = c(0) + c(1)x + ... + c(2n)x^(2n) which is the numerator of the n-th convergent of the continued fraction [k, k, k, ... ], where k = (x^2 + 1)/(x + 1).