【基底】数学的帰納法とは？無数の主張を証明する方法を解説【帰納】

こんにちは。タクマ™ [@suwaru_blog] です。

プログラミングでループ処理を作るとき、
インクリメントされていく 0 以上の整数を使った処理が常に「真」になるか？

それを数式で証明することはできますか？

【問題1】貯金箱の金額

このように貯金をしていくと 100 日目の貯金はいくらになるでしょうか？
単純に足し算していく場合、意外と大変かもしれません。

これを簡単に計算する方法をご紹介します。

答え

昇順で 1 + 2 + 3 + 4 ... 97 + 98 + 99 + 100 と計算しても、
降順で 100 + 99 + 98 + 97 ... 4 + 3 + 2 + 1 と計算しても結果は同じです。

なので (昇順の計算結果 + 降順の計算結果) / 2 の計算結果も同じになるはずです。

答えは 5050 円ですが、当時 9 才の数学者ガウスは似た問題をこの公式で解いたらしいです。

数式を一般化する

1 から 100 までの和を簡単に計算するには、
1 と 100 の両端を足して、100 倍して、最後に 2 で割ればよい、という考え方をしました。

それを数式にすると ((100 + 1) * 100) / 2 となります。

0 以上の整数についての主張

((n + 1) * n) / 2 という公式は本当にどんな整数 n でも成り立つでしょうか？

そのためには整数 n が 0, 1, 2 … と変化するごとに「真」か「偽」の判定ができないといけません。
そんな真偽判定が可能な主張は「 0 以上の整数についての主張」といいます。

((n + 1) * n) / 2 という主張が正しいか証明する前に、
「 0 以上の整数についての主張」がどういうものか説明します。

例

主張A(n): n * 2 は偶数である

「主張A(n): n * 2 は偶数である」が成り立つか、検証してみます。

主張A(n) は「 0 以上のすべての整数について真」だと言える。

主張B(n): n * 3 は奇数である

「主張B(n): n * 3 は奇数である」が成り立つか、検証してみます。

主張B(n) は「 0 以上のすべての整数について真」だと言えない。
このときの B(2) は主張をくつがえす「反例」と言います。

そのほかの例

ガウス少年の主張は真になるのか？

さて「 0 以上の整数についての主張」がわかったところで、話をもとに戻します。
ガウス少年の主張は以下の公式でした。

実際、整数は無数にあるので 0 以上のすべての整数が常に真になるのか？
…を、整数ひとつずつ例にとって証明をするのは大変です。

ですが、ここで「数学的帰納法」という証明方法を使えば、
0 以上のすべての整数についての主張を作ることができます。

数学的帰納法とは

0 以上のすべての整数 n について証明することを「数学的帰納法」といいます。
これを使うと「無数の証明」が可能です。

たとえば「 0 以上のすべての整数 n について主張P(n) が成り立つ」を数学的帰納法で証明します。

基底とは (base)

これが「基底」の証明です。

帰納とは (induction)

これが「帰納」の証明です。

なぜ「基底」と「帰納」で無数の証明が可能なのか

数学的帰納法では「ドミノ倒し」のような証明が繰り返されます。

…というイメージです。具体的にいいますと、

…という感じで、たとえ n = 10000000000 みたいな大きな数字が選ばれても、
そこまでループ計算されて証明される作りになっています。

ガウス少年の主張を数学的帰納法で証明する

基底

G(0) の証明を行います。

答えは 0 で「真」になったので、基底の証明が完了しました。

帰納

0 以上のどんな整数 k を選んでも、
G(k) が成り立つならば、G(k + 1) も成り立つことを証明します。

これを証明するには「左辺と右辺の一致」を証明できればよいです。

つまり 0 から (k + 1) までの和が「左辺」で、
((k + 1) * ((k + 1) + 1)) / 2 が「右辺」となります。

左辺

0 + 1 + 2 + ... + k + (k + 1) が 0 から (k + 1) までの和のことですが、
主張G(k) は成り立つ前提なので、
(K * (k + 1) / 2) + (k + 1) に書き換えることができます。

これをまとめると ((K + 1) * (k + 2)) / 2 になります。

右辺

((k + 1) * ((k + 1) + 1)) / 2 をまとめると、
((K + 1) * (k + 2)) / 2 になります。

左辺と右辺が一緒で「真」になったので、帰納の証明が完了しました。

これで基底と帰納を証明できたので、
数学的帰納法により主張G(n)が成り立つことを証明できました。

【問題2】奇数の和

次の主張Q(n)が、1 以上のすべての整数 n について成り立つことを証明してください。

n 個の奇数を小さい方から並べると n * n の平方数 (n^2) になるという主張です。

奇数の和の主張を数学的帰納法で証明する

基底

今回は「 0 以上のすべての整数…」ではなく、
「 1 以上のすべての整数 n について成り立つことを証明」となっています。

Q(1):1 = 1^2 は「真」になるので、基底の証明は完了しました。

帰納

0 以上のどんな整数 k を選んでも、
Q(k) が成り立つならば、Q(k + 1) も成り立つことを証明します。

これを証明するには「左辺と右辺の一致」を証明できればよかったですね。

1 + 3 + 5 + 7 … + (2 * k - 1) + (2 * (k + 1) - 1) が「左辺」で、
(k + 1)^2 が「右辺」となります。

左辺

1 + 3 + 5 + 7 ... + (2 * k - 1) + (2 * (k + 1) - 1) ですが、主張Q(k) は成り立つ前提なので、
K^2 + (2 * (k + 1) - 1) に書き換えることができます。

これをまとめると K^2 + 2 * K + 1 になります。

左辺

(k + 1)^2 をまとめると、K^2 + 2 * K + 1 になります。

左辺と右辺が一緒で「真」になったので帰納の証明が完了しました。

これで基底と帰納を証明できたので、
数学的帰納法により主張Q(n)が成り立つことを証明できました。

【問題3】オセロの石の色

オセロの表裏は「白と黒」です。

なのでオセロを投げると白か黒になるわけですが、
誤った数学的帰納法を使うと、何回投げても同じ色になることを証明できてしまいます。

もちろんそんなことは起こりえません。

誤った数学的帰納法

下記の主張を、数式を使わない数学的帰納法で証明しようと思います。

基底

オセロが 1 つしかなければ、色も 1 種類しかないので「真」になります。

帰納

帰納は図をつかって考えてみましょう。

【図1】を「k + 1 個」のオセロと見た場合、k 個の 2 グループにわけてみます。

主張T(k) は成立する前提、かつグループ AB のオセロはそれぞれ k 個なので同じ色になります。

図の … はグループ AB で共有されているオセロです。
個数は k + 1 個から先頭・末尾のオセロを除外するので k – 1 個あることになります。

グループ AB は同じ色であり、先頭と末尾以外のオセロは共有されているので「真」になります。

k = 1 のとき

ただし、主張T(k + 1) は k = 1 の場合「真」になりません。

AB グループ間で共有するオセロはないので、色が保証されず「偽」になります。
このように図だけで数学的帰納法を考える場合、間違いやすいので注意が必要です。

プログラムで数学的帰納法を表現する

基底・帰納の証明さえ出来ていれば、関数を呼び出すだけで簡単に結果を出力できます。

// p(0) から P(n) まで証明を行う
void prove(int n) {
    int k;

    printf("いまから、P(%d)が成り立つことを証明します。\n", n);

    /*
     * 基底
     */

    k = 0;
    printf("基底より、P(%d)が成り立ちます。\n", k);

    /*
     * 帰納
     */

    // k を 1 ずつ増やして、帰納を繰り返す
    while (k < n) {
        printf("帰納より「P(%d)が成り立つならばP(%d)も成り立つ」といえます。\n", k, k + 1);
        printf("したがって「P(%d)が成り立つ」といえます。\n", k + 1);
        k = k + 1;
    }

    printf("以上で、証明が終わりました。\n");
}

引数 n が証明したい値であり、k はあくまでローカル変数である点に注意しましょう。

そもそも、帰納で「P(k)が成り立つこと」を決め打ちすることに違和感があったかもしれません。
その k をいまから証明したいのではないか？…と。

k と n の値が一致する瞬間はありますが、k は証明のために一時的に使われるローカル変数です。

ループ不変条件とは

ループ不変条件は数学的帰納法で証明する「主張」に相当します。

例

たとえば「配列要素の和を返却する」だけの関数があったとします。

// array[0] から array[size - 1] までの和を返却
int sum(int array[], int size) {
    int k = 0;
    int s = 0;
    while (k < size) {
        s = s + array[k];
        k = k + 1;
    }
    return s;
}

この関数に主張(ループ不変条件)をつけるなら、以下になります。

ループ不変条件 M(k) が成立するように、ローカル変数 k を 0 から size まで増幅させています。

// size が n にあたる
int sum(int array[], int size) {
    int k = 0;
    // M(0) が成り立つように s を初期化しておく
    int s = 0;
    while (k < size) {
        // M(k) が成り立つ前提
        s = s + array[k];
        // M(k + 1) の準備
        k = k + 1;
        // このタイミングで M(k) が成立
    }
    // M(size)
    return s;
}

まとめ

CS シリーズ

次回

前回