数学的帰納法

自然数に関する命題 P(n) が全ての自然数 n に対して成り立っている事を証明するための、次のような証明手法

基底: P(1) が成り立つ事を示す。
帰納法: 任意の自然数 k に対して、「P(k) ⇒ P(k + 1)」が成り立つ事を示す。
演繹法: 以上の議論から任意の自然数 n について P(n) が成り立つ事を結論づける。

※ 帰納法でも最後は演繹法を使っている

プログラムでの例

命題: 0からnまでの和は$\frac{n\times (n+1)}{2} = \sum_{i=0}^n n_i$

def sum(n):
    if n == 0: # 基底
        return n
    return n + sum(n-1) # 帰納

検算

>>> n = 100
>>> sum(n) == (n * (n+1))/2
True

references:

https://ja.wikipedia.org/wiki/%E6%95%B0%E5%AD%A6%E7%9A%84%E5%B8%B0%E7%B4%8D%E6%B3%95