【応用】2つ前までさかのぼる数学的帰納法

ここでは、2つ前までさかのぼる数学的帰納法を見ていきます。 $n=k,k+1$ の2つを仮定して示すケースです。

【広告】

1つ前だけではダメな数学的帰納法

例題
$a+b$, $ab$ が整数のとき、自然数 n に対して $a^n+b^n$ も整数になることを示しなさい。

この例題を数学的帰納法で考えてみましょう。

ステップ1の $n=1$ の場合は明らかです。ステップ2では「 $a^k+b^k$ が整数なら $a^{k+1}+b^{k+1}$ も整数」を示せばいいですね。 $a^k+b^k$ に $a+b$ を掛ければ、 $a^{k+1}$, $b^{k+1}$ が出てくるので、このことを利用して変形してみましょう。
\begin{eqnarray}
& &
a^{k+1}+b^{k+1} \\[5pt] &=&
(a^k+b^k)(a+b)-ba^k-ab^k \\[5pt] &=&
(a^k+b^k)(a+b)-ab(a^{k-1}+b^{k-1}) \\[5pt] \end{eqnarray}となります。ここで、 $a^k+b^k$ は数学的帰納法の仮定から整数であることがわかります。また、 $a+b$ と $ab$ も整数であることは仮定からわかります。しかし、 $a^{k-1}+b^{k-1}$ がやっかいです。これが整数であるかどうかはわかりません。

$a^{k+1}+b^{k+1}$ が整数であることは、 $a^k+b^k$ が整数であることだけでなく、 $a^{k-1}+b^{k-1}$ も整数であることも使えば、示すことができます。

このように、 $n=k+1$ の1つ前「 $n=k$ の場合」だけでなく、2つ前の「 $n=k-1$ の場合」も仮定で使いたい場合があります。その場合は、次のようにやります。

  • $n=1,2$ の場合に成り立つことを示す
  • $n=k,k+1$ の場合に成り立つとすると、 $n=k+2$ の場合にも成り立つことを示す

こういうステップになります。まず、ステップ1で、 $n=1,2$ の場合に成り立つことがわかります。これらと、ステップ2で $k=1$ としたものを使えば、 $n=3$ のときにも成り立つことがわかります。 $n=2,3$ の場合とステップ2から、 $n=4$ も成り立つことがわかります。少し変形したドミノ倒しになりますが、これでもすべての自然数について成り立つことが言えます。
\begin{eqnarray}
& & 1,2 \to 3 \\[5pt] & & 2,3 \to 4 \\[5pt] & & 3,4 \to 5 \\[5pt] & & 4,5 \to 6 \\[5pt] & & \quad \vdots \\[5pt] \end{eqnarray}

2つ前までさかのぼる数学的帰納法

上の内容を踏まえて示してみましょう。

(i) $n=1$ のときは、仮定より $a+b$ は整数です。 $n=2$ のときは
\begin{eqnarray}
a^2+b^2
&=&
(a+b)^2-2ab
\end{eqnarray}となり、 $a+b,ab$ が整数なので、 $a^2+b^2$ は整数となります。よって、 $n=1,2$ のときには、 $a^n+b^n$ は整数になります。

(ii) $n=k,k+1$ のときに $a^n+b^n$ が整数になるとします。このとき $n=k+2$ のときも $a^n+b^n$ が整数になることを示します。
\begin{eqnarray}
& &
a^{k+2}+b^{k+2} \\[5pt] &=&
(a^{k+1}+b^{k+1})(a+b)-ba^{k+1}-ab^{k+1} \\[5pt] &=&
(a^{k+1}+b^{k+1})(a+b)-ab(a^k+b^k) \\[5pt] \end{eqnarray}となります。仮定より最後の式は整数だから、 $n=k+2$ のときも $a^n+b^n$ が整数になることがわかります。

(i)(ii)より、数学的帰納法から、自然数 n に対して $a^n+b^n$ が整数になることが示せました。

2つ前までさかのぼるのはどういうときか

2つ前までさかのぼって数学的帰納法を使う方法を見ましたが、どういうときに2つ前までさかのぼるのでしょうか。

それは、上の問題を見てもわかる通り、ステップ2を示すときに、どのような仮定を使いたいかによって変わってきます。2つ目のステップで、「1つ前だけ」で示せるなら普通の数学的帰納法で大丈夫ですが、「2つ前まで」の仮定があれば示せそうだ、ということであれば、「2つ前までを仮定する」必要が出てきます。

つまり、ステップ2の途中で気づくことになります。そのため、ステップ2で方針を立ててから解答を書き始める必要があります。

おわりに

ここでは、2つ前までさかのぼる数学的帰納法について見てきました。2つ目のステップの途中で、「1つ前だけでなく2つ前も仮定したい」場合には、この「2つ前までさかのぼる数学的帰納法」を使うことになります。出くわす頻度は少ないですが、出会ったときにはステップ2を示す途中で気づくでしょう。