Spillet «Hanois tårn» består av tre pinner og en mengde disker med ulik radius som skal tres på pinnene.

Når spillet starter, skal alle diskene være plassert på samme pinne. Ingen av diskene skal ha en større disk liggende oppå seg.

Målet er å flytte alle diskene over på én av de to ledige pinnene. Det er bare lov å flytte én disk av gangen. Diskene som ikke flyttes, må ligge på en pinne. Det er aldri lov å plassere en større disk oppå en mindre disk.

Det minste antallet forflytninger du må gjøre for å flytte $n$ disker kaller vi $F(n)$.

a)

Bestem $F(3)$.

Det er en rekursiv sammenheng mellom $F(n)$ og $F(n-1)$.

b)

Bestem den rekursive sammenhengen. Bruk denne til å bestemme $F(10)$.

Det finnes også en eksplisitt formel for $F$.

c)

Undersøk og finn denne formelen.

d)

Bevis formelen ved å bruke induksjon på antall disker $n$.