Med 3 disker må vi først flytte de 2 øverste diskene over på hjelpepinnen. Det tar 3 trekk (siden $F(2)=3$). Deretter flytter vi den nederste (største) disken direkte til målpinnen — det er 1 trekk. Til slutt flytter vi de 2 diskene fra hjelpepinnen oppå den store disken på målpinnen, som igjen tar 3 trekk.

Totalt antall trekk blir da

$\underline{\underline{F(3)=7}}$

Samme resonnement som i a) gjelder for et vilkårlig antall disker $n$. For å flytte $n$ disker fra startpinnen til målpinnen må vi

1. flytte de $n-1$ øverste diskene over på hjelpepinnen: $F(n-1)$ trekk
2. flytte den største (nederste) disken direkte til målpinnen: $1$ trekk
3. flytte de $n-1$ diskene fra hjelpepinnen oppå den store disken på målpinnen: $F(n-1)$ trekk

Dette gir den rekursive sammenhengen

Vi bruker sammenhengen til å regne oss trinnvis oppover til $F(10)$:

$\underline{\underline{F(10)=1023}}$

Vi ser på verdiene vi fant i b):

Hvert tall er nøyaktig $1$ mindre enn en potens av $2$:

Dette gir mistanke om den eksplisitte formelen

Vi beviser formelen $F(n)=2^n-1$ ved komplett induksjon på $n$.

Grunntilfelle ($n=1$):

Formelen stemmer for $n=1$.

Induksjonshypotese: Anta at formelen er sann for et vilkårlig $k\ge 1$, altså at

Induksjonssteg: Vi skal vise at formelen da også er sann for $n=k+1$. Fra den rekursive sammenhengen i b) har vi $F(k+1)=2F(k)+1$. Setter vi inn induksjonshypotesen får vi

Dette er nettopp formelen for $n=k+1$.

Konklusjon: Siden formelen er sann for $n=1$, og siden den er sann for $n=k+1$ hver gang den er sann for $n=k$, følger det ved induksjon at