A099393 a(n) = 4^n + 2^n - 1.

1, 5, 19, 71, 271, 1055, 4159, 16511, 65791, 262655, 1049599, 4196351, 16781311, 67117055, 268451839, 1073774591, 4295032831, 17180000255, 68719738879, 274878431231, 1099512676351, 4398048608255, 17592190238719

Offset: 0

Author

Ralf Stephan, Oct 20 2004

Keywords

• nonn
• easy

Comments

Number of occurrences of letter 2 in the (n+1)-st Peano word.

In binary representation, a leading one followed by n zeros then by n ones. - Reinhard Zumkeller, Feb 07 2006

The number of involutions in group G_n G_{n+1} = G_n(operation) D_8. For example, Q_8->1 involution; D_8->5 involutions - Roger L. Bagula, Aug 08 2007

Examples

			n=5: a(5)=4^5+2^5-1=1024+32-1=1055 -> '10000011111'.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..170
• A. M. Cohen and D. E. Taylor, On a Certain Lie Algebra Defined By a Finite Group, American Mathematical Monthly, volume 114, number 7, August-September 2007, pages 633-638. Also preprint. a(n) = t_n in proof of theorem 6.2.
• Sergey Kitaev and Toufik Mansour, The Peano curve and counting occurrences of some patterns, arXiv:math/0210268 [math.CO], 2002. Section 3 lemma 1, d_2^n = a(n-1).
• Sergey Kitaev, Toufik Mansour, and Patrice Séébold, Generating the Peano curve and counting occurrences of some patterns, Journal of Automata, Languages and Combinatorics, volume 9, number 4, 2004, pages 439-455. Also at ResearchGate. Section 4, |P_n|_r = a(n-1).
• Index entries for linear recurrences with constant coefficients, signature (7,-14,8).

Crossrefs

See the formula section for the relationships with A000120, A000217, A000225, A002378, A007582, A020522, A023416, A030101, A063376, A070939, A083420, A279396.

Programs

Magma

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

Mathematica

LinearRecurrence[{7,-14,8},{1,5,19},30] (* Harvey P. Dale, Sep 06 2015 *)

PARI

a(n)=4^n+2^n-1; \\ Charles R Greathouse IV, Sep 24 2015

Python

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

Formula

a(n) = A063376(n)-1.

a(n) = A020522(n) + A000225(n+1) = A083420(n) - A020522(n); A000120(a(n)) = n+1; A023416(a(n))=n; A070939(a(n)) = 2*n+1; 2*A020522(n)+1 = A030101(a(n)). - Reinhard Zumkeller, Feb 07 2006

a(n) = 2^(2*n-1) + 2*a(n-1) + 1. - Roger L. Bagula, Aug 08 2007

From Mohammad K. Azarian, Jan 15 2009: (Start)

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

E.g.f.: e^(4*x) + e^(2*x) - e^x. (End)

a(n) = A279396(n+4, 4). - Wolfdieter Lang, Jan 10 2017

a(n) = A002378(2^n) - 1 = 2*A000217(2^n) - 1 = 2*A007582(n) - 1. - Peter Munn, Nov 20 2022