Vi skal flytte 3 disker fra venstre pinne til høyre pinne. Kall pinnene A (venstre), B (midtre) og C (høyre), og diskene 1 (minst), 2 (mellom) og 3 (størst).

Strategien er: flytt de to øverste diskene til midtpinnen, flytt den største til høyre, og flytt de to øverste tilbake.

1. Disk 1: A → C
2. Disk 2: A → B
3. Disk 1: C → B
4. Disk 3: A → C
5. Disk 1: B → A
6. Disk 2: B → C
7. Disk 1: A → C

Det er altså $3+1+3=7$ trekk, og vi kan ikke gjøre det på færre.

For å flytte $n$ disker fra pinne A til pinne C bruker vi denne strategien:

1. Flytt de øverste $n-1$ diskene fra A til B. Det krever $F(n-1)$ trekk.
2. Flytt den største disken fra A til C. Det er $1$ trekk.
3. Flytt de $n-1$ diskene fra B til C. Det krever igjen $F(n-1)$ trekk.

Den rekursive sammenhengen er:

med startverdien $F(1)=1$.

Vi bygger opp tabellen:

Fra tabellen i b) ser vi at verdiene er $1,3,7,15,31,\dots$ Vi legger merke til at disse er $2^1-1,2^2-1,2^3-1,2^4-1,2^5-1,\dots$

Vi gjetter at den eksplisitte formelen er:

Verifisering: Vi setter inn i rekursjonen og sjekker at formelen stemmer:

Formelen er altså konsistent med rekursjonen. Kombinert med startverdien $F(1)=2^1-1=1$ gir dette: