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

%I #44 Nov 20 2022 13:06:26

%S 1,5,19,71,271,1055,4159,16511,65791,262655,1049599,4196351,16781311,

%T 67117055,268451839,1073774591,4295032831,17180000255,68719738879,

%U 274878431231,1099512676351,4398048608255,17592190238719

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

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

%C In binary representation, a leading one followed by n zeros then by n ones. - _Reinhard Zumkeller_, Feb 07 2006

%C 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

%H Vincenzo Librandi, <a href="/A099393/b099393.txt">Table of n, a(n) for n = 0..170</a>

%H A. M. Cohen and D. E. Taylor, <a href="https://doi.org/10.1080/00029890.2007.11920454">On a Certain Lie Algebra Defined By a Finite Group</a>, American Mathematical Monthly, volume 114, number 7, August-September 2007, pages 633-638. Also <a href="https://www.maths.usyd.edu.au/u/pubs/publist/preprints/2006/cohen-12.html">preprint</a>. a(n) = t_n in proof of theorem 6.2.

%H Sergey Kitaev and Toufik Mansour, <a href="http://arXiv.org/abs/math.CO/0210268">The Peano curve and counting occurrences of some patterns</a>, arXiv:math/0210268 [math.CO], 2002. Section 3 lemma 1, d_2^n = a(n-1).

%H Sergey Kitaev, Toufik Mansour, and Patrice Séébold, <a href="https://doi.org/10.25596/jalc-2004-439">Generating the Peano curve and counting occurrences of some patterns</a>, Journal of Automata, Languages and Combinatorics, volume 9, number 4, 2004, pages 439-455. Also at <a href="https://www.researchgate.net/publication/230802620_Generating_the_Peano_curve_and_counting_occurrences_of_some_patterns">ResearchGate</a>. Section 4, |P_n|_r = a(n-1).

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (7,-14,8).

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

%F 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

%F a(n) = 2^(2*n-1) + 2*a(n-1) + 1. - _Roger L. Bagula_, Aug 08 2007

%F From _Mohammad K. Azarian_, Jan 15 2009: (Start)

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

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

%F a(n) = A279396(n+4, 4). - _Wolfdieter Lang_, Jan 10 2017

%F a(n) = A002378(2^n) - 1 = 2*A000217(2^n) - 1 = 2*A007582(n) - 1. - _Peter Munn_, Nov 20 2022

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

%t LinearRecurrence[{7,-14,8},{1,5,19},30] (* _Harvey P. Dale_, Sep 06 2015 *)

%o (Magma) [4^n + 2^n - 1: n in [0..60]]; // _Vincenzo Librandi_, Apr 26 2011

%o (PARI) a(n)=4^n+2^n-1; \\ _Charles R Greathouse IV_, Sep 24 2015

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

%K nonn,easy

%O 0,2

%A _Ralf Stephan_, Oct 20 2004