数と極限数のいろいろ、漸化式ハノイの塔、円盤の枚数、最短手数、一般化

学習環境

微分積分演習〈理工系の数学入門コース/演習新装版〉 (和達三樹(著)、十河清(著)、岩波書店)の第1章(数と極限)、1-1(数のいろいろ、漸化式)、問題5の解答を求めてみる。

漸化式。

M_{n + 1} = M_{n} + 1 + M_{n} = 2 M_{n} + 1,

よって、

M_{n + 1} + 1 = 2 (M_{n + 1} + 1)

また、

\begin{array}{l} M_{1} = 1 \\ M_{1} + 1 = 2 \end{array}

ゆえに、

{(M_{n} + 1)}_{n \in ℕ \ {0}}

は初項2、公比2の等比数列なので、

M_{n} + 1 = 2 \cdot 2^{n - 1}

よって、求めるゲーム、ハノイの塔の最短手数は

M_{n} = 2^{n} - 1

で与えられる。

（証明終）

コード(Wolfram Language, Jupyter)

WolframAlpha["tower of hanoi, 5 disks"]

WolframAlpha["tower of hanoi, 4 disks"]

WolframAlpha["tower of hanoi, 10 disks"]

2^10-1