ハノイの塔問題（３）の解答例を示します。
問題（３）の解
（Ａ）nの値が1の場合。
左辺に、n=1として代入し、計算すると、その値は 1 になる。
同様に、右辺に、n=1として代入し、計算するとその値が 1 になる。
したがって、nの値が1のとき、左辺の値と右辺の値が等しくなり、
命題は正しい。
（Ｂ）nの値がkのとき命題が正しいと仮定する。
つまり、n=kとし、
が成り立つ。
つぎに、nの値がk+1のときも命題が成り立つことを示す。
となる。すなわち、nの値が k+1のときも命題は正しい。
（Ａ）,（Ｂ）より、命題が証明された。
