15

私は数学が大の苦手なので、見当違いの質問かもしれませんが・・

"プログラマの数学" (ISBN4-7973-2973-4)の中で0からnまでの整数の和は(n * (n + 1)) / 2 に等しいということを証明するために数学的帰納法を使っています

基底の証明G(0)が成り立つことは実際に計算すればわかります

(0 * (0 + 1)) / 2 = 0 //確かに計算すると答えが0になる

この中の帰納の証明の中でG(k) = 0 + 1 + ••• + k = (k * (k + 1)) / 2 が成り立つと仮定して話を進めていますが、
これはあくまでも仮定であり、G(k)が成り立ったからといってG(k+1)が成り立つとは限らないのではないのでしょうか?

G(0)が成り立ったからといってG(1263712)が成り立つことは分からないのではないかと思います

数学的帰納法での証明は実際に正しいかどうかはわからないのでしょうか?

G(k) = 0 + 1 + ••• + k = (k * (k + 1)) / 2

G(k + 1) = 0 + 1 + ••• + k + (k + 1) = ((k + 1) * (k + 1) + 1) / 2

6
  • 8
    質問にクローズ票を投じます。オフトピックである理由: プログラマ向けの本から引っぱってきた話題ではあるものの、ご質問の内容は純粋に数学の帰納法に関するもののように思われます。
    – hata
    Commented 2016年3月1日 18:22
  • 10
    @hata さん、この程度の数学的帰納法の理解は計算量の推定など、プログラマーが知っておいた方が良い様々な事柄で必要になってきます。必ずしもオフトピックとは言えないでしょう。
    – OOPer
    Commented 2016年3月1日 22:54
  • G(k)でG(k+1)を定義していないのだから帰納法になっていないのでは? Commented 2016年3月2日 0:41
  • Wikipeidaの数学的帰納法の項そのまんまですね。 Commented 2016年3月2日 1:03
  • 2
    @Le Pere d'OOさん、帰納法自体が「正しいかどうか」という主旨になっているように思われるからです。帰納法の「使い方」なら実装上関係あると思うので文句はないのですが。
    – hata
    Commented 2016年3月2日 13:43

8 件の回答 8

13

数学的帰納法に限らず、一般に、「Aが成り立つと仮定する。このときBが成り立つ。」という論理 (ちゃんとした言葉を使えば命題) の正しさは、実際にAが成り立つ場合があるかどうかには関係ありません。この命題の意味するところは、「Aが成り立てば、必ずBも成り立つよ。Aが成り立たなかった場合のことは何も言っていない (ので、どうなるかわからない) よ。」ということです。

例えば、とある国で大統領を決める選挙を行うとしましょう。票数は全部で 51 で、過半数の 26票以上取れば、次期大統領に決定です。C氏と T氏が立候補しました。さて選挙当日、非常に接戦で、現時点での開票速報での得票数は C氏が 25、T氏が 24です。このとき「C氏がもう一票取ったとする。このとき C氏が次期大統領である。」という命題は正しいでしょうか。接戦なので、T氏が 2票取る可能性も十分あります。

答えは、この命題は正しい、です。なにしろ、あと一票取れば、確かに合計 26票になるわけですから。T氏が 2票取るようなことになっても、それは、どうなるのか、この命題が何も述べていない事が起きただけのことなのです。

同様に数学的帰納法においても、「G(k)が成り立つと仮定する。このときG(k+1)が成り立つ」の正しさは、実際に G(k)が成り立つ場合があるかどうかには影響されません。

数学的帰納法というのは伝言ゲームみたいなものです。「G(k)が成り立つと仮定する。このときG(k+1)が成り立つ」というのは、伝言の途中で絶対に間違えないことを保証するための証明です。あとは、一番最初に正しいことで伝言を始めれば、正しさが、どこまでも伝わっていくわけです。

6
  • +1。分かりやすいです。ただし、Aが偽のとき「AならばB」自体は真になります。したがって確かに「B」が成り立つかはAが成り立つかどうかには影響されませんが、「AならばB」が成り立つかはAが成り立つかどうかに影響されます。このため正確を期すのであれば部分的に修正が必要です (特に、4段落目)。
    – nekketsuuu
    Commented 2018年8月13日 23:26
  • @nekketsuuu 命題Bの真偽と命題A=>Bの真偽を混同なさっていませんか。
    – Hideki
    Commented 2018年8月18日 14:49
  • Hideki さん、まさにそのことを指摘しています。「「G(k)が成り立つと仮定する。このときG(k+1)が成り立つ」の正しさ」と書くと、「AならばB」の真偽について論じているようにも捉えられ、そうするとG(k)の真偽が関係してしまいます。
    – nekketsuuu
    Commented 2018年8月18日 21:00
  • @nekketsuuu そうすると、ますますわかりません。なぜなら、その部分は、まさしく「AならばB」の真偽について述べている部分だからです。
    – Hideki
    Commented 2018年8月18日 22:08
  • はい、「『AならばB』の真偽はAの真偽に影響されない」と書かれているように読めたので指摘させて頂きました。実際はAの真偽が影響します。いかがでしょうか?
    – nekketsuuu
    Commented 2018年8月18日 22:11
10

G(k)が成り立ったからといってG(k+1)が成り立つとは限らない

G(k)が成り立つことを仮定したのでG(k+1)が成り立つ、のではないです。

「G(k)が成り立つという仮定の下G(k+1)が成り立つことを示す」のは、数学的帰納法の方法として証明者に要求されている1ステップです。

G(k+1)が成り立つことが示せなければ、数学的帰納法による証明はできないということになります。

前提として、ここでのkは具体的な数(5とか1362とか)ではなく、あくまで記号です。なので、G(k)は元の式G(n)のnをkで置き換えただけの式になります。要するに「元の式は正しい」という当たり前のことを言っているに過ぎません(元の式は正しくない、と仮定する背理法という証明法もあるのですが)

「G(k)が成り立つという仮定の下G(k+1)が成り立つ」ことを示すことができ、別にG(1)が成り立つことも証明できれば、「G(1)が成り立つのでG(1+1)すなわちG(2)も成り立つ」と言え、以下同様にG(3)、G(4)、・・・も成り立つことが証明されます。

2

これはあくまでも仮定であり、G(k)が成り立ったからといってG(k+1)が成り立つとは限らないのではないのでしょうか?

その通りです。だからG(k+1)のとき成り立つことを証明しています。

1.G(k)が成り立つならG(k+1)成り立つ
2.G(0)が成り立つ

この2つを証明すると命題が成り立つと証明されます

1

数学的帰納法を用いた証明は通常

  1. 変数(この場合k)が最小の場合(k=0?)に限って実際に成り立つと証明する
  2. kの場合に成り立つと仮定すると、k + 1の場合も成り立つことを示す

という2ステップで構成されています。

問題の証明にも「明らかにG(0)=0」というような最小値での計算が含まれているのではないでしょうか。

1

それにしても帰納法を信用できないとなると

for (int i = 0; i <= 100; i++)
    ;

みたいなループも1~100を正確にカウントできないのではないか、というような疑問も持たれるということなのでしょうか?


あまり意図が伝わらなかったようなのですが、式i++(変数iとインクリメント演算子++)がプログラミングにおける帰納法の原点なのかなと思いました。

  • 変数はiは用途に依らず任意の値を格納できる
  • インクリメント演算子++は変数の値に依らず、その変数の値を1増加させる

これを理解し受け入れることができないとプログラミングにおいて任意のループを記述することができませんし、これを受け入れることができるのであれば数学的帰納法も理解できると思います。

1
  • 1
    再帰の方が良い例だったかもしれませんね。 Commented 2016年3月2日 2:21
1

G(k) = 0 + 1 + ••• + k = (k*(k+1))/2 [式1] が成り立つと仮定します。

そして、この仮定が成り立てば、

G(k+1) = 0 + 1 + ••• + k + (k+1) = ((k+1)*((k+1)+1))/2 が成り立つことを、証明します。

式1の右辺(((k+1) * ((k+1)+1))/2)は、次のように変形できます。

((k+1) * ((k+1)+1))/2
 = ((k+1)(k+1) + (k+1))/2
 = (k
(k+1) + 1*(k+1) + (k+1))/2
 = (k*(k+1))/2 + (k+1)

これを式1に加えるとは、以下のようになります。
G(K+1) = 0 + 1 + ••• + k + (k+1) = ((k+1) * ((k+1)+1))/2 = (k*(k+1))/2 + (k+1)

上の連続等式の2項目と4項目を取り出すと、式2が得られます。
0 + 1 + ••• + k + (k+1) = (k*(k+1))/2 + (k+1) [式2]
0 + 1 + ••• + k     = (k*(k+1))/2       [式1]

式2の左辺から式1の左辺を、式2の右辺から式1の右辺をそれぞれ引くと
(k+1) = (k+1)
が得られます。
この式は左右の辺の式が同じですから、常に成り立ちます。

== 証明おわり ==

これで、G(k)が成り立つなら、G(k+1)が常に成り立つ事を納得いただけたでしょうか?

0

何を仮定すると、何が成立するか、がわかりにくいのが難しさなのかな、と思ったりしました。

参考までに、今回の証明の、展開の関係をなるべく誤解のないように(つまり数学の証明的に)表すとこうなります。

定義.
sum(0..k) := 0 + 1 + ... + k
n ∈ N に対する命題 G(n): sum(0..n) = n * (n+1) / 2

Thm. ∀n ∈ N. G(n)

Proof.
1. sum(0..0) = 0 = 0 * (0 + 1) / 2
2. G(0) が成立
3. ∀k ∈ N が与えられたとする。
   3-1. G(k) が成立したとする。
        3-1-1. sum(0..k) = k * (k + 1) / 2                       (∵ 3-1.)
        3-1-2. sum(0..k+1) = sum(0..k) + k + 1
                           = k * (k + 1) / 2 + k + 1             (∵ 3-1-1.)
                           = k * (k + 1) / 2 + 2 * (k + 1) / 2
                           = (k + 2) * (k + 1) / 2
                           = (k + 1) * (k + 2) / 2
        3-1-3. G(k+1) が成立する。
   3-2. G(k) => G(k+1)      (∵ 3-1 から 3-1-3 が成立するので)
4. ∀k ∈ N. G(k) => G(k+1)   (∵ 3 から 3-2 が成立するので)
5. ∀n ∈ N. G(n)             (∵ 2,4 と数学的帰納法より)
0

ポイントは「G(k)が成り立ったらG(k+1)が成り立つ」ということが成り立つ、ということですね。

ということはG(0)が成り立ったらG(1)が成り立つ。

G(1)が成り立ったらG(2)が成り立つ。

G(2)が成り立ったらG(3)が成り立つ。

これが無限に続けられるので、「G(0)が成り立つ」かつ「G(k)が成り立ったらG(k+1)が成り立つ」が成り立つならば、「すべての自然数kについてG(k)が成り立つ」といえます。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。