%I #22 Sep 08 2022 08:45:03
%S 0,2,18,126,810,5022,30618,185166,1115370,6705342,40271418,241746606,
%T 1450833930,8706066462,52239587418,313447090446,1880711240490,
%U 11284353536382,67706379498618,406239051832686,2437436635519050,14624626786683102,87747781640805018
%N a(n) = 2*(2^n-1)*3^(n-1).
%C a(n)/3^n is the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.
%H Harry J. Smith, <a href="/A060589/b060589.txt">Table of n, a(n) for n = 0..200</a>
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (9,-18).
%F a(n) = Sum_{j<2^n} j*A001316(j) = 6*a(n-1) + A008776(n-1) = 4*A000400(n-1) - A008776(n-1) = A000244(n)*A060590(n)/A010684(n).
%F G.f.: 2*x/((3*x-1)*(6*x-1)). [_Colin Barker_, Dec 26 2012]
%t Table[2 (2^n - 1) 3^(n - 1), {n, 0, 50}] (* or *) LinearRecurrence[{9, -18}, {0, 2}, 40] (* _Vincenzo Librandi_, Jul 03 2018 *)
%o (PARI) a(n)={2*(2^n - 1)*3^(n - 1)} \\ _Harry J. Smith_, Jul 07 2009
%o (Magma) [2*(2^n - 1)*3^(n - 1): n in [0..30]]; // _Vincenzo Librandi_, Jul 03 2018
%Y Cf. A007798, A060586, A060590.
%K nonn,easy
%O 0,2
%A _Henry Bottomley_, Apr 05 2001
%E Corrected by _T. D. Noe_, Nov 07 2006