수학적 귀납법

수학적 귀납법

법칙 1

명제 $p(n) (n=1,2,3, \cdots )$ 에 대해 $p(1)$ 이 참이고 $p(n)$ 을 가정했을 때 $p(n+1)$ 이 성립하면 $p(n)$ 은 참이다.

설명

어떤 식이 자연수에 대해 성립할 때 특히 큰 위력을 발휘하는 증명법으로, 페아노 제5공리라고도 불리며 혹은 ‘수학적’이라는 말을 떼고 그냥 귀납법이라고도 한다. 본래 귀납법이란 현상이나 실체를 경험적으로 모아 어떤 결론을 내리는 것인데, 수학에선 이런 풀이가 없기 때문에 그냥 귀납법이라고 해도 어련히 수학적 귀납법이라고 알아듣는다.

수학적 귀납법은 이해하기 전엔 어렵고 이해하면 너무나 쉬운 증명법이다. 페아노 제5공리라는 이명에서도 알 수 있듯이 ‘공리’라고 할 수 있을만큼 당연한 논리기 때문이다.

수학적 귀납법은 흔히 도미노에 많이 비유된다:

$2$ 번째 블럭은 넘어지면서 $3$ 번째 블럭을 넘어뜨린다. 이렇게 모든 블럭들은 그 다음 블럭을 넘어뜨리기 때문에, 블럭이 얼마나 많든 모두 넘어진다.

다시 수학적 귀납법의 이야기로 돌아오자면, $p(1)$ 이 성립할 때 $p(1+1)$, 즉 $p(2)$ 이 성립한다. $p(2)$ 이 성립할 때, $p(2+1)$ 이 성립하고 $p(n)$ 이 성립할 때 $p(n+1)$ 이 성립한다. $p(n)$ 이 성립하는 걸 왜 가정해도 되는지 모르겠다고 하는 사람이 있는데, 실제로 우리가 보이는 것은 $p(n)$ 이 성립하는 걸 가정하는 게 아니라 $p(n)$ 이 성립할 때 $p(n+1)$ 도 성립한다는 것을 보이는 것이다. 만약 그것이 성립한다면, $p(1)$ 이 성립하므로 모든 자연수에 대해 성립한다는 것이 진짜 결론이다.


  1. 이흥천 역, You-Feng Lin. (2011). 집합론(Set Theory: An Intuitive Approach): p63, 367. ↩︎

댓글