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

  • このエントリーをはてなブックマークに追加
  • Pocket

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

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

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

今回、0 以上のすべての整数についての主張を作ることができる証明方法「数学的帰納法」について解説します。

【問題1】貯金箱の金額

  • 1 日目、貯金箱に 1 円を入れます
    • 貯金箱は 1 円
  • 2 日目、貯金箱に 2 円を入れます
    • 貯金箱は 1 + 2 = 3 円
  • 3 日目、貯金箱に 3 円を入れます
    • 貯金箱は 1 + 2 + 3 = 6 円
  • 4 日目、貯金箱に 4 円を入れます
    • 貯金箱は 1 + 2 + 3 + 4 = 10 円

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

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

答え

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

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

((1 + 100) + (2 + 99) + (3 + 98) + (4 + 97) + ... (97 + 4) + (98 + 3) + (99 + 2) + (100 + 1)) / 2
このようにまとめると 101 が 100 個ならんで、最後に 2 で割るだけの計算になります。

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

数式を一般化する

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

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

この数式をさらに一般化すると「0 から n までの和は ((n * (n + 1)) / 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(0)
    • 0 * 2 = 0 で偶数
    • A(0) は真
  • A(1)
    • 1 * 2 = 2 で偶数
    • A(1) は真

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

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

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

  • B(1)
    • 1 * 3 = 0 で奇数
    • B(1) は真
  • B(2)
    • 2 * 3 = 6 で偶数
    • B(2) は

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

そのほかの例
  • 主張C(n): n + 1 は 0 以上の整数である
    • 0 以上のすべての整数について真だと言える
  • 主張D(n): n – 1 は 0 以上の整数である
    • D(0) のときになる
    • 0 以上のすべての整数について真だと言えない
  • 主張E(n): n * 2 は 0 以上の整数である
    • 0 以上のすべての整数について真だと言える
  • 主張F(n): n / 2 は 0 以上の整数である
    • F(奇数) のとき整数にならないのでになる
    • 0 以上のすべての整数について真だと言えない

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

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

  • 主張G(n): 0 から n までの和は (n * (n + 1)) / 2 に等しい

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

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

数学的帰納法とは

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

数学的帰納法は「基底」と「帰納」の 2 STEP で証明を行います。

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

基底とは (base)

P(n) において、P(0) を証明すること。

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

帰納とは (induction)

P(n) において、0 以上の整数 k で P(k) が成り立つ場合、
P(k + 1) も成り立つことを証明すること。

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

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

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

STEP1 基底で 0 番目である最初のドミノが倒れることを保証する。
STEP2 帰納で k 番目のドミノが倒れたならば、k + 1 番目のドミノが倒れることを保証する。

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

  1. 主張P(0) が成り立つ
    • 基底で P(0) が証明される
  2. 主張P(1) が成り立つ
    • 前回の基底で P(0) が証明されている、かつ
    • 今回の帰納で k = 0 の場合 P(0 + 1) が証明される
  3. 主張P(2) が成り立つ
    • 前回の帰納で P(1) が証明されている、かつ
    • 今回の帰納で k = 1 の場合 P(1 + 1) が証明される

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

最後のドミノはいつか必ず倒れますが、数学の証明では「かかる時間は無視」されます。
プログラミングでは処理時間は大事なので、そこは大きな相違点ですね。

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

  • 主張G(n): 0 から n までの和は (n * (n + 1)) / 2 に等しい

基底

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

  • 主張G(0): 0 から 0 までの和は (0 * (0 + 1)) / 2 に等しい

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

帰納

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

  • 主張G(k): 0 から k までの和は (k * (k + 1)) / 2 に等しい
    • これが仮定する式
  • 主張G(k + 1): 0 から (k + 1) までの和は ((k + 1) * ((k + 1) + 1)) / 2 に等しい
    • これが証明したい式

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

つまり 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 について成り立つことを証明してください。

  • 主張Q(n): 1 + 3 + 5 + 7 … + (2 * n – 1) = n^2
    • 主張Q(1):1 = 1^2
    • 主張Q(2):1 + 3 = 2^2
    • 主張Q(3):1 + 3 + 5 = 3^2
    • 主張Q(4):1 + 3 + 5 + 7 = 4^2
    • 主張Q(5):1 + 3 + 5 + 7 + 9 = 5^2

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

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

基底

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

この場合 Q(0) ではなく、Q(1) で基底の証明を行えば数学的帰納法を使用できます。

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

帰納

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

  • 主張Q(k): 1 + 3 + 5 + 7 … + (2 * k – 1) = k^2
    • これが仮定する式
  • 主張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) が「左辺」で、
(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】オセロの石の色

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

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

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

誤った数学的帰納法

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

  • 主張T(n): n 個のオセロを投げたとき、すべてのオセロが必ず同じ色になる

基底

  • 主張T(1): 1 個のオセロを投げたとき、すべてのオセロが必ず同じ色になる

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

帰納

  • 主張T(k): k 個のオセロを投げたとき、すべてのオセロが必ず同じ色になる
    • これが仮定する式
  • 主張T(k + 1): k + 1 個のオセロを投げたとき、すべてのオセロが必ず同じ色になる
    • これが証明したい式

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

○ … ○
【図1】k + 1 個のオセロ

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

○ …
【図2】グループ A (先頭から数えた k 個)

… ○
【図3】グループ B (末尾から数えた k 個)

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

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

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

k = 1 のとき

○ ●

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

  • グループ A が先頭のオセロだけ (1個)
  • グループ B が末尾のオセロだけ (1個)
  • 共有するオセロなし (0 個)
    • ※ 共有するオセロの数は 1 – 1 で 0 個

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");
}
  • prove(0) を実行すると、主張P(0) の証明を出力します
  • prove(1) を実行すると、主張P(1) の証明を出力します
  • prove(2) を実行すると、主張P(2) の証明を出力します

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

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

いいえ、証明したいのは P(k) ではなく P(n) です。

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(n): 配列 array の最初の n 個の要素の和は、変数 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 シリーズ

次回

前回

お仕事ください!

僕が代表を務める 株式会社 EeeeG では Web 制作・システム開発・マーケティング相談を行っています。
なにかお困りごとがあれば、Twitter DM や Web サイトからお気軽にご相談ください。

コメント

コメントを残す

*