数学的帰納法 — 原理・手順・例題

数学的帰納法は、ある出発点以降のすべての整数について命題が真であることを示す証明方法です。すべての $n \ge n_0$ について主張を証明するには、最初のケースが真であることを示し、さらにある整数で真なら次の整数でも真になることを示します。

この2つがどちらも正しければ、その命題は述べた範囲のすべての整数で成り立ちます。これが数学的帰納法の基本的な考え方です。

数学的帰納法の仕組み

命題を $P(n)$ と書きます。すると、帰納法は次の形になります。

1. 基底部を証明する：$P(n_0)$ が真であることを示す。
2. 帰納段階を証明する：任意の整数 $k \ge n_0$ について $P(k)$ が真だとすると、$P(k+1)$ も真であることを示す。

この2つができれば、すべての整数 $n \ge n_0$ について $P(n)$ が真であると結論できます。

この論理は順番につながっています。基底部が連鎖の出発点になり、帰納段階がその連鎖を1つずつ先へ進めます。

なぜ基底部と帰納段階の両方が必要なのか

基底部は、最初の真の命題を与えます。帰納段階は、その真がある整数から次の整数へ受け継がれることを示します。

したがって、$P(n_0)$ が真なら、$P(n_0 + 1)$ も真です。すると $P(n_0 + 2)$ も真になり、以下同様に続きます。帰納法では出発点を飛ばすことも、あるケースから次のケースへのつながりを飛ばすこともできません。

計算例：和の公式を帰納法で証明する

標準的な例として、次の公式があります。

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

これはすべての整数 $n \ge 1$ について成り立ちます。

次のようにおきます。

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

基底部

$n = 1$ とします。左辺は $1$ で、右辺は

$$\frac{1(1+1)}{2} = 1$$

です。したがって $P(1)$ は真です。

帰納段階

ある任意の整数 $k \ge 1$ について、$P(k)$ が真であると仮定します。つまり、

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

が成り立つとします。

次に $P(k+1)$ を証明します。$k+1$ のときの左辺から始めると、

$$1 + 2 + 3 + \cdots + k + (k+1)$$

となります。

帰納法の仮定を使うと、

$$\frac{k(k+1)}{2} + (k+1)$$

です。

ここで $(k+1)$ をくくり出すと、

$$(k+1)\left(\frac{k}{2} + 1\right)$$

となります。

さらに整理すると、

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

です。

これはちょうど $n = k+1$ のときの公式そのものです。したがって $P(k+1)$ は真です。

以上より、基底部と帰納段階の両方が証明されたので、この公式はすべての整数 $n \ge 1$ について成り立ちます。

数学的帰納法を使う場面

帰納法は、命題が整数のパラメータに依存していて、各場合が自然に前のものとつながるときに有効です。これは和、整除性、不等式、漸化式、アルゴリズムの証明などでよく現れます。

まず、正しい開始値を見極めます。$n = 0$ から始まる主張もあれば、$n = 1$ から始まるものもあり、もっと大きい整数でしか意味をもたないものもあります。

次に、どのケースへ進めばよいかを確認します。通常は $k$ から $k+1$ へのステップですが、命題が偶数についてだけ述べられているなら、$k$ から $k+2$ へのステップが適切な場合もあります。

帰納法の証明でよくあるミス

基底部しか証明していない

基底部で確かめられるのは最初の値だけです。それだけでは、その後の整数について命題が成り立つことは示せません。

開始値を間違える

主張がすべての $n \ge 2$ についてのものなら、$P(1)$ だけを証明しても役に立ちません。基底部は、実際の主張の範囲と一致していなければなりません。

帰納法の仮定を雑に扱う

帰納段階では、適切な範囲にある任意の1つの整数 $k$ について $P(k)$ を仮定します。定理全体がすでに証明されたと仮定してよいわけではありません。

間違った次のケースを証明する

定理に $k \to k+1$ のステップが必要なのに、別のステップを示しただけでは不十分です。その別のステップで十分である理由を説明しない限り、証明は完成しません。

便利な拡張：強い帰納法

$P(k+1)$ を証明するのに、$P(k)$ だけでは足りないことがあります。そのような場合、強い帰納法では $k$ までのすべての前のケースを仮定して、次のケースを証明できます。

考え方は非常に近いですが、仮定がより強くなります。たとえば、ある数をより小さい部分に分けて考える必要がある証明で役立ちます。

自分でもやってみよう

次の主張を考えてみましょう。

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

これを、基底部を先に、その後で $k$ から $k+1$ へのステップを示すという同じ構成で、すべての整数 $n \ge 1$ について証明してみてください。その証明をすっきり書ければ、数学的帰納法の感覚がつかめているはずです。