수학적 귀납법
수학이야기
2009. 4. 26. 14:29
수학에선 거의 모든 것을 연역(deduction)으로 생각하지만 때로는 귀납(induction)이 필요하다. 그 가운데 대표적인 것이 수학적 귀납법이다. 자연수 `n`과 관련된 명제 `P(n)`을 증명하려고 할 때, 다음 두 가지만 증명하면 된다. 1) `n=1`일 때, 참이다. 2) `n=k`일 때, 참이라고 가정하면 `n=k+1`일 때도 참이다. 1)과 2)에 따라서 모든 자연수일때 명제가 성립한다. 아래 증명을 보자. 세상 모든 사람이 대머리이다를 증명하려고 한다. 다시 말하면 머리카락이 `n`인 사람은 대머리이다를 보이는 것이다. 증명) `n=1`일 때, 머리카락이 하나인 사람은 대머리이다. 머리카락이 `k`인 사람이 대머리이면 머리카락이 하나 더 있는 `k+1`인 사람도 대머리이다. 그러므로 머..