A048473 a(0)=1, a(n) = 3*a(n-1) + 2; a(n) = 2*3^n - 1.

1, 5, 17, 53, 161, 485, 1457, 4373, 13121, 39365, 118097, 354293, 1062881, 3188645, 9565937, 28697813, 86093441, 258280325, 774840977, 2324522933, 6973568801, 20920706405, 62762119217, 188286357653, 564859072961, 1694577218885, 5083731656657, 15251194969973, 45753584909921

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

The number of triangles (of all sizes, including holes) in Sierpiński's triangle after n inscriptions. - Lee Reeves, May 10 2004

The sequence is not only related to Sierpiński's triangle, but also to "Floret's cube" and the quaternion factor space Q X Q / {(1,1), (-1,-1)}. It can be written as a_n = ves((A+1)x)^n) as described at the Math Forum Discussions link. - Creighton Dement, Jul 28 2004

Relation to C(n) = Collatz function iteration using only odd steps: If we look for record subsequences where C(n) > n, this subsequence starts at 2^n - 1 and stops at the local maximum of 2*3^n - 1. Examples: [3,5], [7,11,17], [15,23,35,53], ..., [127,191,287,431,647,971,1457]. - Lambert Klasen, Mar 11 2005

Group the natural numbers so that the (2n-1)-th group sum is a multiple of the (2n)-th group containing one term. (1,2),(3),(4,5,6,7,8,9,10,11),(12),(13,14,15,16,17,18,19,...,38),(39),(40,41,...,118,119),(120), (121,122,123,...) ... a(n) = {the sum of the terms of (2n-1)-th group}/{the term of (2n)th group}. The first term of the odd numbered group is given by A003462. The only term of even numbered group is given by A029858. - Amarnath Murthy, Aug 01 2005

a(n)+1 = A008776(n); it appears that this gives the number of terms in the (n+1)-th "gap" of numbers missing in A171884. - M. F. Hasler, May 09 2013

Sum of n-th row of triangle of powers of 3: 1; 1 3 1; 1 3 9 3 1; 1 3 9 27 9 3 1; ... - Philippe Deléham, Feb 23 2014

For n >= 3, also the number of dominating sets in the n-helm graph. - Eric W. Weisstein, May 28 2017

The number of elements of length <= n in the free group on two generators. - Anton Mellit, Aug 10 2017

In general, a first order inhomogeneous recurrence of the form s(0) = a, s(n) = m*s(n-1) + k, n>0, will have a closed form of a*m^n + ((m^n-1)/(m-1))*k. - Gary Detlefs, Jun 07 2024

Examples

			a(0) = 1;
a(1) = 1 + 3 + 1 = 5;
a(2) = 1 + 3 + 9 + 3 + 1 = 17;
a(3) = 1 + 3 + 9 + 27 + 9 + 3 + 1 = 53; etc. - _Philippe Deléham_, Feb 23 2014
		

References

• Theoni Pappas, Math Stuff, Wide World Publ/Tetra, San Carlos CA, page 15, 2002.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Creighton Dement, A paper on floretions and quaternions, some questions, The Math Forum.
• Eric Weisstein's World of Mathematics, Dominating Set.
• Eric Weisstein's World of Mathematics, Helm Graph.
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

a(n)=T(2,n), array T given by A048471.

Cf. A003462, A029858. A column of A119725.

Cf. A008776, A010684, A046055, A112468, A112739, A134347, A171884.

Programs

Magma

[2*3^n - 1: n in [0..30]]; // Vincenzo Librandi, Sep 23 2011

Maple

g:= ((1+x)/(1-3*x)/(1-x)): gser:=series(g, x=0, 43): seq(coeff(gser, x, n), n=0..30); # Zerinvary Lajos, Jan 11 2009; typo fixed by Marko Mihaily, Mar 07 2009

Mathematica

NestList[3 # + 2 &, 1, 30] (* Harvey P. Dale, Mar 06 2012 *)
LinearRecurrence[{4, -3}, {1, 5}, 30] (* Harvey P. Dale, Mar 06 2012 *)
Table[2 3^n - 1, {n, 20}] (* Eric W. Weisstein, May 28 2017 *)
2 3^Range[20] - 1 (* Eric W. Weisstein, May 28 2017 *)

PARI

first(m)=vector(m,n,n--;2*3^n - 1) \\ Anders Hellström, Dec 11 2015

Formula

n-th difference of a(n), a(n-1), ..., a(0) is 2^(n+1) for n=1, 2, 3, ...

a(0)=1, a(n) = a(n-1) + 3^n + 3^(n-1). - Lee Reeves, May 10 2004

a(n) = (3^n + 3^(n+1) - 2)/2. - Creighton Dement, Jul 31 2004

(1, 5, 17, 53, 161, ...) = Ternary (1, 12, 122, 1222, 12222, ...). - Gary W. Adamson, May 02 2005

Row sums of triangle A134347. Also, binomial transform of A046055: (1, 4, 8, 16, 32, 64, ...); and double binomial transform of A010684: (1, 3, 1, 3, 1, 3, ...). - Gary W. Adamson, Oct 21 2007

G.f.: (1+x)/((1-3*x)*(1-x)). - Zerinvary Lajos, Jan 11 2009; corrected by R. J. Mathar, Jan 21 2009

a(0)=1, a(1)=5, a(n) = 4*a(n-1) - 3*a(n-2). - Harvey P. Dale, Mar 06 2012

a(n) = Sum_{k=0..n} A112468(n,k)*4^k. - Philippe Deléham, Feb 23 2014

E.g.f.: exp(x)*(2*exp(2*x) - 1). - Elmo R. Oliveira, Mar 08 2025

Extensions

Better description from Amarnath Murthy, May 27 2001