A103453 a(n) = 0^n + 3^n - 1.

1, 2, 8, 26, 80, 242, 728, 2186, 6560, 19682, 59048, 177146, 531440, 1594322, 4782968, 14348906, 43046720, 129140162, 387420488, 1162261466, 3486784400, 10460353202, 31381059608, 94143178826, 282429536480, 847288609442

Offset: 0

Author

Paul Barry, Feb 06 2005

Keywords

• easy
• nonn

Comments

A transform of 3^n under the matrix A103452.

a(n) is the number of moves required to solve a Towers of Hanoi puzzle of 3 towers in a line (no direct connection between the two towers on the ends) with n pieces to be moved from one end tower to the other. This is easily proved through demonstration. - Roderick Kimball, Nov 22 2015

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..190
• Steven Schlicker, Roman Vasquez, and Rachel Wofford, Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. A103452.

Essentially identical to A024023.

Programs

Magma

[0^n+3^n-1: n in [0..30] ]; // Vincenzo Librandi, Apr 30 2011

Mathematica

Table[If[n==0, 1, 3^n -1], {n, 0, 30}] (* G. C. Greubel, Jun 18 2021 *)
LinearRecurrence[{4,-3},{1,2,8},30] (* Harvey P. Dale, Feb 13 2022 *)

PARI

a(n) = if(n==0, 1, 3^n-1); \\ Altug Alkan, Nov 22 2015

Sage

[3^n -1 +0^n for n in (0..30)] # G. C. Greubel, Jun 18 2021

Formula

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

a(n) = Sum_{k=0..n} A103452(n, k)*3^k.

a(n) = Sum_{k=0..n} (2*0^(n-k) - 1)*0^(k*(n-k))*3^k.

From G. C. Greubel, Jun 18 2021: (Start)

E.g.f.: 1 - exp(x) + exp(3*x).

a(n) = [n=0] + 2*A003462(n). (End)