A060816 a(0) = 1; a(n) = (5*3^(n-1) - 1)/2 for n > 0.

1, 2, 7, 22, 67, 202, 607, 1822, 5467, 16402, 49207, 147622, 442867, 1328602, 3985807, 11957422, 35872267, 107616802, 322850407, 968551222, 2905653667, 8716961002, 26150883007, 78452649022, 235357947067, 706073841202

Offset: 0

Author

Jason Earls, Apr 29 2001

Keywords

• easy
• nonn

Comments

From Erich Friedman's math magic page 2nd paragraph under "Answers" section.

Let A be the Hessenberg matrix of order n, defined by: A[1,j] = 1, A[i,i] = 2,(i>1), A[i,i-1] = -1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n) = (-1)^n*charpoly(A,-1). - Milan Janjic, Jan 26 2010

If n > 0 and H = hex number (A003215), then 9*H(a(n)) - 2 = H(a(n+1)), for example 9*H(2) - 2 = 9*19 - 2 = 169 = H(7). For n > 2, this is a subsequence of A017209, see formula. - Klaus Purath, Mar 31 2021

Consider the Tower of Hanoi puzzle of order n (i.e., with n rings to be moved). Label each ring with a distinct symbol from an alphabet of size n. Construct words by performing moves according to the standard rules of the puzzle, recording the corresponding symbol each time a ring is moved. To ensure finiteness, we forbid returning to any previously encountered state. Additionally, we impose the constraint that the same ring cannot be moved twice in succession. Then, a(n) is the number of distinct words that can be formed under these rules. - Thomas Baruchel, Jul 22 2025

Links

• Harry J. Smith, Table of n, a(n) for n = 0..200
• Erich Friedman, Math. Magic
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. A005030 (first differences), A244762 (partial sums).

Cf. A003215, A003462, A007051, A008343, A017209, A057198, A134931.

Programs

Mathematica

LinearRecurrence[{4,-3},{1,2,7},30] (* Harvey P. Dale, Nov 15 2022 *)

PARI

A060816(n)=if(n, 3^n*5\6, 1) \\ M. F. Hasler, Apr 06 2019

Formula

The following is a summary of formulas added over the past 18 years.

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

a(n) = 3*a(n-1) + 1; with a(0)=1, a(1)=2. - Jason Earls, Apr 29 2001

From Henry Bottomley, May 01 2001: (Start)

For n>0, a(n) = a(n-1)+5*3^(n-2) = a(n-1)+A005030(n-2).

For n>0, a(n) = (5*A003462(n)+1)/3. (End)

From Colin Barker, Apr 24 2012: (Start)

a(n) = 4*a(n-1) - 3*a(n-2) for n > 2.

G.f.: (1-2*x+2*x^2)/((1-x)*(1-3*x)). (End)

a(n+1) = A134931(n) + 1. - Philippe Deléham, Apr 14 2013

For n > 0, A008343(a(n)) = 0. - Dmitry Kamenetsky, Feb 14 2017

For n > 0, a(n) = floor(3^n*5/6). - M. F. Hasler, Apr 06 2019

From Klaus Purath, Mar 31 2021: (Start)

a(n) = A017209(a(n-2)), n > 2.

a(n) = 2 + Sum_{i = 0..n-2} A005030(i).

a(n+1)*a(n+2) = a(n)*a(n+3) + 20*3^n, n > 1.

a(n) = 3^n - A007051(n-1). (End)

E.g.f.: (5*exp(3*x) - 3*exp(x) + 4)/6. - Stefano Spezia, Aug 28 2023

Extensions

Edited by M. F. Hasler, Apr 06 2019 and by N. J. A. Sloane, Apr 09 2019