数学的帰納法と具体例による検証
数例で式が合うことと、すべての自然数で成り立つと証明することの違いを学びます。
説明
計算結果が何例か一致すると、その式がいつも成り立つように見えることがあります。しかし、まだ試していない値に反例があるかもしれません。すべての自然数で成り立つと述べるには、有限個の計算だけでは足りません。
このモジュールでは、1からnまでの和を題材にします。まず数例を計算し、最初の数例だけ一致する別の式を作ります。その後、数学的帰納法の「最初の場合」と「次の場合へ進む論証」を説明し、両方が必要な理由を確かめます。論証の部分では、式を読むことが学習の中心です。
11からnまでの和
1+2+…+nの和と、n(n+1)/2を1〜5で比較します。
total = lambda n: sum(range(1, n+1))実際に加算する関数; formula = lambda n: n * (n+1) // 2候補の公式; [(n, total(n), formula(n)) for n in range(1, 6)]最初の5例を比較1、3、6、10、15という結果が一致します。ただし、この計算で確認したのはn=1〜5だけです。
2同じ5例に一致する別の式
候補の公式へ(n−1)(n−2)…(n−5)を足した式を用意します。nが1〜5なら、積のどこかが0です。
import math積を求める関数を使う; impostor = lambda n: formula(n) + math.prod(n-k for k in range(1, 6))1〜5では差が0になる式; [(n, total(n), impostor(n)) for n in range(1, 6)]同じ5例を比較別の式でも最初の5例はすべて一致します。確認済みの値だけを一致させる式はいくらでも作れるため、例の数だけで一般的な正しさは決まりません。
3まだ試していない値の反例
n=6では、追加した積のすべての項が0以外になります。
n = 6次の値; total(n), formula(n), impostor(n)実際の和・公式・別の式, impostor(n) - total(n)別の式の誤差実際の和と公式は21、別の式は141です。差の120は5×4×3×2×1です。最初の5例が一致していても、6番目で外れる式が作れました。
4帰納法の出発点
数学的帰納法では、まず対象範囲の最初の値で主張が成り立つことを示します。ここでは自然数n≥1を対象にするのでn=1です。
total(1)出発点の実際の和, formula(1)出発点の公式どちらも1なので、出発点は成立します。
次に、あるk≥1で1+…+k=k(k+1)/2が成り立つと仮定します。両辺にk+1を加えると、1+…+k+(k+1)=k(k+1)/2+(k+1)=(k+1)(k+2)/2です。これはn=k+1の場合の式です。
n=1の成立と、この「kで成り立てばk+1でも成り立つ」という論証を合わせると、1からすべての自然数へ順に成立が伝わります。
5次の値への式変形を具体例で確認
証明の式変形を、k=5の具体的な数でも確認します。この計算は論証の代わりではなく、式の各項が何を表すかを確認する例です。
k = 5具体例のk; formula(k) + (k+1)前の和に次の整数を加える, (k+1) * (k+2) // 2次の値に対する公式, total(k+1)実際に加算した和どれも21です。前の和15に次の整数6を加える処理と、n=6を公式へ代入する処理が一致しています。一般のkで成立することは、前の説明の式変形で示しています。
6出発点が必要な理由
「n≥2」という主張なら、nで成り立つと仮定すればn+1でも成り立ちます。しかし自然数1からすべてに成り立つ主張ではありません。
[(n, n >= 2対象値と主張の真偽, (not (n >= 2)) or (n+1 >= 2)成立すれば次も成立するか) for n in range(1, 5)1〜4で表示]各行の最後にある「nで成立するなら次でも成立する」はTrueですが、n=1での主張はFalseです。次へ進めることだけでは、最初の成立を保証できません。帰納法では出発点と次への論証の両方を示します。
まとめ
具体例は、式の理解や反例探しに使えます。しかし、何例かが一致しただけでは、すべての自然数での成立を証明したことにはなりません。
数学的帰納法では、対象範囲の最初で成立することと、ある値で成立すれば次の値でも成立することを示します。個々の計算例を確認する方法と、範囲全体を証明する方法の違いを確かめます。
操作履歴と解説を振り返れます。
Python 3
total = lambda n: sum(range(1, n+1)); formula = lambda n: n * (n+1) // 2; [(n, total(n), formula(n)) for n in range(1, 6)][(1, 1, 1), (2, 3, 3), (3, 6, 6), (4, 10, 10), (5, 15, 15)]
import math; impostor = lambda n: formula(n) + math.prod(n-k for k in range(1, 6)); [(n, total(n), impostor(n)) for n in range(1, 6)][(1, 1, 1), (2, 3, 3), (3, 6, 6), (4, 10, 10), (5, 15, 15)]
n = 6; total(n), formula(n), impostor(n), impostor(n) - total(n)(21, 21, 141, 120)
total(1), formula(1)(1, 1)
k = 5; formula(k) + (k+1), (k+1) * (k+2) // 2, total(k+1)(21, 21, 21)
[(n, n >= 2, (not (n >= 2)) or (n+1 >= 2)) for n in range(1, 5)][(1, False, True), (2, True, True), (3, True, True), (4, True, True)]
演習完了