数学的帰納法

数学的帰納法は、数学でよく使われる証明の方法です。特に、自然数やほかの数列を扱うときによく使われます。

考え方

基本的な考え方は、まず命題を最初の要素について証明することです（第1段階）。自然数の場合、最初の要素はたいてい n = 1 で、代入するだけで証明できます。第2段階では、「n = a のとき命題が成り立つならば、n = a + 1 のときも成り立つ」という含意を証明します。

この2つの段階から、命題が（考えている集合の）すべての n について成り立つことが導かれます。なぜそうなるのでしょうか。最初に、命題が n = 1 のとき成り立つことを証明します。また、命題が n = a のとき成り立つならば、n = a + 1 のときも成り立つこともわかっています。そこで、a = 1 とします。a = 1 のとき命題は成り立つので、a + 1 = 2 のときも成り立ちます。これで、命題が a = 2 のとき成り立つことがわかりました。すると、a + 1 のときも成り立つので、2 + 1 = 3 のときも成り立つはずです。以下同様です。

1つ目の例

1つ目の例は自明なものです。どんな偶数に2を足しても、また偶数になることを証明しましょう。自然数を扱うので、偶数を一般に 2n と書きます。ここで、n は自然数です。n にどんな自然数を代入しても偶数になることは、見ればすぐにわかります。割り切れることは、縦線を使って次のように書きます（高校の教科書には出てきませんが、大学ではよく使う記号です）。

$$2\mid 2n$$

この式は、2が 2n を割り切ることを表します。割り切れることを式で書けるようになったので、数学的帰納法で証明したいことも式で書けます。

$$2\mid 2n+2;n\in \mathbb{N}$$

1つ目の例で証明するのはこの式、つまり2が 2n + 2 を割り切ることです。これは、もとの「どんな偶数に2を足しても、また偶数になる」という命題とぴったり対応しています。

第1段階では、最初の要素、つまり1について証明します。式に n = 1 を代入します。

$$\begin{array}{rcl}2& \mid & 2\cdot 1+2\\ 2& \mid & 4\end{array}$$

2は4を割り切るので、最初の要素については成り立ちます。次は第2段階です。a 番目の要素について成り立つならば、(a + 1) 番目の要素についても成り立つことを証明します。まず、n = a のとき成り立つと仮定します。

$$2\mid 2a+2$$

この式は正しいと仮定して、証明を組み立てるときに使います。ここで証明したいのは、次の式です。

$$2\mid 2(a+1)+2.$$

何をしたのでしょうか。a のところに (a + 1) を書きました。大切なのはかっこで、2a + 1 + 2 と書くのは誤りです。式全体に1を足すのではなく、a を1だけ大きい式 (a + 1) にしているのです。かっこをはずして式を変形します。

$$\begin{array}{rcl}2& \mid & 2(a+1)+2\\ 2& \mid & 2a+2+2\end{array}$$

ここで少し、割り切れることについて寄り道をします。2つの数、例えば p と q が、ある数、例えば r で割り切れるとき、それらの和も r で割り切れます。つまり、次の式が成り立ちます。

$$(r\mid p\wedge r\mid q)\Rightarrow r\mid (p+q)$$

例えば、p = 8、q = 20、r = 4 を代入してみましょう。4は8も20も割り切ります。そして、それらの和 8 + 20 = 28 も割り切ります。

これを今の例にどう使うのでしょうか。右側の式を、次のように p と q の2つに分けます。

$$p=2a+2;q=2$$

q、つまり2は、明らかに2で割り切れます。そして、式 p も2で割り切れます。仮定からそういえるからです。式 p は、正しいと仮定した式とぴったり同じです。p が2で割り切れ、q も2で割り切れるなら、それらの和も2で割り切れます。

もう一度、仮定について確認しましょう。最初に、次の式が成り立つと仮定しました。

$$2\mid 2a+2.$$

そのため、証明を組み立てる途中で式 2a + 2 が出てきたとき、それが2で割り切れるといえたのです。それが仮定だからです。帰納法の仮定をいつ、なぜ使えるのかを理解するところが、ふつう数学的帰納法でいちばんむずかしい部分です。

これで帰納法は終わりです。証明は無事に完了し、命題が成り立つことが示されました。

別の分け方をすれば、仮定を使わなくてもすみます。p = 2n、q = 2 + 2 とします。q = 4 は明らかに2で割り切れます。p = 2n も、2で割ると自然数、つまり整数の n が残るので、2で割り切れます。この場合も、どちらも2で割り切れる2つの式が得られたので、それらの和も2で割り切れます。

どちらの場合も、次のことを証明しました。

1. n = 1 のとき、式が成り立つ。
2. n のとき式が成り立つならば、n + 1 のときも成り立つ。

ここから、次のように導けます。

• n = 1 のとき、式が成り立つことがわかっています。
• n のとき成り立つならば、n + 1、つまり 1 + 1 のときも成り立つはずなので、n = 2 のときも成り立ちます。
• n のとき成り立つならば、n + 1、つまり 2 + 1 のときも成り立つはずなので、n = 3 のときも成り立ちます。
• n のとき成り立つならば、n + 1、つまり 3 + 1 のときも成り立つはずなので、n = 4 のときも成り立ちます。
• n のとき成り立つならば、n + 1、つまり 4 + 1 のときも成り立つはずなので、n = 5 のときも成り立ちます。
• …

2つ目の例

次に、数学的帰納法を使って、簡単な命題を証明しましょう。

$$2^n\geqq 2n;n\in \mathbb{N}.$$

まず第1段階として、n を選ぶ自然数の最初の要素である n = 1 のとき、命題が成り立つかを調べます。

$$\begin{array}{rcl}{2}^1& \geqq & 2\cdot 1\\ 2& \geqq & 2\end{array}$$

これは明らかに成り立ちます。次は第2段階です。n = a のとき成り立つならば、n = a + 1 のときも成り立つかを調べます。仮定は、次の式が成り立つことです。

$$2^a\geqq 2a$$

そして、証明したいのは次の式です。

$$2^{a+1}\geqq 2(a+1)$$

まず、左辺を累乗の計算法則を使って書きかえ、右辺はかっこをはずします。

$$2\cdot 2^a\geqq 2a+2$$

左辺は、かけ算のかわりに足し算で書きます。右辺はそのままです。

$$2^a+2^a\geqq 2a+2$$

ここで仮定を使います。仮定とは、成り立つと仮定した命題のことです。この不等式では、両辺がそれぞれ2つの項の和になっています。また、次のこともわかっています。

$$\begin{array}{rcl}{2}^a& \geqq & 2a\\ 2^a& \geqq & 2.\end{array}$$

1行目は仮定からいえることで、2行目は明らかです（2^a がいちばん小さくなるのは a = 1 のときで、そのとき値は2です）。したがって、左辺の2つの項は、それぞれ右辺の2つの項以上です。これで、式が a のとき成り立つならば (a + 1) のときも成り立つことが帰納法で証明できました。式は1のときも成り立つので、すべての自然数について成り立ちます。

3つ目の例

次の命題を証明してみましょう。

$$3\mid n\Rightarrow 3\mid n^2;n\in \mathbb{N}$$

言葉で言うと、n が3で割り切れるならば、n² も3で割り切れるということです。n が3で割り切れないときは、（含意の定義から）式は自明に成り立つので、n が3で割り切れる場合だけを考えます。すると、自然数の数列 a_i = 3, 6, 9, 12, 15, … が得られます。ここからは、この数列 a_i の中だけで考えます。

帰納法による証明は、第1段階、つまり最初の要素について成り立つかどうかから始めます。今は数列 a_i の中で考えているので、この数列の最初の項、つまり a₁ を選びます。これは3です。3について、式は成り立ちます。

$$3\mid 3\Rightarrow 3\mid 3^2$$

次は第2段階です。数列 a_i は、n を自然数として 3n と書けることがわかります。つまり、2番目の項は1つ前の項より3大きく、以下同様です。ここで、n のとき式が成り立つと仮定し、考えている数列の次の項を表す (n + 3) のときも成り立つことを示さなければなりません。まず、仮定を書きます。

$$3\mid n\Rightarrow 3\mid n^2$$

次に、証明したいことを書きます。

$$3\mid (n+3)\Rightarrow 3\mid (n+3{)}^2.$$

右側のかっこを、公式を使って展開します。

$$3\mid (n+3)\Rightarrow 3\mid n^2+6n+9.$$

もう少しで終わりです。左側の式は確かに3で割り切れます。仮定から n は3で割り切れ（数列 a_i の数だけを考えています）、3も3で割り切れるからです。右側では、まず n² があり、これは仮定から3で割り切れます。実際、n は3で割り切れることがわかっていて、仮定によれば、n が3で割り切れるならば n² も3で割り切れます。

$$3\mid n\Rightarrow 3\mid n^2$$

次は式 6n で、これは明らかに3で割り切れます。分数の約分と考えるとわかりやすいでしょう。

$$\frac{6n}{3}=2n$$

n は何かの自然数なので、積 2n も自然数になります。つまり、3で割ると自然数が得られたので、式 6n は3で割り切れます。最後の9も3で割り切れます。式は最初の要素についても第2段階でも成り立つので、正しいことがわかります。

式に含まれるかっこの個数

最後の例は少し変わっています。単純な式に含まれるかっこの個数がいつも偶数であることを証明してみましょう。数学的帰納法は、自然数とはまったく別の場面でも使えることがわかります。まず、単純な式とは何かを定義しなければなりません。単純な式とは、次のものです。

• 自然数
• p が単純な式のときの (p²)
• p と q が単純な式のときの (p + q)

例えば、12、54、(5 + 6)、(12 + 7)、(6²)、((5 + 6)²) は単純な式です。逆に、次のものは単純な式ではありません。

• 1 + 2 → 外側のかっこがない
• (1 + 2 → 右のかっこがない
• 13² → 外側のかっこがない
• (1 + 2 + 3) → かっこが足りない。正しくは (1 + (2 + 3)) と書く

単純な式は、例えば次のようにしてつくれます。はじめに単純な式 (a + b) を選びます。ここで、a に単純な式 a = (c + d) を代入すると ((c + d) + b) になり、b に3を代入すると ((c + d) + 3) になります。c に10を代入すると ((10 + d) + 3)、最後に d に (5²) を代入すると ((10 + (5²)) + 3) になります。かっこをきちんと守ることが大切で、そうしないとうまくいきません。

では、単純な式には偶数個のかっこが含まれることを証明しましょう（0も偶数です）。

第1段階では、最初の要素を選びます。この場合、最初の要素はいちばん単純な式、つまり任意の自然数です。そこで、次のようにおきます。

$$j=n;n\in \mathbb{N}.$$

式 j に含まれるかっこの個数は0なので、最初の要素は条件を満たします。第2段階では、2つの単純な式 p と q があり、どちらも偶数個のかっこを含むと仮定します。そして、単純な式 (p + q) と (p²) も偶数個のかっこを含むことを証明します。

まず足し算です。式 q に含まれるかっこの個数を z(q) で表すことにします。すると、式 (p + q) のかっこの個数は z(p) + z(q) + 2 です。つまり、式 p と q のかっこの個数の和より2個多くなります。仮定から z(p) と z(q) はどちらも偶数なので、3つの偶数を足すと、また偶数になります。この場合、命題は成り立ちます。

次は累乗です。この場合も、単純な式 p は偶数個のかっこを含むと仮定します。すると、式 (p²) は z(p) + 2 個のかっこを含みます。つまり、やはり式 p より2個多くなります。この場合も偶数どうしを足すので、結果は偶数です。

命題は最初の要素について成り立ち、第2段階でも成り立つので、正しいことがわかります。