Ａ地点　　　　　　　　　　　　Ｂ地点　　　　　　　　　　　Ｃ地点

　 n 枚の皿でのハノイの塔の移動を完成させるための最少手技数を f (n) とします。
　 ３地点のうち元のＡ地点には最大の皿が １ つだけ置いてあり、 Ｂ地点にはその他の皿がハノイの塔状に重ねて置いてあり、 Ｃ地点は空き地になっている場面を考えましょう。 ハノイの塔の初期状態からこの状態になるための最少手技数は f (n-1) 回 です。 ここから、 ハノイの塔の移動を完成させるための最少手技数は、 最大の皿をＣ地点に移動してから、 Ｂ地点に重ねて置いてある皿たちを最大の皿の上に最少手技数で移動させればいいので、 f (n-1)+1 です。 したがって次の漸化式が成り立ちます。
　　　f (n) ＝ 2 × f (n-1) + 1
したがって、
　　　f (n)＋１ ＝ 2 × { f (n-1)+1 }
よって、
　　　f (n)＋１ ＝ 2 ⁿ
よって、
　　　f (n) ＝ 2 ⁿ−1