数学的帰納法
自然数に関する命題 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