5-2. 강한귀납법(Strong Induction)과 정렬 원리(Well-Ordering Property)

[이전글] 5-1. 수학적 귀납법(Mathematical Induction) 개념 총정리와 증명법

[다음글] 5-3. Recursive Definitions and Structural Induction

★본문의 더보기는 증명과 풀이입니다.

 

수학적 귀납법(Mathematical Induction)은 수열이나 정수 관련 명제를 증명할 때 매우 강력한 도구다. 하지만 단순히 $P(k) \to P(k+1)$ 관계만으로 증명하기 까다로운 문제들이 존재한다. 이때 사용하는 개념이 바로 강한귀납법(Strong Induction)과 정렬 원리(Well-Ordering Property)다.

 

1. 강한귀납법(Strong Induction)이란?

강한귀납법은 제2 수학적 귀납법(Second Principle of Induction) 또는 완전귀납법(Complete Induction)이라고도 부른다.

일반 수학적 귀납법과의 차이는 귀납 가정(Inductive Hypothesis)의 범위에 있다.

• 일반 귀납법: $P(k)$가 참이라고 가정하고 $P(k+1)$이 참임을 증명함.
• 강귀납법: $P(1), P(2), \dots, P(k)$가 모두 참이라고 가정하고 $P(k+1)$이 참임을 증명함.

강귀납법의 증명 단계 (모든 양의 정수 $n$에 대해)

1. 기초 단계 (Basis Step): $P(1)$이 참임을 확인한다.
2. 귀납 단계 (Inductive Step): 모든 양의 정수 $k$에 대해, $[P(1) \land P(2) \land \dots \land P(k)] \to P(k+1)$ 이 참임을 증명한다.

참고: 일반 귀납법과 강귀납법은 증명 능력 면에서 동치(Equivalent)이다. 즉, 강귀납법으로 증명할 수 있는 것은 일반 귀납법으로도 증명 가능하지만, 강귀납법을 쓰면 귀납 가정이 더 풍부해져 증명 과정이 훨씬 단순해진다.

 

2. 변형된 강귀납법 (시작점이 $b$ 이상인 경우)

문제 조건에 따라 기초 단계가 $n=1$이 아니라 $n=b$부터 시작하거나, 기초 단계에서 여러 초기값을 확인해야 할 때가 있다.

• 기초 단계: $P(b), P(b+1), \dots, P(b+j)$가 참임을 증명한다.
• 귀납 단계: $k \ge b+j$인 정수 $k$에 대해, $[P(b) \land P(b+1) \land \dots \land P(k)] \to P(k+1)$이 참임을 증명한다.

[예제 1] 소인수분해의 존재성 증명

 $n \ge 2$인 모든 정수 $n$은 하나 이상의 소수(Prime number)들의 곱으로 나타낼 수 있음을 강귀납법으로 증명하여라.

[증명]

• 기초 단계 ($n=2$): $2$는 그 자체로 소수이므로 $1$개의 소수의 곱으로 나타낼 수 있다. 따라서 $P(2)$는 참이다.
• 귀납 가정: $2 \le j \le k$인 모든 정수 $j$에 대해 $P(j)$가 참이라고 가정하자. 즉, $2$ 이상 $k$ 이하의 모든 정수는 소수의 곱으로 표현 가능하다.
• 귀납 단계 ($n=k+1$):
  1. 만약 $k+1$이 소수라면, 명제는 즉시 성립한다.
  2. 만약 $k+1$이 합성수라면, $k+1 = a \times b$를 만족하는 정수 $a, b$가 존재한다 ($2 \le a \le b < k+1$).
  3. 이때 $a$와 $b$는 모두 $2$ 이상 $k$ 이하의 정수이므로 귀납 가정에 의해 각각 소수들의 곱으로 표현할 수 있다.
  4. 따라서 $k+1 = a \times b$ 역시 소수들의 곱으로 나타낼 수 있다.
• 결론: 강귀납법에 의해 $n \ge 2$인 모든 정수는 소수의 곱으로 표현할 수 있다.

[예제 2]우표 결합 문제 

3원짜리 우표와 7원짜리 우표만 사용하여 12원 이상의 모든 금액을 만들어낼 수 있음을 강귀납법으로 증명하여라.

[증명]

우표의 조합으로 만들어야 하므로 연속된 3개의 금액($12, 13, 14$)을 기초 단계로 설정한다.

• 기초 단계 ($n=12, 13, 14$):
  • $12$원 = 3원 $\times$ 4개
  • $13$원 = 3원 $\times$ 2개 + 7원 $\times$ 1개
  • $14$원 = 7원 $\times$ 2개
  • 따라서 $P(12), P(13), P(14)$는 모두 참이다.
• 귀납 가정: $12 \le j \le k$ ($k \ge 14$)인 모든 정수 $j$에 대해 $P(j)$가 참이라고 가정하자.
• 귀납 단계 ($n=k+1$):
  • $k \ge 14$이므로 $(k+1) - 3 = k-2 \ge 12$가 성립한다.
  • 귀납 가정에 의해 $k-2$원에 대한 우표 조합이 존재한다.
  • 이 $k-2$원 조합에 3원짜리 우표 1장을 추가하면 $(k+1)$원의 우표 조합이 완성된다.
• 결론: 강귀납법에 의해 12원 이상의 모든 금액을 3원 및 7원 우표로 만들 수 있다.

[예제 3] 다각형의 삼각분할(Triangulation)

$n$개의 변을 가진 단순 다각형(Simple Polygon)은 $n-2$개의 삼각형으로 분할(Triangulation)될 수 있음을 보여라. ($n \ge 3$).

[풀이]

• 기초 단계 ($n=3$): 변이 3개인 다각형은 삼각형 그 자체이다. 추가적인 대각선 없이 $3-2 = 1$개의 삼각형으로 구성되므로 $T(3)$은 참이다.
• 귀납 가정: $3 \le j \le k$인 모든 정수 $j$에 대해, $j$각형은 $j-2$개의 삼각형으로 분할된다고 가정하자.
• 귀납 단계 ($n=k+1$):
  • $k+1 \ge 4$인 다각형 $P$는 내부에 적어도 하나의 내부 대각선(Interior Diagonal) $ab$를 가진다.
  • 대각선 $ab$에 의해 다각형 $P$는 두 개의 더 작은 단순 다각형 $Q$($s$개 변)와 $R$($t$개 변)로 나누어진다.
  • 이때 $Q$와 $R$의 변의 수 $s, t$는 모두 $3 \le s, t \le k$를 만족하며, 전체 변의 합 공식은 $s + t - 2 = k+1$이 된다.
  • 귀납 가정에 따라 $Q$는 $s-2$개, $R$은 $t-2$개의 삼각형으로 분할된다.
  • 따라서 다각형 $P$ 전체의 삼각형 개수는 $(s-2) + (t-2) = (s+t-2) - 2 = (k+1) - 2$개가 된다.
• 결론: 강귀납법에 의해 $n \ge 3$인 모든 단순 다각형은 $n-2$개의 삼각형으로 분할할 수 있다.

3. 정렬 원리(Well-Ordering Property)

수학적 귀납법과 강귀납법의 정당성은 정수의 기본 공리인 정렬 원리에서 비롯된다.

 

정렬 원리 (Well-Ordering Property): 공집합이 아닌 음이 아닌 정수들의 모든 집합은 최소 원소(Least Element)를 가진다.

[증명] (대류/귀류법과 강귀납법을 이용한 증명)

$S$가 최소 원소를 가지지 않는다고 가정하자 (귀류법의 가정).

우리의 목표는 이 가정이 $S$가 공집합이라는 결론으로 이어짐을 보여, "$S$는 공집합이 아니다"라는 전제조건과 모순됨을 유도하는 것이다.

이를 위해 명제 $P(n)$을 다음과 같이 정의하자.

$$\text{"} 0, 1, 2, \dots, n \text{ 중에서 그 어떤 원소도 } S\text{에 속하지 않는다."}$$

이제 $n$에 대한 강귀납법(Strong Induction)으로 모든 음이 아닌 정수 $n$에 대해 $P(n)$이 참임을 증명한다.

1. 기초 단계 (Basis Step)

• $P(0)$이 참임을 확인해야 한다. 즉, $0 \notin S$임을 보인다.
• 만약 $0 \in S$라면, $S$의 모든 원소는 음이 아닌 정수이므로 $0$보다 작은 원소는 $S$에 존재할 수 없다.
• 따라서 $0$은 $S$의 최소 원소가 되어버려 "$S$가 최소 원소를 가지지 않는다"는 가정에 모순된다.
• 그러므로 $0 \notin S$이어야만 하며, $P(0)$은 참이다.

2. 귀납 단계 (Inductive Step)

• $0 \le j \le k$인 모든 정수 $j$에 대해 $P(j)$가 참이라고 가정하자 (강귀납 가정).
• 즉, $0, 1, 2, \dots, k$ 중 그 어느 것도 $S$에 속하지 않는다고 가정하자.
• 이제 $P(k+1)$이 참임, 즉 $k+1 \notin S$임을 증명해야 한다.
• 만약 $k+1 \in S$라면 어떻게 되는지 살펴보자.
  • 귀납 가정에 의해 $0, 1, 2, \dots, k$는 모두 $S$의 원소가 아니다.
  • 따라서 $S$에 존재하는 모든 원소는 $k+1$보다 큰 정수일 수밖에 없다.
  • 이는 $k+1$이 $S$의 최소 원소가 됨을 의미하므로, "$S$가 최소 원소를 가지지 않는다"는 가정에 모순된다.
• 따라서 $k+1 \notin S$이어야만 한다.
• 이로써 $[P(0) \land P(1) \land \dots \land P(k)] \implies P(k+1)$임이 입증되었다.

3. 결론

• 강귀납법에 의해 모든 음이 아닌 정수 $n \ge 0$에 대해 $P(n)$은 참이다.
• 이는 $0, 1, 2, 3, \dots$ 모든 음이 아닌 정수가 $S$에 속하지 않는다는 것을 의미하므로, $S = \emptyset$ (공집합)이 된다.
• 이는 "$S$가 공집합이 아닌 부분집합이다"라는 전제조건에 모순된다.

따라서 귀류법에 의해 "공집합이 아닌 음이 아닌 정수들의 집합 $S$는 반드시 최소 원소를 가진다"는 잘순서 원리가 성립한다.

정렬 원리를 이용한 나눗셈 정리(Division Algorithm) 증명

정수 $a$와 양의 정수 $d$에 대해, $a = dq + r$ ($0 \le r < d$)를 만족하는 유일한 정수 $q, r$이 존재함을 증명하여라.

[존재성 증명]

1. 집합 $S = {a - dk \mid k \in \mathbb{Z}, a - dk \ge 0}$를 정의하자.
2. $k$를 충분히 작은 음의 정수로 잡으면 $a - dk \ge 0$이 되므로, 집합 $S$는 음이 아닌 정수들의 비어있지 않은 집합(Nonempty set)이다.
3. 정렬 원리에 의해 $S$는 최소 원소 $r$을 가진다. 즉, 어떤 정수 $q$에 대해 $r = a - dq \ge 0$이다.
4. 이제 $r < d$임을 증명하기 위해 귀류법을 사용하자. 만약 $r \ge d$라고 가정하면: 
   $$r' = r - d = (a - dq) - d = a - d(q + 1)$$ 이 되어 $r' \ge 0$이 되고, $r' \in S$가 된다.
5. 하지만 $r' = r - d < r$이므로 $r$이 $S$의 최소 원소라는 사실에 모순이 발생한다.
6. 따라서 $0 \le r < d$를 만족하는 정수 $q, r$이 존재한다.

4. 수학적 귀납법 vs 강귀납법: 언제 무엇을 사용하는가?

강귀납법과 일반 귀납법을 접할 때 가장 흔히 드는 의문은 "도대체 어떤 상황에서 강귀납법을 선택해야 하는가?"이다.

1) 구조적 차이점 비교

 

2) 선택 기준

$P(k+1)$항의 형태가 $P(k)$만으로 표현되지 않고, $P(k-1)$, $P(k/2)$, 혹은 그보다 더 작은 인덱스들의 조합으로 표현된다면 무조건 강귀납법을 사용해야 증명이 풀린다.

 

[예제 4] 점화식으로 정의된 수열의 상한(Upper Bound) 증명

수열 ${a_n}$이 다음과 같이 재귀적으로 정의되어 있다.

$$a_1 = 1, \quad a_2 = 3$$

$$a_n = a_{n-1} + 2a_{n-2} \quad (n \ge 3)$$

모든 양의 정수 $n \ge 1$에 대해 $a_n \le 2^n$임을 강귀납법으로 증명하여라.

[풀이]

• 기초 단계 ($n=1, 2$):
  • $n=1$일 때: $a_1 = 1 \le 2^1 = 2$ (참)
  • $n=2$일 때: $a_2 = 3 \le 2^2 = 4$ (참)
  • 항 $a_n$이 이전 2개의 항에 의존하므로, 기초 단계에서 2개의 초기값을 모두 검증해야 한다.
• 귀납 가정: $1 \le j \le k$ ($k \ge 2$)인 모든 정수 $j$에 대해 $a_j \le 2^j$가 성립한다고 가정하자.
• 귀납 단계 ($n=k+1$):
  • 점화식 정의에 따라 $a_{k+1} = a_k + 2a_{k-1}$이다.
  • $k \ge 2$이므로 $k$와 $k-1$ 모두 귀납 가정의 범위($1 \le j \le k$)에 속한다.
  • 귀납 가정을 적용하면:$$a_{k+1} = a_k + 2a_{k-1} \le 2^k + 2 \cdot (2^{k-1})$$
  • 오른쪽 식을 정리하면:$$2^k + 2 \cdot 2^{k-1} = 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$$
  • 따라서 $a_{k+1} \le 2^{k+1}$이 성립한다.
• 결론: 강귀납법에 의해 모든 $n \ge 1$에 대해 $a_n \le 2^n$이다.

[예제 5] 2의 거듭제곱 지불 문제 (게임/조합론 응용)

모든 자연수 $n \ge 1$은 서로 다른 2의 거듭제곱들의 합(즉, 이진수 표현)으로 나타낼 수 있음을 증명하여라.

[풀이]

• 기초 단계 ($n=1$): $1 = 2^0$이므로 성립한다.
• 귀납 가정: $1 \le j \le k$인 모든 정수 $j$가 서로 다른 2의 거듭제곱의 합으로 표현된다고 가정하자.
• 귀납 단계 ($n=k+1$):
  • Case 1: $k+1$이 짝수인 경우
    • $k+1 = 2m$을 만족하는 정수 $m$이 존재한다 ($1 \le m \le k$).
    • 귀납 가정에 의해 $m$은 서로 다른 2의 거듭제곱의 합으로 표현된다: $m = 2^{e_1} + 2^{e_2} + \dots + 2^{e_r}$.
    • 양변에 2를 곱하면 $k+1 = 2m = 2^{e_1+1} + 2^{e_2+1} + \dots + 2^{e_r+1}$이 되며, 지수들이 여전히 모두 서로 다르므로 $k+1$ 역시 성립한다.
  • Case 2: $k+1$이 홀수인 경우
    • $k$는 짝수이므로 귀납 가정 또는 Case 1에 의해 $k$를 2의 거듭제곱의 합으로 표현할 수 있다.
    • 짝수의 이진 표현에는 $2^0(=1)$ 항이 들어가지 않는다.
    • 따라서 $k$의 표현에 $2^0$을 더해주기만 하면 $k+1$의 표현이 완성되며, 중복되는 거듭제곱 항은 생기지 않는다.
• 결론: 강귀납법에 의해 모든 자연수 $n$은 서로 다른 2의 거듭제곱의 합으로 나타낼 수 있다.

5. [동등성] 정렬 원리로 강귀납법 증명하기

수학적으로 정렬 원리(Well-Ordering Property), 수학적 귀납법, 그리고 강귀납법은 동치(Equivalent)다. 앞서 귀납법으로 잘순서 원리를 증명했으니, 반대로 잘순서 원리를 공리로 사용하여 강귀납법의 정당성을 증명해 보자.

 

[정리] 정렬 원리 $\implies$ 강귀납법의 성립

[증명]

1. 다음 두 조건을 만족하는 명제 $P(n)$이 있다고 하자.
   • (조건 1) $P(1)$은 참이다.
   • (조건 2) 모든 $k \ge 1$에 대해, $[P(1) \land P(2) \land \dots \land P(k)] \implies P(k+1)$은 참이다.
2. 강귀납법이 거짓이라고 가정하자 (귀류법). 즉, $P(n)$이 거짓이 되게 하는 양의 정수 $n$이 적어도 하나 존재한다.
3. $P(n)$을 거짓으로 만드는 양의 정수들의 집합을 $S$라 하자.
   $$S = \{ n \in \mathbb{Z}^+ \mid P(n)\text{은 거짓이다} \}$$
4. 가정에 의해 $S$는 공집합이 아닌 양의 정수의 집합이다.
5. 정렬 원리에 의해 $S$는 반드시 최소 원소(Least Element) $m$을 갖는다.
6. (조건 1)에 의해 $P(1)$은 참이므로 $1 \notin S$이다. 따라서 최소 원소 $m$은 $1$보다 엄밀히 크다 ($m > 1$, 즉 $m - 1 \ge 1$).
7. $m$이 $S$의 최소 원소이므로, $m$보다 작은 모든 양의 정수 $1, 2, \dots, m-1$은 $S$에 속하지 않는다.
8. 이는 $P(1), P(2), \dots, P(m-1)$이 모두 참이라는 뜻이다.
9. 하지만 (조건 2)에 의해 $P(1) \land \dots \land P(m-1)$이 참이면 $P(m)$도 참이어야 한다.
10. 이는 $m \in S$ ($P(m)$은 거짓)이라는 사실과 모순된다.
11. 따라서 $S$는 공집합이어야만 하며, 모든 양의 정수 $n$에 대해 $P(n)$은 참이다.

 

★5-2. 강한귀납법(Strong Induction)과 정렬 원리(Well-Ordering Property) 12문제와 풀이