「バラモンの塔」とも言うそうです。ｎ枚の大きさが違うメダルがあります。図のように大きいメダルの上に小さいメダルが重ねられています。このメダルの塔を、今あるAからCへ移します。その際には
①1回に動かせるのはメダル1枚
②小さなメダルの上に大きなメダルを乗せてはいけない
というルールを守らなければなりません。1枚動かすのを1手と数えることにするとき、何手で移し終えるでしょうか。64枚のメダルの塔を移し終えたとき、世界が終わるという伝説があるそうな……。
ｎ枚を移すのに必要な手数をｆ(ｎ)と表すとき、
であることを数学的帰納法で示します。
（第１段階）
ｎ＝１のとき、ｆ(１)＝１なので、確かに成立しています。
（第２段階）
ｎ＝ｋのとき、必要な手数は
であると仮定しましょう。メダルがｋ＋１枚のとき何手かかるか考えます。ｋ枚をＢに移すのにｆ(ｋ)手かかります（下の図）。
ここからＡにある１枚をＣに移すのに１手かかります（下の図）。
Ｂにあるｋ枚をＣに移すのにｆ(ｋ)手かかります（下の図）。
すると結局、ｋ＋１枚のときにはｆ(ｋ＋１)＝ｆ(ｋ)＋１＋ｆ(ｋ)＝２ｆ(ｋ)＋１手かかります。つまり
となり、証明されました。
紙を切って（つまみやすく）３枚くらいで実際にあれこれ動かすと何をどうすればよいのかよく分かります。自分で実験してみることです。数列の知識を使っても解けます。ｆ(ｎ＋１)＝２ｆ(ｎ)＋１なのですから、教科書の例題に出てくるあの漸化式の問題です！
まあこれでいいんですが……。違和感はありませんか？ これでいいんでしょうか？ ここまでで示せたことは「ｆ(ｎ)手で塔を他の場所に移せる」という事実です。これ自体は正しいけれど、「これがどうしても必要な手数である」ということはまだ示していません。つまり、もっと短い手数で移動できるかどうか、何も考えていないのです。この手順を見てみるとどうも他にもっと短い手数の方法などなさそうな気はします。でも断言はできません。……というわけでご存じの方、教えて下さい……。
