수학적 귀납법

수학에선 거의 모든 것을 연역(deduction)으로 생각하지만 때로는 귀납(induction)이 필요하다. 그 가운데 대표적인 것이 수학적 귀납법이다.

자연수 `n`과 관련된 명제 `P(n)`을 증명하려고 할 때, 다음 두 가지만 증명하면 된다.
1) `n=1`일 때, 참이다.
2) `n=k`일 때, 참이라고 가정하면 `n=k+1`일 때도 참이다.
1)과 2)에 따라서 모든 자연수일때 명제가 성립한다.

아래 증명을 보자. 세상 모든 사람이 대머리이다를 증명하려고 한다. 다시 말하면 머리카락이 `n`인 사람은 대머리이다를 보이는 것이다.

증명) `n=1`일 때, 머리카락이 하나인 사람은 대머리이다.
머리카락이 `k`인 사람이 대머리이면 머리카락이 하나 더 있는 `k+1`인 사람도 대머리이다.
그러므로 머리카락이 자연수 `n`개인 모든 사람이 대머리이다. 아무리 머리숱이 많아도 말이다.

어디가 잘못된 것일까?