수학적 귀납법

개요

도미노를 일렬로 늘어세운 후 처음 세운 도미노를 넘어뜨린다고 가정하자. 만약 앞에 있는 도미노가 쓰러지면서 다음 도미노를 무조건 넘어뜨린다면, 첫번째 도미노를 넘어뜨리면 세워진 모든 도미노가 넘어지지 않을까?

수학적 귀납법(Mathematical induction)은 일반화된 명제의 증명 방법으로, 귀납법이란 이름을 달고 있지만 사실은 연역법이다. 고등학교 교육과정에선 수학적 귀납법의 원리를 이해할 수 있을 정도로 간단히 다루지만 대학교에서 수학 관련 전공에 진입하면 증명까지 다루게 된다. 이 문서에 한해서 자연수의 집합 [math]\displaystyle{ \mathbb{N} }[/math]이 0을 포함한다고 본다.

진술

자연수의 집합이 정의역인 조건을 [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]의 부분집합이므로, 정렬순서원리(well-ordering principle)에 의해 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]이 거짓이라는 가정에 모순이다. 따라서 원하는 결론을 얻게 된다.

귀납적 집합을 정의한 경우

귀납적 집합은 무한공리(axiom of infinity)로 인해 그 존재성이 보장된다. 집합 A를 다음과 같이 정의하자.

[math]\displaystyle{ A=\{n\in \mathbb{N}\vert P(n)\text{ holds}\} }[/math]

그러면 A는 귀납적 집합이고 따라서 [math]\displaystyle{ \mathbb{N}\subseteq A }[/math]이다. 따라서 원하는 결론을 얻는다.

수학적 귀납법의 변형

완전귀납법

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

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

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

완전귀납법의 증명은 간단하다. 조건 [math]\displaystyle{ Q(n) }[/math]를 "[math]\displaystyle{ P(0),P(1),\cdots,P(n) }[/math]는 참이다."로 설정하면 [math]\displaystyle{ Q(0)=P(0) }[/math]은 참이고 [math]\displaystyle{ P(0),P(1),\cdots,P(n) }[/math]이 참이면 가정에 의해 [math]\displaystyle{ P(n+1) }[/math]가 참이므로 결국 [math]\displaystyle{ P(0),P(1),\cdots,P(n+1) }[/math]가 참이다. 즉 [math]\displaystyle{ Q(n) }[/math]이 참이면 [math]\displaystyle{ Q(n+1) }[/math]이 참이다. 따라서 [math]\displaystyle{ Q(n) }[/math]은 귀납법 가정을 만족하므로 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ Q(n) }[/math]은 참인데 [math]\displaystyle{ Q(n) }[/math]의 정의에 의해 [math]\displaystyle{ P(n) }[/math]은 참이다.

한편 완전귀납법으로 정렬순서공리를 증명할 수 있다. 이 말은 수학적 귀납법과 정렬순서공리가 동치라는 것을 의미한다.

수학적 귀납법을 가정하자. 그리고 [math]\displaystyle{ \mathbb{N} }[/math]의 부분집합이고 공집합이 아니며, 최소원소가 없는 집합 S가 존재한다고 가정하자. 만약 [math]\displaystyle{ 0\in S }[/math]이면, 임의의 [math]\displaystyle{ x\in S }[/math]에 대해 [math]\displaystyle{ 0\le x }[/math]이므로 n이 S의 최소원소가 된다. 따라서 [math]\displaystyle{ 0\not\in S }[/math]이다. [math]\displaystyle{ 0\not \in S, 1\not\in S, \cdots, n\not\in S }[/math]라고 하자. 만약 [math]\displaystyle{ n+1\in S }[/math]라면, 임의의 [math]\displaystyle{ x\in S }[/math]에 대해 [math]\displaystyle{ n+1\le x }[/math]이므로 [math]\displaystyle{ n+1 }[/math]이 최소원소가 되어 모순이다. 따라서 [math]\displaystyle{ n+1\in S }[/math]이다. 따라서 완전귀납법에 의해 임의의 [math]\displaystyle{ n\in \mathbb{N} }[/math]에 대해 [math]\displaystyle{ n\not\in S }[/math]이고 따라서 S는 공집합이다. 이것은 S가 공집합이 아니라는 가정과 모순이다. 따라서 [math]\displaystyle{ \mathbb{N} }[/math]의 부분집합이고 공집합이 아닌 집합 S는 반드시 최소원소를 가진다.

초한귀납법

[math]\displaystyle{ P(x) }[/math]를 순서수를 정의역으로 하는 조건이라 하자. 임의의 순서수 α에 대해,

임의의 [math]\displaystyle{ \beta \lt \alpha }[/math]에 대해 [math]\displaystyle{ P(\beta) }[/math]가 참이면, [math]\displaystyle{ P(\alpha) }[/math]는 참이다.

이면 임의의 순서수 α에 대해 [math]\displaystyle{ P(\alpha) }[/math]는 참이다.

예시

다항함수의 도함수

다항함수 [math]\displaystyle{ f(x)=x^n\;(n\ge 1) }[/math]의 도함수는 [math]\displaystyle{ f'(x)=nx^{n-1} }[/math]임을 수학적 귀납법을 이용해 증명하자.

[math]\displaystyle{ f(x)=x }[/math]의 도함수는

[math]\displaystyle{ f'(x)=\lim_{h\to 0}\frac{f(h)-f(0)}{h}=1 }[/math]

이다. 이제 [math]\displaystyle{ f(x)=x^n }[/math]의 도함수가 [math]\displaystyle{ f'(x)=nx^{n-1} }[/math]이라고 가정하자. [math]\displaystyle{ f(x)=x^{n+1} }[/math]의 도함수는

[math]\displaystyle{ f'(x)=(x \cdot x^n)'=(x)' x^n + x(x^n)' = x^n + x(nx^{n-1})=(n+1)x^n }[/math]

이다. 따라서 수학적 귀납법에 의해 원하는 결론을 얻는다.

귀납적으로 정의된 수열

수열 [math]\displaystyle{ (a_n) }[/math]이 다음 식을 만족한다고 하자.

[math]\displaystyle{ a_{n+1}=\frac{a_n}{1+a_n}\; (n\ge 0) }[/math]

이때 임의의 n에 대해 다음 식이 성립한다고 가정하자.

[math]\displaystyle{ a_n=\frac{a_0}{1+na_0} }[/math]

그러면

[math]\displaystyle{ \begin{align} a_{n+1}&=\frac{a_n}{1+a_n}\\ &=\frac{\frac{a_0}{1+na_0}}{1+\frac{a_0}{1+na_0}}\\ &=\frac{\frac{a_0}{1+na_0}}{\frac{1+(n+1)a_0}{1+na_0}}\\ &=\frac{a_0}{1+(n+1)a_0} \end{align} }[/math]

이므로 수학적 귀납법에 의해 모든 자연수 n에 대해 [math]\displaystyle{ a_n=\frac{a_0}{1+na_0} }[/math]임을 안다.