%I #19 Mar 11 2021 20:41:09
%S 0,2,2,14,10,62,42,254,170,1022,682,4094,2730,16382,10922,65534,43690,
%T 262142,174762,1048574,699050,4194302,2796202,16777214,11184810,
%U 67108862,44739242,268435454,178956970,1073741822,715827882,4294967294
%N Numerator of the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.
%H Harry J. Smith, <a href="/A060590/b060590.txt">Table of n, a(n) for n = 0..500</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,5,0,-4).
%H <a href="/index/To#Hanoi">Index entries for sequences related to Towers of Hanoi</a>
%F a(n) = 2*(2^n - 1)*(2 - (-1)^n)/3.
%F a(2n) = A020988(n-1).
%F From _Ralf Stephan_, Mar 07 2003: (Start)
%F G.f.: (4*x^3+2*x^2+2*x)/(4*x^4-5*x^2+1).
%F a(n+4) = 5*a(n+2) - 4*a(n). (End)
%e a(2)=2 since there are nine equally likely possibilities, with times required of 0,1,1,2,2,3,3,3,3 giving an average of 18/9 = 2/1.
%o (PARI) a(n)={2*(2^n - 1)*(2 - (-1)^n)/3} \\ _Harry J. Smith_, Jul 07 2009
%Y Denominator is A010684(n). Cf. A007798, A060586, A060589, A020988 (even bisection).
%K easy,frac,nonn
%O 0,2
%A _Henry Bottomley_, Apr 05 2001