A060590 Numerator of the expected time to finish a random Tower of Hanoi problem with n disks using optimal moves.

0, 2, 2, 14, 10, 62, 42, 254, 170, 1022, 682, 4094, 2730, 16382, 10922, 65534, 43690, 262142, 174762, 1048574, 699050, 4194302, 2796202, 16777214, 11184810, 67108862, 44739242, 268435454, 178956970, 1073741822, 715827882, 4294967294

Offset

0,2

Links

Harry J. Smith, Table of n, a(n) for n = 0..500

Index entries for linear recurrences with constant coefficients, signature (0,5,0,-4).

Index entries for sequences related to Towers of Hanoi

Formula

a(n) = 2*(2^n - 1)*(2 - (-1)^n)/3.

a(2n) = A020988(n-1).

From Ralf Stephan, Mar 07 2003: (Start)

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

a(n+4) = 5*a(n+2) - 4*a(n). (End)

Example

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.

Prog

(PARI) a(n)={2*(2^n - 1)*(2 - (-1)^n)/3} \\ Harry J. Smith, Jul 07 2009

Crossrefs

Denominator is A010684(n). Cf. A007798, A060586, A060589, A020988 (even bisection).

Sequence in context: A327930 A068511 A306544 * A365161 A129083 A045685

Adjacent sequences: A060587 A060588 A060589 * A060591 A060592 A060593

Keyword

easy,frac,nonn

Author

Henry Bottomley, Apr 05 2001

Status

approved