A047849 -id:A047849 - cp's OEIS frontend

A002450 a(n) = (4^n - 1)/3.

0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 22906492245, 91625968981, 366503875925, 1466015503701, 5864062014805, 23456248059221, 93824992236885, 375299968947541

Offset: 0

N. J. A. Sloane

For n > 0, a(n) is the degree (n-1) "numbral" power of 5 (see A048888 for the definition of numbral arithmetic). Example: a(3) = 21, since the numbral square of 5 is 5(*)5 = 101(*)101(base 2) = 101 OR 10100 = 10101(base 2) = 21, where the OR is taken bitwise. - John W. Layman, Dec 18 2001
a(n) is composite for all n > 2 and has factors x, (3*x + 2*(-1)^n) where x belongs to A001045. In binary the terms greater than 0 are 1, 101, 10101, 1010101, etc. - John McNamara, Jan 16 2002
Number of n X 2 binary arrays with path of adjacent 1's from upper left corner to right column. - R. H. Hardin, Mar 16 2002
The Collatz-function iteration started at a(n), for n >= 1, will end at 1 after 2*n+1 steps. - Labos Elemer, Sep 30 2002 [corrected by Wolfdieter Lang, Aug 16 2021]
Second binomial transform of A001045. - Paul Barry, Mar 28 2003
All members of sequence are also generalized octagonal numbers (A001082). - Matthew Vandermast, Apr 10 2003
Also sum of squares of divisors of 2^(n-1): a(n) = A001157(A000079(n-1)), for n > 0. - Paul Barry, Apr 11 2003
Binomial transform of A000244 (with leading zero). - Paul Barry, Apr 11 2003
Number of walks of length 2n between two vertices at distance 2 in the cycle graph C_6. For n = 2 we have for example 5 walks of length 4 from vertex A to C: ABABC, ABCBC, ABCDC, AFABC and AFEDC. - Herbert Kociemba, May 31 2004
Also number of walks of length 2n + 1 between two vertices at distance 3 in the cycle graph C_12. - Herbert Kociemba, Jul 05 2004
a(n+1) is the number of steps that are made when generating all n-step random walks that begin in a given point P on a two-dimensional square lattice. To make one step means to mark one vertex on the lattice (compare A080674). - Pawel P. Mazur (Pawel.Mazur(AT)pwr.wroc.pl), Mar 13 2005
a(n+1) is the sum of square divisors of 4^n. - Paul Barry, Oct 13 2005
a(n+1) is the decimal number generated by the binary bits in the n-th generation of the Rule 250 elementary cellular automaton. - Eric W. Weisstein, Apr 08 2006
a(k) = [M^k]2,1, where M is the 3 X 3 matrix defined as follows: M = [1, 1, 1; 1, 3, 1; 1, 1, 1]. - _Simone Severini, Jun 11 2006
a(n-1) / a(n) = percentage of wasted storage if a single image is stored as a pyramid with a each subsequent higher resolution layer containing four times as many pixels as the previous layer. n is the number of layers. - Victor Brodsky (victorbrodsky(AT)gmail.com), Jun 15 2006
k is in the sequence if and only if C(4k + 1, k) (A052203) is odd. - Paul Barry, Mar 26 2007
This sequence also gives the number of distinct 3-colorings of the odd cycle C(2*n - 1). - Keith Briggs, Jun 19 2007
All numbers of the form m*4^m + (4^m-1)/3 have the property that they are sums of two squares and also their indices are the sum of two squares. This follows from the identity m*4^m + (4^m-1)/3 = 4(4(..4(4m + 1) + 1) + 1) + 1 ..) + 1. - Artur Jasinski, Nov 12 2007
For n > 0, terms are the numbers that, in base 4, are repunits: 1_4, 11_4, 111_4, 1111_4, etc. - Artur Jasinski, Sep 30 2008
Let A be the Hessenberg matrix of order n, defined by: A[1, j] = 1, A[i, i] := 5, (i > 1), A[i, i - 1] = -1, and A[i, j] = 0 otherwise. Then, for n >= 1, a(n) = charpoly(A,1). - Milan Janjic, Jan 27 2010
This is the sequence A(0, 1; 3, 4; 2) = A(0, 1; 4, 0; 1) of the family of sequences [a, b : c, d : k] considered by G. Detlefs, and treated as A(a, b; c, d; k) in the W. Lang link given below. - Wolfdieter Lang, Oct 18 2010
6*a(n) + 1 is every second Mersenne number greater than or equal to M3, hence all Mersenne primes greater than M2 must be a 6*a(n) + 1 of this sequence. - Roderick MacPhee, Nov 01 2010
Smallest number having alternating bit sum n. Cf. A065359.
For n = 1, 2, ..., the last digit of a(n) is 1, 5, 1, 5, ... . - Washington Bomfim, Jan 21 2011
Rule 50 elementary cellular automaton generates this sequence. This sequence also appears in the second column of array in A173588. - Paul Muljadi, Jan 27 2011
Sequence found by reading the line from 0, in the direction 0, 5, ... and the line from 1, in the direction 1, 21, ..., in the square spiral whose edges are the Jacobsthal numbers A001045 and whose vertices are the numbers A000975. These parallel lines are two semi-diagonals in the spiral. - Omar E. Pol, Sep 10 2011
a(n), n >= 1, is also the inverse of 3, denoted by 3^(-1), Modd(2^(2*n - 1)). For Modd n see a comment on A203571. E.g., a(2) = 5, 3 * 5 = 15 == 1 (Modd 8), because floor(15/8) = 1 is odd and -15 == 1 (mod 8). For n = 1 note that 3 * 1 = 3 == 1 (Modd 2) because floor(3/2) = 1 and -3 == 1 (mod 2). The inverse of 3 taken Modd 2^(2*n) coincides with 3^(-1) (mod 2^(2*n)) given in A007583(n), n >= 1. - Wolfdieter Lang, Mar 12 2012
If an AVL tree has a leaf at depth n, then the tree can contain no more than a(n+1) nodes total. - Mike Rosulek, Nov 20 2012
Also, this is the Lucas sequence V(5, 4). - Bruno Berselli, Jan 10 2013
Also, for n > 0, a(n) is an odd number whose Collatz trajectory contains no odd number other than n and 1. - Jayanta Basu, Mar 24 2013
Sum_{n >= 1} 1/a(n) converges to (3*(log(4/3) - QPolyGamma[0, 1, 1/4]))/log(4) = 1.263293058100271... = A321873. - K. G. Stier, Jun 23 2014
Consider n spheres in R^n: the i-th one (i=1, ..., n) has radius r(i) = 2^(1-i) and the coordinates of its center are (0, 0, ..., 0, r(i), 0, ..., 0) where r(i) is in position i. The coordinates of the intersection point in the positive orthant of these spheres are (2/a(n), 4/a(n), 8/a(n), 16/a(n), ...). For example in R^2, circles centered at (1, 0) and (0, 1/2), and with radii 1 and 1/2, meet at (2/5, 4/5). - Jean M. Morales, May 19 2015
From Peter Bala, Oct 11 2015: (Start)
a(n) gives the values of m such that binomial(4*m + 1,m) is odd. Cf. A003714, A048716, A263132.
2*a(n) = A020988(n) gives the values of m such that binomial(4*m + 2, m) is odd.
4*a(n) = A080674(n) gives the values of m such that binomial(4*m + 4, m) is odd. (End)
Collatz Conjecture Corollary: Except for powers of 2, the Collatz iteration of any positive integer must eventually reach a(n) and hence terminate at 1. - Gregory L. Simay, May 09 2016
Number of active (ON, black) cells at stage 2^n - 1 of the two-dimensional cellular automaton defined by "Rule 598", based on the 5-celled von Neumann neighborhood. - Robert Price, May 16 2016
From Luca Mariot and Enrico Formenti, Sep 26 2016: (Start)
a(n) is also the number of coprime pairs of polynomials (f, g) over GF(2) where both f and g have degree n + 1 and nonzero constant term.
a(n) is also the number of pairs of one-dimensional binary cellular automata with linear and bipermutive local rule of neighborhood size n+1 giving rise to orthogonal Latin squares of order 2^m, where m is a multiple of n. (End)
Except for 0, 1 and 5, all terms are Brazilian repunits numbers in base 4, and so belong to A125134. For n >= 3, all these terms are composite because a(n) = {(2^n-1) * (2^n + 1)}/3 and either (2^n - 1) or (2^n + 1) is a multiple of 3. - Bernard Schott, Apr 29 2017
Given the 3 X 3 matrix A = [2, 1, 1; 1, 2, 1; 1, 1, 2] and the 3 X 3 unit matrix I_3, A^n = a(n)(A - I_3) + I_3. - Nicolas Patrois, Jul 05 2017
The binary expansion of a(n) (n >= 1) consists of n 1's alternating with n - 1 0's. Example: a(4) = 85 = 1010101_2. - Emeric Deutsch, Aug 30 2017
a(n) (n >= 1) is the viabin number of the integer partition [n, n - 1, n - 2, ..., 2, 1] (for the definition of viabin number see comment in A290253). Example: a(4) = 85 = 1010101_2; consequently, the southeast border of the Ferrers board of the corresponding integer partition is ENENENEN, where E = (1, 0), N = (0, 1); this leads to the integer partition [4, 3, 2, 1]. - Emeric Deutsch, Aug 30 2017
Numbers whose binary and Gray-code representations are both palindromes (i.e., intersection of A006995 and A281379). - Amiram Eldar, May 17 2021
Starting with n = 1 the sequence satisfies {a(n) mod 6} = repeat{1, 5, 3}. - Wolfdieter Lang, Jan 14 2022
Terms >= 5 are those q for which the multiplicative order of 2 mod q is floor(log_2(q)) + 2 (and which is 1 more than the smallest possible order for any q). - Tim Seuré, Mar 09 2024
The order of 2 modulo a(n) is 2*n for n >= 2. - Joerg Arndt, Mar 09 2024

			Apply Collatz iteration to 9: 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5 and hence 16, 8, 4, 2, 1.
Apply Collatz iteration to 27: 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5 and hence 16, 8, 4, 2, 1. [Corrected by _Sean A. Irvine_ at the suggestion of Stephen Cornelius, Mar 04 2024]
a(5) = (4^5 - 1)/3 = 341 = 11111_4 = {(2^5 - 1) * (2^5 + 1)}/3 = 31 * 33/3 = 31 * 11. - _Bernard Schott_, Apr 29 2017

A. Fletcher, J. C. P. Miller, L. Rosenhead and L. J. Comrie, An Index of Mathematical Tables. Vols. 1 and 2, 2nd ed., Blackwell, Oxford and Addison-Wesley, Reading, MA, 1962, Vol. 1, p. 112.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 217.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..200
Peter Bala, A characterization of A002450, A020988 and A080674.
Henry Bottomley, Illustration of initial terms
Sung-Hyuk Cha, On Complete and Size Balanced k-ary Tree Integer Sequences, International Journal of Applied Mathematics and Informatics, Issue 2, Volume 6, 2012, pp. 67-75. - From _N. J. A. Sloane_, Dec 24 2012
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 8.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J., 41 (1974), 305-318. (Annotated scanned copy)
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
C. Ernst and D. W. Sumners, The Growth of the Number of Prime Knots, Math. Proc. Cambridge Philos. Soc. 102, 303-315, 1987
Ernesto Estrada and José A. de la Peña, Integer sequences from walks in graphs, Notes on Number Theory and Discrete Mathematics, Vol. 19, 2013, No. 3, 78-84.
Rigoberto Flórez, Robinson A. Higuita, and Antara Mukherjee, Alternating Sums in the Hosoya Polynomial Triangle, Article 14.9.5 Journal of Integer Sequences, Vol. 17 (2014).
Enrico Formenti and Luca Mariot, Exhaustive Generation of Linear Orthogonal CA, Automata 2023, Univ. Twente (Netherlands), see p. 22 of 38.
Mattia Fregola, Elementary Cellular Automata Rule 1 generating OEIS sequence A277799, A058896, A141725, A002450
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 373
Petro Kosobutskyy and Nataliia Nestor, On the mathematical model of the transformation of natural numbers by a function of a split type, Comp. Des. Sys. Theor. Practice (2024) Vol. 6, No. 2. See p. 7.
Petro Kosobutskyy, Anastasiia Yedyharova, and Taras Slobodzyan, From Newton's binomial and Pascal's triangle to Collatz's problem, Comp. Des. Sys., Theor. Practice (2023) Vol. 5, No. 1, 121-127.
Wolfdieter Lang, Notes on certain inhomogeneous three term recurrences.
J. V. Leyendekkers and A.G. Shannon, Modular Rings and the Integer 3, Notes on Number Theory & Discrete Mathematics, 17 (2011), 47-51.
Luca Manzoni, Luca Mariot, and Giuliamaria Menara, Combinatorial Designs and Cellular Automata: A Survey, arXiv:2503.10320 [math.CO], 2025. See pp. 16, 27.
Luca Mariot, Cryptography by Cellular Automata, 2017.
Luca Mariot, Orthogonal labelings in de Bruijn graphs, IWOCA 2020 - Open Problems Session, Delft University of Technology (Netherlands).
Luca Mariot, Connections between Latin squares, Cellular Automata and Coprime Polynomials, Univ. Twente (Netherlands, 2023). See p. 16/37.
Luca Mariot and Enrico Formenti, The number of coprime/non-coprime pairs of polynomials over F_2 with degree n and nonzero constant term.
Luca Mariot, Enrico Formenti and Alberto Leporati, Constructing Orthogonal Latin Squares from Linear Cellular Automata. In: Exploratory papers of AUTOMATA 2016.
Luca Mariot, Maximilien Gadouleau, Enrico Formenti, and Alberto Leporati, Mutually Orthogonal Latin Squares based on Cellular Automata, arXiv:1906.08249 [cs.DM], 2019.
Luca Mariot, Counting Coprime Polynomials over Finite Fields with Formal Languages and Compositions of Natural Numbers, Univ. Twente (Netherlands 2023). See p. 11.
Mircea Merca, A Note on Cosine Power Sums J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
Mező István, Several Generating Functions for Second-Order Recurrence Sequences , JIS 12 (2009) 09.3.7.
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.
Kalika Prasad, Munesh Kumari, Rabiranjan Mohanta, and Hrishikesh Mahato, The sequence of higher order Mersenne numbers and associated binomial transforms, arXiv:2307.08073 [math.NT], 2023.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See p. 4.
A. G. Shannon, Some recurrence relations for binary sequence matrices, NNTDM 17 (2011), 4, 913. - From _N. J. A. Sloane_, Jun 13 2012
T. N. Thiele, Interpolationsrechnung, Teubner, Leipzig, 1909, p. 35.
Eric Weisstein's World of Mathematics, Repunit, Rule 250, Prime Knot.
Wikipedia, Elementary cellular automaton
Wikipedia, Lucas sequence: Specific names.
Michael Williams, Collatz conjecture: an order isomorphic recursive machine, ResearchGate (2024). See pp. 8, 13.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Partial sums of powers of 4, A000302.
When converted to binary, this gives A094028.
Subsequence of A003714.
Primitive factors: A129735.
Cf. A000225, A002446, A006995, A007583, A018215, A020988, A024036, A047849, A048716, A080355, A080674, A112627, A113860, A139391, A155701, A156605, A160967, A163834, A163868, A178415, A263132, A281379, A347834.

List([0..25], n -> (4^n-1)/3); # Muniru A Asiru, Feb 18 2018

a002450 = (`div` 3) . a024036
a002450_list = iterate ((+ 1) . (* 4)) 0
-- Reinhard Zumkeller, Oct 03 2012

[ (4^n-1)/3: n in [0..25] ]; // Klaus Brockhaus, Oct 28 2008

[n le 2 select n-1 else 5*Self(n-1)-4*Self(n-2): n in [1..70]]; // Vincenzo Librandi, Jun 13 2015

[seq((4^n-1)/3,n=0..40)];
A002450:=1/(4*z-1)/(z-1); # Simon Plouffe in his 1992 dissertation, dropping the initial zero

Table[(4^n - 1)/3, {n, 0, 127}] (* Vladimir Joseph Stephan Orlovsky, Sep 29 2008 *)
LinearRecurrence[{5, -4}, {0, 1}, 30] (* Harvey P. Dale, Jun 23 2013 *)

makelist((4^n-1)/3, n, 0, 30); /* Martin Ettl, Nov 05 2012 */

PARI
```
a(n) = (4^n-1)/3;
```

my(z='z+O('z^40)); Vec(z/((1-z)*(1-4*z))) \\ Altug Alkan, Oct 11 2015

def A002450(n): return ((1<<(n<<1))-1)//3 # Chai Wah Wu, Jan 29 2023

((List.fill(20)(4: BigInt)).scanLeft(1: BigInt)( * )).scanLeft(0: BigInt)( + ) // Alonso del Arte, Sep 17 2019

From Wolfdieter Lang, Apr 24 2001: (Start)
a(n+1) = Sum_{m = 0..n} A060921(n, m).
G.f.: x/((1-x)*(1-4*x)). (End)
a(n) = Sum_{k = 0..n-1} 4^k; a(n) = A001045(2*n). - Paul Barry, Mar 17 2003
E.g.f.: (exp(4*x) - exp(x))/3. - Paul Barry, Mar 28 2003
a(n) = (A007583(n) - 1)/2. - N. J. A. Sloane, May 16 2003
a(n) = A000975(2*n)/2. - N. J. A. Sloane, Sep 13 2003
a(n) = A084160(n)/2. - N. J. A. Sloane, Sep 13 2003
a(n+1) = 4*a(n) + 1, with a(0) = 0. - Philippe Deléham, Feb 25 2004
a(n) = Sum_{i = 0..n-1} C(2*n - 1 - i, i)*2^i. - Mario Catalani (mario.catalani(AT)unito.it), Jul 23 2004
a(n+1) = Sum_{k = 0..n} binomial(n+1, k+1)*3^k. - Paul Barry, Aug 20 2004
a(n) = center term in M^n * [1 0 0], where M is the 3 X 3 matrix [1 1 1 / 1 3 1 / 1 1 1]. M^n * [1 0 0] = [A007583(n-1) a(n) A007583(n-1)]. E.g., a(4) = 85 since M^4 * [1 0 0] = [43 85 43] = [A007583(3) a(4) A007583(3)]. - Gary W. Adamson, Dec 18 2004
a(n) = Sum_{k = 0..n, j = 0..n} C(n, j)*C(j, k)*A001045(j - k). - Paul Barry, Feb 15 2005
a(n) = Sum_{k = 0..n} C(n, k)*A001045(n-k)*2^k = Sum_{k = 0..n} C(n, k)*A001045(k)*2^(n-k). - Paul Barry, Apr 22 2005
a(n) = A125118(n, 3) for n > 2. - Reinhard Zumkeller, Nov 21 2006
a(n) = Sum_{k = 0..n} 2^(n - k)*A128908(n, k), n >= 1. - Philippe Deléham, Oct 19 2008
a(n) = Sum_{k = 0..n} A106566(n, k)*A100335(k). - Philippe Deléham, Oct 30 2008
If we define f(m, j, x) = Sum_{k = j..m} binomial(m, k)*stirling2(k, j)*x^(m - k) then a(n-1) = f(2*n, 4, -2), n >= 2. - Milan Janjic, Apr 26 2009
a(n) = A014551(n) * A001045(n). - R. J. Mathar, Jul 08 2009
a(n) = 4*a(n-1) + a(n-2) - 4*a(n-3) = 5*a(n-1) - 4*a(n-2), a(0) = 0, a(1) = 1, a(2) = 5. - Wolfdieter Lang, Oct 18 2010
a(0) = 0, a(n+1) = a(n) + 2^(2*n). - Washington Bomfim, Jan 21 2011
A036555(a(n)) = 2*n. - Reinhard Zumkeller, Jan 28 2011
a(n) = Sum_{k = 1..floor((n+2)/3)} C(2*n + 1, n + 2 - 3*k). - Mircea Merca, Jun 25 2011
a(n) = Sum_{i = 1..n} binomial(2*n + 1, 2*i)/3. - Wesley Ivan Hurt, Mar 14 2015
a(n+1) = 2^(2*n) + a(n), a(0) = 0. - Ben Paul Thurston, Dec 27 2015
a(k*n)/a(n) = 1 + 4^n + ... + 4^((k-1)*n). - Gregory L. Simay, Jun 09 2016
Dirichlet g.f.: (PolyLog(s, 4) - zeta(s))/3. - Ilya Gutkovskiy, Jun 26 2016
A000120(a(n)) = n. - André Dalwigk, Mar 26 2018
a(m) divides a(m*n), in particular: a(2*n) == 0 (mod 5), a(3*n) == 0 (mod 3*7), a(5*n) == 0 (mod 11*31), etc. - M. F. Hasler, Oct 19 2018
a(n) = 4^(n-1) + a(n-1). - Bob Selcoe, Jan 01 2020
a(n) = A178415(1, n) = A347834(1, n-1), arrays, for n >= 1.  - Wolfdieter Lang, Nov 29 2021
a(n) = A000225(2*n)/3. - John Keith, Jan 22 2022
a(n) = A080674(n) + 1 = A047849(n) - 1 = A163834(n) - 2 = A155701(n) - 3 = A163868(n) - 4 = A156605(n) - 7. - Ray Chandler, Jun 16 2023
From Peter Bala, Jul 23 2025: (Start)
The following are examples of telescoping products. Cf. A016153:
Product_{k = 1..2*n} 1 + 2^k/a(k+1) = a(n+1)/A007583(n) = (4^(n+1) - 1)/(2*4^n + 1).
Hence, Product_{k >= 1} 1 + 2^k/a(k+1) = 2.
Product_{k >= 1} 1 - 2^k/a(k+1) = 2/5, since 1 - 2^n/a(n+1) = b(n)/b(n-1), where b(n) = 2 - 3/(1 - 2^(n+1)).
Product_{k >= 1} 1 + (-2)^k/a(k+1) = 2/3, since 1 + (-2)^n/a(n+1) = c(n)/c(n-1), where c(n) = 2 - 1/(1 + (-2)^(n+1)).
Product_{k >= 1} 1 - (-2)^k/a(k+1) = 6/5, since 1 - (-2)^n/a(n+1) = d(n)/d(n-1), where d(n) = 2 - 1/(1 - (-2)^(n+1)). (End)

A078008 Expansion of (1 - x)/((1 + x)(1 - 2x)).

Original entry on oeis.org

1, 0, 2, 2, 6, 10, 22, 42, 86, 170, 342, 682, 1366, 2730, 5462, 10922, 21846, 43690, 87382, 174762, 349526, 699050, 1398102, 2796202, 5592406, 11184810, 22369622, 44739242, 89478486, 178956970, 357913942, 715827882, 1431655766, 2863311530, 5726623062

Offset: 0

N. J. A. Sloane, Nov 17 2002

Conjecture: a(n) = the number of fractions in the infinite Farey row of 2^n terms with even denominators. Compare the Salamin & Gosper item in the Beeler et al. link. - Gary W. Adamson, Oct 27 2003
Counts closed walks starting and ending at the same vertex of a triangle. 3*a(n) = P(C_n, 3) chromatic polynomial for 3 colors on cyclic graph C_n. A078008(n) + 2*A001045(n) = 2^n provides decomposition of Pascal's triangle. - Paul Barry, Nov 17 2003
Permutations with one fixed point avoiding 123 and 132.
General form: iterate k -> 2^n - k. See also A001045. - Vladimir Joseph Stephan Orlovsky, Dec 11 2008
The inverse g.f. generates sequence 1, 0, -2, -2, -2, -2, ...
a(n) gives the number of oriented (i.e., unreduced for symmetry) meanders on an (n+2) X 3 rectangular grid; see A201145. - Jon Wild, Nov 22 2011
Pisano period lengths: 1, 1, 6, 1, 4, 6, 6, 2, 18, 4, 10, 6, 12, 6, 12, 2, 8, 18, 18, 4, ... - R. J. Mathar, Aug 10 2012
a(n) is the number of length n binary words that end in an odd length run of 0's if we do not include the first letter of the word in our run length count. a(4) =6 because we have 0000, 0010, 0110, 1000, 1010, 1110. - Geoffrey Critzer, Dec 16 2013
a(n) is the top left entry of the n-th power of any of the six 3 X 3 matrices [0, 1, 1; 1, 1, 1; 1, 0, 0], [0, 1, 1; 1, 1, 0; 1, 1, 0], [0, 1, 1; 1, 0, 1; 1, 1, 0], [0, 1, 1; 1, 1, 0; 1, 0, 1], [0, 1, 1; 1, 0, 1; 1, 0, 1] or [0, 1, 1; 1, 0, 0; 1, 1, 1]. - R. J. Mathar, Feb 04 2014
a(n) is the number of compositions of n into parts of two kinds without part 1. - Gregory L. Simay, Jun 04 2018
a(n) is the number of words of length n over a binary alphabet whose position in the lexicographic order is a multiple of three.  a(3) = 2: aba, bab. - Alois P. Heinz, Apr 13 2022
a(n) is the number of words of length n over a ternary alphabet starting with a fixed letter (say, 'a') and ending in a different letter, such that no two adjacent letters are the same. a(4) = 6: abab, abac, abcb, acab, acac, acbc. - Ignat Soroko, Jul 19 2023

			G.f. = 1 + 2*x^2 + 2*x^3 + 6*x^4 + 10*x^5 + 22*x^6 + ... - _Michael Somos_, Mar 18 2022

Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, Part II, Fib. Q., 58:2 (2020), 169-177.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, ex. 1.1.10a.

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms n=0..300 from T. D. Noe)
David Applegate, Omar E. Pol and N. J. A. Sloane, The Toothpick Sequence and Other Sequences from Cellular Automata, Congressus Numerantium, Vol. 206 (2010), 157-191. [There is a typo in Theorem 6: (13) should read u(n) = 4.3^(wt(n-1)-1) for n >= 2.]
Roland Bacher, Chebyshev polynomials, quadratic surds and a variation of Pascal's triangle, arXiv:1509.09054 [math.CO], 2015. See Section 4.6.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry and A. Hennessy, Notes on a Family of Riordan Arrays and Associated Integer Hankel Transforms , JIS 12 (2009) 09.5.3.
M. Beeler, R. W. Gosper, and R. C. Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb 29 1972. (Item #54 by Salamin & Gosper)
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Kenneth Edwards and Michael A. Allen, A new combinatorial interpretation of the Fibonacci numbers squared, arXiv:1907.06517 [math.CO], 2019.
Ernesto Estevez-Rams, Cristy Azanza Ricardo and Beatriz Aragón Fernández, An alternative expression for counting the number of close-packaged polytypes, Z. Krist. 220 (2005) 592-595, eq (4)
Leonhard Euler, Introductio in analysin infinitorum, (1748), section 216.
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See p. 13.
T. Mansour and A. Robertson, Refined Restricted Permutations Avoiding Subsets of Patterns of Length Three, arXiv:math/0204005 [math.CO], 2002.
N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
Index entries for linear recurrences with constant coefficients, signature (1,2).
Index entries for sequences related to Chebyshev polynomials.

First differences of A001045.
See A151575 for a signed version.
Bisections: A047849, A020988.
Cf. A151548, A139250, A151555, A153006.

List([0..40], n-> (2^n + 2*(-1)^n)/3); # G. C. Greubel, Jun 28 2019

[(2^n + 2*(-1)^n)/3: n in [0..40]]; // G. C. Greubel, Jun 28 2019

Table[(2^n + 2*(-1)^n)/3, {n,0,40}] (* Vladimir Joseph Stephan Orlovsky, Dec 11 2008; modified by G. C. Greubel, Jun 28 2019 *)
CoefficientList[Series[(1-x)/(1-x-2x^2),{x,0,40}],x]  (* Harvey P. Dale, Mar 30 2011 *)
LinearRecurrence[{1, 2}, {1, 0}, 40] (* Jean-François Alcover, Sep 23 2017 *)

a(n)=(1<Charles R Greathouse IV, Jun 10 2011

def A078008(n): return ((1<Chai Wah Wu, Apr 18 2025

[(2^n + 2*(-1)^n)/3 for n in (0..40)] # G. C. Greubel, Jun 28 2019

Euler expands(1-x)/(1 - x - 2*x^2) into an infinite series and finds that the coefficient of the n-th term is (2^n + (-1)^n 2)/3. Section 226 shows that Euler could have easily found the recursion relation: a(n) = a(n-1) + 2a(n-2) with a(0) = 1 and a(1) = 0. - V. Frederick Rickey (fred-rickey(AT)usma.edu), Feb 10 2006. [Typos corrected by Jaume Oliver Lafont, Jun 01 2009]
a(n) = Sum_{k=0..floor(n/3)} binomial(n, f(n)+3*k) where f(n) = (0, 2, 1, 0, 2, 1, ...) = A080424(n). - Paul Barry, Feb 20 2003
E.g.f. (exp(2*x) + 2*exp(-x))/3. - Paul Barry, Apr 20 2003
a(n) = A001045(n) + (-1)^n = A000079(n) - 2*A001045(n). - Paul Barry, Feb 20 2003
a(n) = (2^n + 2*(-1)^n)/3. - Mario Catalani (mario.catalani(AT)unito.it), Aug 29 2003
a(n) = T(n, i/(2*sqrt(2)))*(-i*sqrt(2))^n - U(n-1, i/(2*sqrt(2)))*(-i*sqrt(2))^(n-1)/2. - Paul Barry, Nov 17 2003
From Paul Barry, Jul 30 2004: (Start)
a(n) = 2*a(n-1) + 2*(-1)^n for n > 0, with a(0)=1.
a(n) = Sum_{k=0..n} (-1)^k*(2^(n-k-1) + 0^(n-k)/2). (End)
a(n) = A014113(n-1) for n > 0; a(n) = A052953(n-1) - 2*(n mod 2) = sum of n-th row of the triangle in A108561. - Reinhard Zumkeller, Jun 10 2005
A137208(n+1) - 2*A137208(n) = a(n) signed. - Paul Curtz, Aug 03 2008
a(n) = A001045(n+1) - A001045(n) - Paul Curtz, Feb 09 2009
If p[1] =0, and p[i]=2, (i>1), and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=1, a(n)=det A. - Milan Janjic, Apr 29 2010
a(n) = 2*(a(n-2) + a(n-3) + a(n-4) ... + a(0)), that is, twice the sum of all the previous terms except the last; with a(0) = 1 and a(1) = 0. - Benoit Jubin, Nov 21 2011
a(n+1) = 2*A001045(n). - Benoit Jubin, Nov 22 2011
G.f.: 1 - x + x*Q(0), where Q(k) = 1 + 2*x^2 + (2*k+3)*x - x*(2*k+1 + 2*x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 05 2013
G.f.: 1+ x^2*Q(0), where Q(k) = 1 + 1/(1 - x*(4*k+1+2*x)/(x*(4*k+3+2*x) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 01 2014
a(n) = 3*a(n-2) + 2*a(n-3). - David Neil McGrath, Sep 10 2014
a(n) = (-1)^n * A151575(n). - G. C. Greubel, Jun 28 2019
a(n)+a(n+1) = 2^n. - R. J. Mathar, Feb 24 2021
a(n) = -a(2-n) * (-2)^(n-1) = (3/2)*(a(n-1) + a(n-2)) - a(n-3) for all n in Z. - Michael Somos, Mar 18 2022

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

Original entry on oeis.org

0, 2, 10, 42, 170, 682, 2730, 10922, 43690, 174762, 699050, 2796202, 11184810, 44739242, 178956970, 715827882, 2863311530, 11453246122, 45812984490, 183251937962, 733007751850, 2932031007402, 11728124029610, 46912496118442, 187649984473770, 750599937895082

Offset: 0

N. J. A. Sloane

Numbers whose binary representation is 10, n times (see A163662(n) for n >= 1). - Alexandre Wajnberg, May 31 2005
Numbers whose base-4 representation consists entirely of 2's; twice base-4 repunits. - Franklin T. Adams-Watters, Mar 29 2006
Expected time to finish a random Tower of Hanoi problem with 2n disks using optimal moves, so (since 2n is even and A010684(2n) = 1) a(n) = A060590(2n). - Henry Bottomley, Apr 05 2001
a(n) is the number of derangements of [2n + 3] with runs consisting of consecutive integers. E.g., a(1) = 10 because the derangements of {1, 2, 3, 4, 5} with runs consisting of consecutive integers are 5|1234, 45|123, 345|12, 2345|1, 5|4|123, 5|34|12, 45|23|1, 345|2|1, 5|4|23|1, 5|34|2|1 (the bars delimit the runs). - Emeric Deutsch, May 26 2003
For n > 0, also smallest numbers having in binary representation exactly n + 1 maximal groups of consecutive zeros: A087120(n) = a(n-1), see A087116. - Reinhard Zumkeller, Aug 14 2003
Number of walks of length 2n + 3 between any two diametrically opposite vertices of the cycle graph C_6. Example: a(0) = 2 because in the cycle ABCDEF we have two walks of length 3 between A and D: ABCD and AFED. - Emeric Deutsch, Apr 01 2004
From Paul Barry, May 18 2003: (Start)
Row sums of triangle using cumulative sums of odd-indexed rows of Pascal's triangle (start with zeros for completeness):
            0  0
            1  1
         1  4  4  1
      1  6 14 14  6  1
   1  8 27 49 49 27  8  1 (End)
a(n) gives the position of the n-th zero in A173732, i.e., A173732(a(n)) = 0 for all n and this gives all the zeros in A173732. - Howard A. Landman, Mar 14 2010
Smallest number having alternating bit sum -n. Cf. A065359. For n = 0, 1, ..., the last digit of a(n) is 0, 2, 0, 2, ... . - Washington Bomfim, Jan 22 2011
Number of toothpicks minus 1 in the toothpick structure of A139250 after 2^n stages. - Omar E. Pol, Mar 15 2012
For n > 0 also partial sums of the odd powers of 2 (A004171). - K. G. Stier, Nov 04 2013
Values of m such that binomial(4*m + 2, m) is odd. Cf. A002450. - Peter Bala, Oct 06 2015
For a(n) > 2, values of m such that m is two steps away from a power of 2 under the Collatz iteration. - Roderick MacPhee, Nov 10 2016
a(n) is the position of the first occurrence of 2^(n+1)-1 in A020986. See the Brillhart and Morton link, pp. 856-857. - John Keith, Jan 12 2021
a(n) is the number of monotone paths in the n-dimensional cross-polytope for a generic linear orientation. See the Black and De Loera link. - Alexander E. Black, Feb 15 2023

G. C. Greubel, Table of n, a(n) for n = 0..1000 (terms 0..170 from Vincenzo Librandi)
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, On extremal cases of pop-stack sorting, Permutation Patterns (Zürich, Switzerland, 2019) [link is not very stable].
Andrei Asinowski, Cyril Banderier, and Benjamin Hackl, Flip-sort and combinatorial aspects of pop-stack sorting, arXiv:2003.04912 [math.CO], 2020.
Peter Bala, A characterization of A002450, A020988 and A080674.
Alexander E. Black, Monotone Paths on Polytopes: Combinatorics and Optimization, Ph. D. Dissertation, Univ. Calif. Davis (2024). See p. 59.
Alexander Black and Jesús De Loera, Monotone paths on cross-polytopes, arXiv:2102.01237 [math.CO], Feb 2021
John Brillhart and Peter Morton, A case study in mathematical research: the Golay-Rudin-Shapiro sequence, Amer. Math. Monthly, 103 (1996) 854-869.
Nobushige Kurokawa, Zeta functions over F_1, Proc. Japan Acad., 81, Ser. A (2005), 180-184. See Theorem 3 (3).
Jonathan L. Merzel, Ján Minač, Tung T. Nguyen, and Nguyên Duy Tân, On divisibility relation graphs, 2025. See p. 14.
Andrei K. Svinin, Tuenter polynomials and a Catalan triangle, arXiv:1603.05748 [math.CO], 2016. See p.3.
Index entries for linear recurrences with constant coefficients, signature (5,-4).

Cf. A020989, A047849, A108019, A295521, A020522.

[(2/3)*(4^n-1): n in [0..40] ]; // Vincenzo Librandi, Apr 28 2011

A020988 := proc(n)
    2*(4^n-1)/3 ;
end proc: # R. J. Mathar, Feb 19 2015

(2(4^Range[0, 30] - 1))/3 (* or *) LinearRecurrence[{5, -4}, {0, 2}, 30] (* Harvey P. Dale, Sep 25 2013 *)

vector(100, n, n--; (2/3)*(4^n-1)) \\ Altug Alkan, Oct 06 2015

Vec(2*z/((1-z)*(1-4*z)) + O(z^30)) \\ Altug Alkan, Oct 11 2015

def A020988(n): return (2 * ((1 << (2 * n)) - 1)) // 3 # John Reimer Morales, Aug 05 2025

(((List.fill(20)(4: BigInt)).scanLeft(1: BigInt)( * )).map(2 * )).scanLeft(0: BigInt)( + ) // _Alonso del Arte, Sep 12 2019

a(n) = 4*a(n-1) + 2, a(0) = 0.
a(n) = A026644(2*n).
a(n) = A007583(n) - 1 = A039301(n+1) - 2 = A083584(n-1) + 1.
E.g.f. : (2/3)*(exp(4*x)-exp(x)). - Paul Barry, May 18 2003
a(n) = A007583(n+1) - 1 = A039301(n+2) - 2 = A083584(n) + 1. - Ralf Stephan, Jun 14 2003
G.f.: 2*x/((1-x)*(1-4*x)). - R. J. Mathar, Sep 17 2008
a(n) = a(n-1) + 2^(2n-1), a(0) = 0. - Washington Bomfim, Jan 22 2011
a(n) = A193652(2*n). - Reinhard Zumkeller, Aug 08 2011
a(n) = 5*a(n-1) - 4*a(n-2) (n > 1), a(0) = 0, a(1) = 2. - L. Edson Jeffery, Mar 02 2012
a(n) = (2/3)*A024036(n). - Omar E. Pol, Mar 15 2012
a(n) = 2*A002450(n). - Yosu Yurramendi, Jan 24 2017
From Seiichi Manyama, Nov 24 2017: (Start)
Zeta_{GL(2)/F_1}(s) = Product_{k = 1..4} (s-k)^(-b(2,k)), where Sum b(2,k)*t^k = t*(t-1)*(t^2-1). That is Zeta_{GL(2)/F_1}(s) = (s-3)*(s-2)/((s-4)*(s-1)).
Zeta_{GL(2)/F_1}(s) = Product_{n > 0} (1 - (1/s)^n)^(-A295521(n)) = Product_{n > 0} (1 - x^n)^(-A295521(n)) = (1-3*x)*(1-2*x)/((1-4*x)*(1-x)) = 1 + Sum_{k > 0} a(k-1)*x^k (x=1/s). (End)
From Oboifeng Dira, May 29 2020: (Start)
a(n) = A078008(2n+1) (second bisection).
a(n) = Sum_{k=0..n} binomial(2n+1, ((n+2) mod 3)+3k). (End)
From John Reimer Morales, Aug 04 2025: (Start)
a(n) = A000302(n) - A047849(n).
a(n) = A020522(n) + A000079(n) - A047849(n). (End)

Edited by N. J. A. Sloane, Sep 06 2006

A005578 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)-1.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 22, 43, 86, 171, 342, 683, 1366, 2731, 5462, 10923, 21846, 43691, 87382, 174763, 349526, 699051, 1398102, 2796203, 5592406, 11184811, 22369622, 44739243, 89478486, 178956971, 357913942, 715827883, 1431655766, 2863311531, 5726623062, 11453246123

Offset: 0

N. J. A. Sloane

Might be called the "Arima sequence" after Yoriyuki Arima who in 1769 constructed this sequence as the number of moves of the outer ring in the optimal solution for the Chinese Rings puzzle (baguenaudier). - Andreas M. Hinz, Feb 15 2017
Let u(k), v(k), w(k) be the 3 sequences defined by u(1)=1, v(1)=0, w(1)=0 and u(k+1) = u(k) + v(k), v(k+1) = u(k) + w(k), w(k+1) = v(k) + w(k); let M(k) = Max(u(k), v(k), w(k)); then a(n) = M(n). - Benoit Cloitre, Mar 25 2002
Unimodal analog of Fibonacci numbers: a(n+1) = Sum_{k=0..n/2} A071922(n-k, n-2*k). Based on the observation that F_{n+1} = Sum_{k} binomial (n-k, k). - Michele Dondi (bik.mido(AT)tiscalinet.it), Jun 30 2002
Numbers n at which the length of the symmetric signed digit expansion of n with q=2 (i.e., the length of the representation of n in the (-1,0,1)2 number system) increases. - _Ralf Stephan, Jun 30 2003
Row sums of Riordan array (1/(1-x), x/(1-2*x^2)). - Paul Barry, Apr 24 2005
For n > 0, record-values of A107910: a(n) = A107910(A023548(n)). - Reinhard Zumkeller, May 28 2005
2^(n+1) = 2*a(n) + 2*A001045(n) + A000975(n-1); e.g., 2^6 = 64 = 2*a(5) + 2*A001045(5) + 2*A000975(4) = 2*11 + 2*11 + 2*10. Let a(n), A001045(n) and A000975(n-1) = the legs of a triangle (a, b, c). Then a(n-1), A001045(n-1) and A000975(n-2) = (S-c), (S-b), (S-a), where S = the triangle semiperimeter. Example: a(5), A001045(5) and A000975(4) = triangle (a, b, c) = (11, 11, 10). Then a(4), A001045(4), A000975(3) = (S-c), (S-b), (S-a) = (6, 5, 5). - Gary W. Adamson, Dec 24 2007
a(n) is the number of length-n binary representations of a nonnegative integer that is divisible by 3. The initial digits are allowed to be 0's. a(4) = 6 because we have 0000, 0011, 0110, 1001, 1100, 1111. - Geoffrey Critzer, Jan 13 2014
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 0, 1; 0, 1, 1; 1, 1, 0] or of the 3 X 3 matrix [1, 1, 0; 1, 0, 1; 0, 1, 1]. - R. J. Mathar, Feb 04 2014
With 0 prefixed, this sequence is an autosequence of the first kind because the sequence of first differences A001045 is. Its companion is A052950. - Paul Curtz, Dec 18 2018, edited by M. F. Hasler, Dec 21 2018
Apparently, the sequence gives the distinct values taken by A129761, the first differences of fibbinary numbers. - Rémy Sigrist, Oct 26 2019
The sequence with offset 1 can be generated in three steps starting with A158780. First, put in alternate signs (1, -1, 1, -2, 2, -4, ...) and take the inverse; getting (1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, ...). Take the invert transform of the latter, resulting in the sequence. It follows from the inverti transform being 1, 1, 0, 1, 1, 2, 3, ... that (for example), a(9) = 171 = (1, 1, 0, 1, 1, 2, 3, 5, 8) dot (86, 43, 0, 11, 6, 6, 6, 5, 8) = (86 + 43 + 0 + 11 + 6 + 6 + 6 + 5 + 8). A similar procedure is shown in the Aug 08 2019 comment of A006356. - Gary W. Adamson, Feb 04 2022

R. K. Guy, Graphs and the strong law of small numbers. Graph theory, combinatorics and applications. Vol. 2 (Kalamazoo, MI, 1988), 597-614, Wiley-Intersci. Publ., Wiley, New York, 1991.
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
Sujith Uthsara Kalansuriya Arachchi, Hung Viet Chu, Jiasen Liu, Qitong Luan, Rukshan Marasinghe, and Steven J. Miller, On a Pair of Diophantine Equations, arXiv:2309.04488 [math.NT], 2023.
Joerg Arndt, Matters Computational (The Fxtbook), p. 315.
Ji Young Choi, Ternary Modified Collatz Sequences And Jacobsthal Numbers, Journal of Integer Sequences, Vol. 19 (2016), #16.7.5.
Ji Young Choi, A Generalization of Collatz Functions and Jacobsthal Numbers, J. Int. Seq., Vol. 21 (2018), Article 18.5.4.
Fan Chung and Shlomo Sternberg, Mathematics and the Buckyball
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See pp. 6, 17.
R. K. Guy, Letter to N. J. A. Sloane, Apr 08 1988 (annotated scanned copy, included with permission)
Clemens Heuberger and Helmut Prodinger, On minimal expansions in redundant number systems: Algorithms and quantitative analysis, Computing 66(2001), 377-393.
Andreas M. Hinz, The Lichtenberg sequence, Fib. Quart., 55 (2017), 2-12.
Andreas M. Hinz and Paul K. Stockmeyer, Precious Metal Sequences and Sierpinski-Type Graphs, J. Integer Seq., Vol 25 (2022), Article 22.4.8.
Gurmeet Singh Manku and Joe Sawada, A loopless Gray code for minimal signed-binary representations, 13th Annual European Symposium on Algorithms (ESA), LNCS 3669 (2005), 438-447.
Thor Martinsen, Non-Fisherian generalized Fibonacci numbers, Notes Num. Theor. Disc. Math. (2025) Vol. 31, No. 2, 370-389. See pp. 385, 387.
John P. McSorley, Counting structures in the Moebius ladder, Discrete Math., 184 (1998), 137-164.
Hans Olofsen, Blending functions based on trigonometric and polynomial approximations of the Fabius function, The Arctic University of Norway (Narvik, 2019).
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.
Chloe E. Shiff and Noah A. Rosenberg, Enumeration of rooted binary perfect phylogenies, arXiv:2410.14915 [q-bio.PE], 2024. See p. 16.
Andrew V. Sills and Hua Wang, On the maximal Wiener index and related questions, Discrete Applied Mathematics, Volume 160, Issues 10-11, July 2012, Pages 1615-1623.
Eric Weisstein's World of Mathematics, Walsh Function
Index entries for linear recurrences with constant coefficients, signature (2,1,-2).

Cf. A071922, A072176, A135229.
Bisections: A007583 and A047849.
Cf. also A000975, A001045 (first differences), A129761.
Cf. A006356.

List([0..40],n->(2^(n+1)+3+(-1)^n)/6); # Muniru A Asiru, Dec 22 2018

[(2^(n+1)+3+(-1)^n)/6: n in [0..40]]; // Vincenzo Librandi, Aug 14 2011

A005578:=-(-1+z+z^2)/((z-1)*(2*z-1)*(z+1)); # Simon Plouffe in his 1992 dissertation
with(combstruct):ZL0:=S=Prod(Sequence(Prod(a, Sequence(b))), a):ZL1:=Prod(begin_blockP, Z, end_blockP):ZL2:=Prod(begin_blockLR, Z, Sequence(Prod(mu_length, Z), card>=1), end_blockLR): ZL3:=Prod(begin_blockRL, Sequence(Prod(mu_length, Z), card>=1), Z, end_blockRL):Q:=subs([a=Union(ZL3), b=ZL3], ZL0), begin_blockP=Epsilon, end_blockP=Epsilon, begin_blockLR=Epsilon, end_blockLR=Epsilon, begin_blockRL=Epsilon, end_blockRL=Epsilon, mu_length=Epsilon:temp15:=draw([S, {Q}, unlabelled], size=15):seq(count([S, {Q}, unlabelled], size=n), n=2..34); # Zerinvary Lajos, Mar 08 2008

a=0; Table[a=2^n-a;(a/2+1)/2,{n,5!}] (* Vladimir Joseph Stephan Orlovsky, Nov 22 2009 *)
LinearRecurrence[{2,1,-2}, {1,1,2}, 40] (* G. C. Greubel, Aug 26 2019 *)

a(n)=(2^(n+1)+3+(-1)^n)/6 \\ Charles R Greathouse IV, Mar 22 2016

print([1+2**n//3 for n in range(40)])  # Gennady Eremin, Feb 05 2022

[(2^(n+1)+3+(-1)^n)/6 for n in (0..40)] # G. C. Greubel, Aug 26 2019

a(n) = ceiling(2^n/3).
a(n) = 1 + floor((2^n)/3) (proof by mathematical induction).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-3).
From Paul Barry, Jul 20 2003: (Start)
a(n) = A001045(n) + A000035(n+1), where A000035 = (0, 1, 0, 1, ...).
G.f.: (1 - x - x^2)/((1-x^2)*(1-2*x)). [Guy, 1988];
E.g.f.: (exp(2*x) - exp(-x))/3 + cosh(x) = (2*exp(2*x) + 3*exp(x) + exp(-x))/6. (End)
The 30 listed terms are given by a(0)=1, a(1)=1 and, for n > 1, by a(n) = a(n-1) + a(n-2) + Sum_{i=0..n-4} Fibonacci(i)*a(n-4-i). - John W. Layman, Jan 07 2000
a(n) = (2^(n+1) + 3 + (-1)^n)/6. - Vladeta Jovovic, Jul 02 2002
Binomial transform of A001045(n-1)(-1)^n + 0^n/2. - Paul Barry, Apr 28 2004
a(n) = (1 + A001045(n+1))/2. - Paul Barry, Apr 28 2004
a(n) = Sum_{k=0..n} (-1)^k*Sum_{j=0..n-k} (if((j-k) mod 2)=0, binomial(n-k, j), 0). - Paul Barry, Jan 25 2005
Let M = the 6 X 6 adjacency matrix of a benzene ring, (reference): [0,1,0,0,0,1; 1,0,1,0,0,0; 0,1,0,1,0,0; 0,0,1,0,1,0; 0,0,0,1,0,1; 1,0,0,0,1,0]. Then a(n) = leftmost nonzero term of M^n * [1,0,0,0,0,0]. E.g.: a(6) = 22 since M^6 * [1,0,0,0,0,0] = [22,0,21,0,21,0]. - Gary W. Adamson, Jun 14 2006
Starting (1, 2, 3, 6, 11, 22, ...), = row sums of triangle A135229. - Gary W. Adamson, Nov 23 2007
Let T = the 3 X 3 matrix [1,1,0; 1,0,1; 0,1,1]. Then T^n * [1,0,0] = [A005578(n), A001045(n), A000975(n-1)]. - Gary W. Adamson, Dec 24 2007
a(n) = 1 + 2^(n-1) - a(n-1) = a(n-1) + 2*a(n-2) - 1 = a(n-2) + 2^(n-2). - Paul Curtz, Jan 31 2009
a(n) = A023105(n+1) - 1. - Carl Joshua Quines, Jul 17 2019

Edited by N. J. A. Sloane, Jun 20 2015

A020522 a(n) = 4^n - 2^n.

Original entry on oeis.org

0, 2, 12, 56, 240, 992, 4032, 16256, 65280, 261632, 1047552, 4192256, 16773120, 67100672, 268419072, 1073709056, 4294901760, 17179738112, 68719214592, 274877382656, 1099510579200, 4398044413952, 17592181850112, 70368735789056, 281474959933440

Offset: 0

N. J. A. Sloane, Simon Plouffe

Number of walks of length 2*n+2 between any two diametrically opposite vertices of the cycle graph C_8. - Herbert Kociemba, Jul 02 2004
If we consider a(4*k+2), then 2^4 == 3^4 == 3 (mod 13); 2^(4*k+2) + 3^(4*k+2) == 3^k*(4+9) == 3*0 == 0 (mod 13). So a(4*k+2) can never be prime. - Jose Brox, Dec 27 2005
If k is odd, then a(n*k) is divisible by a(n), since: a(n*k) = (2^n)^k + (3^n)^k = (2^n + 3^n)*((2^n)^(k-1) - (2^n)^(k-2) (3^n) + - ... + (3^n)^(k-1)). So the only possible primes in the sequence are a(0) and a(2^n) for n>=1. I've checked that a(2^n) is composite for 3 <= n <= 15. As with Fermat primes, a probabilistic argument suggests that there are only finitely many primes in the sequence. - Dean Hickerson, Dec 27 2005
Let x,y,z be elements from some power set P(n), i.e., the power set of a set of n elements. Define a function f(x,y,z) in the following manner: f(x,y,z) = 1 if x is a subset of y and y is a subset of z and x does not equal z; f(x,y,z) = 0 if x is not a subset of y or y is not a subset of z or x equals z. Now sum f(x,y,z) for all x,y,z of P(n). This gives a(n). - Ross La Haye, Dec 26 2005
Number of monic (irreducible) polynomials of degree 1 over GF(2^n). - Max Alekseyev, Jan 13 2006
Let P(A) be the power set of an n-element set A and B be the Cartesian product of P(A) with itself. Then a(n) = the number of (x,y) of B for which x does not equal y. - Ross La Haye, Jan 02 2008
For n>1: central terms of the triangle in A173787. - Reinhard Zumkeller, Feb 28 2010
Pronic numbers of the form: (2^n - 1)*2^n, which is the n-th Mersenne number times 2^n, see A000225 and A002378. - Fred Daniel Kline, Nov 30 2013
Indices where records of A037870 occur. - Philippe Beaudoin, Sep 03 2014
Half the total edge length for a minimum linear arrangement of a hypercube of dimension n. (See Harper's paper below for proof). - Eitan Frachtenberg, Apr 07 2017
Number of pairs in GF(2)^{n+1} whose dot product is 1. - Christopher Purcell, Dec 11 2021

			n=5: a(5) = 4^5 - 2^5 = 1024 - 32 = 992 -> '1111100000'.

Vincenzo Librandi, Table of n, a(n) for n = 0..170
M. Archibald, A. Blecher, A. Knopfmacher, and M. E. Mays, Inversions and Parity in Compositions of Integers, J. Int. Seq., Vol. 23 (2020), Article 20.4.1.
Tom Copeland, The Kervaire-Milnor formula
John Elias, Illustration of initial terms: Twin 2^n hexagonal numbers
L. H. Harper, Optimal Assignment of Numbers to Vertices, J. SIAM 12(1), p. 131--135, March 1964; alternative link.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
The Sixtieth William Lowell Putnam Mathematical Competition, Question A6, Amer. Math. Monthly 107 (Oct 2000), 721-732; see p. 725.
Index entries for linear recurrences with constant coefficients, signature (6,-8).

Ratio of successive terms of A028365.
Cf. A000225, A060867, A161168, A006516, A059153, A065442.
Cf. A000079, A265736, A020988, A047849.
Cf. A000079, A000302.

a020522 = (* 2) . a006516  -- Reinhard Zumkeller, Dec 15 2015

[4^n - 2^n: n in [0..60]]; // Vincenzo Librandi, Apr 26 2011

A020522:=n->4^n-2^n; seq(A020522(n), n=0..50); # Wesley Ivan Hurt, Nov 29 2013

Table[4^n - 2^n, {n, 40}] (* or *) LinearRecurrence[{6, -8}, {0, 2}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 20 2012 *)

a(n)=4^n-2^n \\ Charles R Greathouse IV, Jan 30 2012

def A020522(n): return (1<Chai Wah Wu, Mar 10 2025

[4^n - 2^n for n in range(0,23)] # Zerinvary Lajos, Jun 05 2009

From Herbert Kociemba, Jul 02 2004: (Start)
G.f.: 2*x/((-1 + 2*x)*(-1 + 4*x)).
a(n) = 6*a(n-1) - 8*a(n-2). (End)
E.g.f.: exp(4*x) - exp(2*x). - Mohammad K. Azarian, Jan 14 2009
From Reinhard Zumkeller, Feb 07 2006, Jaroslav Krizek, Aug 02 2009: (Start)
a(n) = A099393(n)-A000225(n+1) = A083420(n)-A099393(n).
In binary representation, n>0: n 1's followed by n 0's (A138147(n)).
A000120(a(n)) = n.
A023416(a(n)) = n.
A070939(a(n)) = 2*n.
2*a(n)+1 = A030101(A099393(n)). (End)
a(n) = A085812(n) - A001700(n). - John Molokach, Sep 28 2013
a(n) = 2*A006516(n) = A000079(n)*A000225(n) = A265736(A000225(n)). - Reinhard Zumkeller, Dec 15 2015
a(n) = (4^(n/2) - 4^(n/4))*(4^(n/2) + 4^(n/4)). - Bruno Berselli, Apr 09 2018
Sum_{n>0} 1/a(n) = E - 1, where E is the Erdős-Borwein constant (A065442). - Peter McNair, Dec 19 2022
a(n) = A000302(n) - A000079(n). - John Reimer Morales, Aug 04 2025

cp's OEIS Frontend

A002450 a(n) = (4^n - 1)/3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Magma

Maple

Mathematica

Maxima

PARI

PARI

Python

Scala

Formula

A078008 Expansion of (1 - x)/((1 + x)*(1 - 2*x)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Python

Sage

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Python

Scala

Formula

Extensions

A005578 a(2*n) = 2*a(2*n-1), a(2*n+1) = 2*a(2*n)-1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A020522 a(n) = 4^n - 2^n.

Views

Author

Keywords

Comments

A078008 Expansion of (1 - x)/((1 + x)(1 - 2x)).

A005578 a(2n) = 2a(2n-1), a(2n+1) = 2a(2n)-1.