#0002. 수학적 귀납법(Mathematical induction)

1. 개요

고등학교 과정에서, 자연수(혹은 정수)와 연관된 정리를 증명하는 데 가장 유용한 수단은 수학적 귀납법이다. 가령 다음의 명제를 증명한다고 하자.

자연수 \(n\)에 대하여 \( 11 \mid\left( 21^{2n-1} + 1 \right) \)이 성립한다.

물론 \( n = 1, 2, 3, \cdots \)를 대입해 가며 원하는 수 \(N\) 까지 성립함을 직접 보일 수 있다. 그러나 이 방법은 복잡한 계산이 짜증날 뿐 아니라, 명제가 모든 자연수에 대해 성립함을 보일 수 없다. 이런 경우 수학적 귀납법을 사용한다. 유한 번의 증명으로 무한한 경우에 대해 명제가 성립함을 보일 수 있는 것이다.

앞으로 나올 수학적 귀납법에는 많은 변형이 있지만, 언제나 특정한 경우인 base case와 이를 확장시키는 induction step으로 구성됨을 명심하자.

2. 수학적 귀납법

양의 정수 \(n\)에 대하여 정의된 명제 \(p\left(n\right)\)이 다음 두 조건을 만족한다고 하자.

1. \(p\left(1\right)\)은 참이다.
2. 어떤 자연수 \(k\)에 대하여 \(p\left(k\right)\)가 참이면, \(p\left(k+1\right)\)도 참이다.

그러면, 모든 자연수 \(n\)에 대하여 \(p\left(n\right)\)은 참이다.

이는 귀납법 공리(Axiom of Induction)에 전제한 것이다.

$$ T \subseteq \mathbb{N} \quad \text{s.t.} \quad 1 \in T \quad \land \quad k \in T \implies k+1 \in T \quad \text{then} \quad T = \mathbb{N} $$

2-1. 자연수의 정렬성

정수에서 성립하는 공리적 성질 중 자연수에 대한 정렬성 원리(Well-Ordering Principle for \(\mathbb{N}\), WOP)가 있다. 이는 최소원소 원리라고도 불리는데, 공집합이 아닌 자연수 집합은 언제나 최소원소를 갖는다는 원리이다. 예를 들어 집합 \( \left\{ 3, 5, 12, 109 \right\} \)에서 최소원소는 3이다. 누구나 당연하다고 생각할 것이다. 그런데 수학적 귀납법을 다루는 글에서 왜 정렬성을 꺼내드는가? 그 이유는 \(\mathbb{N}\)에 대한 정렬성 원리(WOP라고 줄이겠다)가 귀납법의 공리와 동치이기 때문이다.

증명(귀류법)

집합 \(T\)가 \( \mathbb{N} \) 안의 모든 원소를 포함하지 않는다고 가정하자. 즉 집합 \( S = \mathbb{N} - T \)가 공집합이 아니라고 하자.

집합 \(S \neq \phi\), \(S \subset \mathbb{N}\)이므로 WOP를 만족한다.

집합 \(S\)의 최소원소를 a라 하자. 이때 \(1 \in T\)이므로 \(a > 1\)이다.

\( a-1 < a\)이고 \(a-1 > 0 \)이므로 \(a-1 \in T\)이다.

\(k \in T \implies k+1 \in T\) 에 의하여 \(a-1 \in T \implies a \in T\)

그런데 \(S = \mathbb{N} - T\) 이므로 \(a\)는 \(S\)와 \(T\)에 동시에 포함될 수 없으므로 모순이다.

따라서 집합 \(S = \phi\)이고, \(T = \mathbb{N}\)이다. ■