22724


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

"プログラマの数学" (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`


CC BY-SA 3.0
2016-03-01T14:23:06.110
22709
2018-11-30T16:42:38.630
2016-03-02T12:51:38.613
5246
5246
question
数学
数学的帰納法での証明は実際に正しいかどうかはわからない?


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

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

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

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


CC BY-SA 3.0
2016-03-01T14:49:44.050
22710
2016-03-01T14:49:44.050
5750
22709
answer


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

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

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

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


CC BY-SA 3.0
2016-03-02T00:45:24.580
22717
2016-03-02T00:45:24.580
7256
22709
answer


> 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)、･･･も成り立つことが証明されます。


CC BY-SA 3.0
2016-03-02T01:19:22.743
22719
2016-03-02T01:19:22.743
5793
22709
answer


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

[code]

    for (int i = 0; i <= 100; i++)
        ;
    
[/code]

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

* * *

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

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

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


CC BY-SA 3.0
2016-03-02T01:44:20.947
22720
2016-03-02T04:48:54.247
2016-03-02T04:48:54.247
4236
4236
22709
answer


数学的帰納法に限らず、一般に、「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)が成り立つ」というのは、伝言の途中で絶対に間違えないことを保証するための証明です。あとは、一番最初に正しいことで伝言を始めれば、正しさが、どこまでも伝わっていくわけです。


CC BY-SA 3.0
2016-03-02T02:55:11.663
22724
2016-03-02T02:55:11.663
3605
22709
answer


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)

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

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

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

＝＝ 証明おわり ＝＝

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


CC BY-SA 3.0
2016-03-04T05:00:27.187
22789
2016-03-04T05:00:27.187
217
22709
answer


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

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

[code]

    定義.
    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 と数学的帰納法より)
    
[/code]


CC BY-SA 4.0
2018-08-13T17:07:12.813
47495
2018-08-13T17:07:12.813
754
22709
answer


ポイントは「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)が成り立つ」といえます。


CC BY-SA 4.0
2018-11-30T16:42:38.630
50794
2018-11-30T16:42:38.630
31226
22709
answer