ハノイの塔問題・考察（１）を示します。
考察（１）
n枚の円盤の移動回数をf(n)として求めてみる。
まず、手順(ア)にしたがって、棒Ｘの上からn-1枚の円盤を棒Ｚに移動するのに
f(n-1)回の移動回数が必要である。
つぎに、手順(イ)にしたがって、棒Ｘのn枚目の円盤を棒Ｙに移動するため1回の移動が必要である。
最後に、手順(ウ)にしたがって、棒Ｚのn-1枚の円盤を棒Ｙに移動するため
f(n-1)回の移動回数が必要になる。
合計で、2f(n-1)+1回の移動回数になる。すなわち、
f(n) = 2f(n-1) + 1
という関係が成り立つ。明らかにf(1)=1であることから、この関係式を解くと、
を得る。
