ハノイの塔

　「ハノイの塔」と呼ばれるパズルです。

　図のように,３本の支柱があります。メニューから円盤の枚数を選ぶと大きさの異なる円盤が重なった山ができます。

　ルール
　　�@円盤の山を中央の支柱に移動させてください。
　　�A円盤は1枚ずつ動かします。
　　�B小さい円盤の上に大きい円盤を重ねることはできません。
　
　　動かす円盤をクリックで選択し,移動先をもう一度クリックすると動きます。

　できるだけ,手数を少なくしてください。各枚数で,最も少ない手数が記録されます。
　
　できましたか？

　さてこのとき，円盤の枚数と最少手数はどんな関係にあるでしょうか。
　つまり，1枚のときの最少手数を a₁，２枚のときを a₂，３枚のときが a₃，……
というように数列として考えていくと，一般項 a_n はどうなるかということです。
　考えてみましょう。

　この　 a_n+1 = 2a_n + 1 　ような式を漸化式と呼びます。

　では次に，この漸化式から一般項を求めてみましょう。

　最後に，なぜ 1 を加えるのか，どうやって a_n+1 + 1 =2(a_n + 1) の形に変形するのかは，自分で考えてみてください。