수학적 귀납법

개요

도미노를 일렬로 늘어세운 후 처음 세운 도미노를 넘어뜨린다고 가정하자. 만약 처음 세운 도미노가 쓰러지면서 다음 도미노를 넘어뜨린다면 그 다음, 다음다음의 도미노도 차례차례 넘어지지 않을까?

수학적 귀납법(Mathematical induction)은 일반화된 명제의 증명 방법으로, 귀납법이란 이름을 달고 있지만 사실은 연역법이다. 고등학교 교육과정에선 수학적 귀납법의 원리를 이해할 수 있을 정도로 간단히 다루지만 대학교에서 수학 관련 전공에 진입하면 증명까지 다루게 된다.

진술

자연수의 집합이 정의역인 조건을 [math]\displaystyle{ P(n) }[/math]이라고 하자. 만약

• [math]\displaystyle{ P(0) }[/math]이 참이다.
• 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ P(n) }[/math]이 참이면 [math]\displaystyle{ P(n+1) }[/math]도 참이다.

이면 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ P(n) }[/math]은 참이다.

명제를 형식적으로 나타내면 다음과 같다.

[math]\displaystyle{ P(0) \land \forall (k\in \mathbb{N})[P(k)\Rightarrow P(k+1)]\Rightarrow \forall (n\in \mathbb{N})P(n) }[/math]

증명

[math]\displaystyle{ n'\in \mathbb{N} }[/math]이 존재하여 [math]\displaystyle{ P(n') }[/math]이 거짓이라고 가정하자. 그리고 집합 S를 다음과 같이 정의하자.

[math]\displaystyle{ S=\{n\in \mathbb{N}\vert \neg P(n)\} }[/math]

그러면 [math]\displaystyle{ \neg P(n') }[/math]이 참이므로 [math]\displaystyle{ n'\in S }[/math]이다. 따라서 S는 공집합이 아니고 [math]\displaystyle{ \mathbb{N} }[/math]의 부분집합이므로, 정렬순서공리에 의해 S의 최소원소가 존재한다. 이 원소를 [math]\displaystyle{ n_0 }[/math]라고 하자. 이때 [math]\displaystyle{ P(0) }[/math]은 참이므로, [math]\displaystyle{ n_0\ne 0 }[/math]이고 따라서 [math]\displaystyle{ n_0 \ge 1 }[/math]이다. 그러면 [math]\displaystyle{ n_0 -1 \ge 0 }[/math]인데, [math]\displaystyle{ n_0-1 }[/math]은 S의 최소원소가 아니므로 [math]\displaystyle{ n_0 -1\not\in S }[/math]이다. 따라서 [math]\displaystyle{ P(n_0 -1) }[/math]는 참이다. 그러면 가정에 의해 [math]\displaystyle{ P(n_0) }[/math]는 참이므로 [math]\displaystyle{ n_0\not\in S }[/math]이다. 그러면 [math]\displaystyle{ n_0\in S }[/math]이고 [math]\displaystyle{ n_0\not\in S }[/math]이므로 [math]\displaystyle{ n'\in \mathbb{N} }[/math]이 존재하여 [math]\displaystyle{ P(n') }[/math]이 거짓이라는 가정에 모순이다. 따라서 원하는 결론을 얻게 된다.