OFFSET
0,3
COMMENTS
All 3^n possible starting positions are chosen with equal probability.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
M. A. Alekseyev and T. Berger, Solving the Tower of Hanoi with Random Moves. In: J. Beineke, J. Rosenhouse (eds.) The Mathematics of Various Entertaining Subjects: Research in Recreational Math, Princeton University Press, 2016, pp. 65-79. ISBN 978-0-691-16403-8
Index entries for linear recurrences with constant coefficients, signature (9,-23,15).
FORMULA
For n>1, a(n) = 8*a(n-1) - 15*a(n-2) + 2 = 2*A016209(n-2). - Henry Bottomley, Jun 06 2000
a(n) = (5^n - 2*3^n + 1) / 4. - Henry Bottomley, Jun 06 2000, proved by Max Alekseyev, Feb 04 2008
From Colin Barker, Sep 17 2014: (Start)
a(n) = 9*a(n-1) - 23*a(n-2) + 15*a(n-3).
G.f.: 2*x^2/((1-x)*(1-3*x)*(1-5*x)). (End)
E.g.f.: (exp(x) - 2*exp(3*x) + exp(5*x))/4. - G. C. Greubel, Mar 05 2020
MAPLE
seq( (1 -2*3^n +5^n)/4, n=0..25); # G. C. Greubel, Mar 05 2020
MATHEMATICA
Table[(1 -2*3^n +5^n)/4, {n, 0, 25}] (* G. C. Greubel, Mar 05 2020 *)
PROG
(Magma) [(5^n-2*3^n+1)/4: n in [0..25]]; // Vincenzo Librandi, Oct 11 2011
(PARI) concat([0, 0], Vec(-2*x^2/((x-1)*(3*x-1)*(5*x-1)) + O(x^30))) \\ Colin Barker, Sep 17 2014
(Sage) [(1 -2*3^n +5^n)/4 for n in (0..25)] # G. C. Greubel, Mar 05 2020
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
David G. Poole (dpoole(AT)trentu.ca)
EXTENSIONS
More precise definition and more terms from Max Alekseyev, Feb 04 2008
a(0)=0 prepended by Max Alekseyev, Sep 08 2014
STATUS
approved