数学的帰納法による中本君の証明を記しておこう． 念のために証明すべき命題をきちんと述べておくと， 次のとおりである．

証明　まず， 1 段のハノイの塔を考える． n = 1 の場合は， 2ⁿ - 1 = 2¹ - 1 = 1 だから， m の値としてとりえるのは 1 だけである． その 1 を 2 進法で表しても 1 だから， 右から数えていって始めて出会う 1 もその 1 桁目の 1 である． このとき，動くのは板 1 であり，命題のとおりになっている．

　続いて， n-1 段のハノイの塔に対して上の命題が成立すると仮定して （この仮定を「帰納法の仮定」と呼ぶ）， n 段の場合にもそれが成立することを示す． その際， ハノイの塔の手数 a_n を求めたときと同じ考え方が適用できる． つまり，板 n を動かす瞬間とその前後を考察するのである．

　板 n が棒 1 から棒 2 に動くためには， まず，それを無視した n-1 段のハノイの塔を棒 1 から棒 3 に移動する必要があった． その移動は 1 手目から 2^n-1-1 手目までで行われるので， 帰納法の仮定により， その間は命題に従って指定された板が動かされることになる．

　板 n が動く瞬間は 2^n-1 手目だから， m = 2^n-1 であり，それを 2 進数で表せば， 10 … 000 となっていて， n 桁目のみが 1 になっている． ということは，その桁数の n と移動する板の番号の n が一致しているので， この m に対しても命題どおりの指定で板が動いたことになる．

　最後に棒 3 に待避してあった n-1 段のハノイの塔を棒 2 に移動する． そのときの手数は 2^n-1 + 1 から 2ⁿ - 1 までである． その手数の 2 進数表現は順に，

　その板の番号を指定する際に， 2 進数を末尾から見ていって 1 が初めて現れるところを探すのだから， 先頭に 1 があろうとなかろうと関係ない． つまり， 2^n-1+1 から 2ⁿ - 1 の値に対しても， 命題が示す方法で， 移動する板が指定できることになる．

　以上を総合して， n 段のハノイの塔に対しても， 命題どおりの指定方法で，板を動かせばよいことが示された． これで帰納法が完結する． ■

　ちなみに，「■」は証明終わりを表す記号である． 昔は“Q.E.D.”と書いていたが， 近年，数学者の間でこの記号を使うことが定着しだしているように思う． 実際，論文の投稿規定の中でこの記号を使うように指示している 数学の専門雑誌も存在している．