PART I — 증명
수학적 귀납법은 유한한 한두 페이지짜리 증명으로 무한히 많은 명제를 한꺼번에 잡는 마법 같은 도구입니다. 이번 챕터에서는 일반 귀납법, 강한 귀납법, 정렬원리(well-ordering)라는 세 가지 동치인 원리를 차근차근 살펴보고, 왜 이 셋이 사실은 같은 이야기를 하는지를 풀어봅니다. 또한 학생들이 흔히 빠지는 함정 — 그 유명한 "모든 말은 같은 색이다" 같은 잘못된 귀납 — 도 함께 해부하며, 귀납이라는 도구를 손에 익혀봅시다.
자연수 \( n \)에 대해 어떤 명제 \( P(n) \)이 모두 참이라는 사실을 증명하고 싶다고 합시다. 무한히 많은 \( n \)을 하나하나 검사할 수는 없습니다. 이때 등장하는 묘책이 바로 귀납법입니다.
가장 흔한 비유는 도미노입니다. 길게 늘어선 도미노가 무한히 있어요. 우리가 보장하고 싶은 건 "모든 도미노가 결국 쓰러진다"는 사실입니다. 그러려면 두 가지만 확인하면 충분합니다. 첫째, 첫 번째 도미노를 우리가 직접 손가락으로 밀어 쓰러뜨립니다. 둘째, 임의의 \( k \)번째 도미노가 쓰러지면 \( k+1 \)번째도 반드시 쓰러진다는 보장이 있습니다. 이 두 가지가 동시에 성립하면, 첫 번째 도미노가 두 번째를 쓰러뜨리고, 두 번째가 세 번째를 쓰러뜨리고… 끝없이 이어져 모든 도미노가 쓰러집니다. 한 번도 손대지 않은 백만 번째 도미노조차도요.
이 직관을 그대로 수학 언어로 옮긴 것이 일반 귀납법입니다.
원리 5.1.1 (일반 귀납법, Induction)
자연수 \( n \in \mathbb{N} = \{0, 1, 2, \ldots\} \)에 대한 명제 \( P(n) \)이 다음 두 조건을 만족한다고 하자.
(1) 기저 단계 (base case): \( P(0) \)이 참이다.
(2) 귀납 단계 (inductive step): 임의의 \( k \ge 0 \)에 대해 \( P(k) \implies P(k+1) \)이 참이다.
그러면 모든 자연수 \( n \)에 대해 \( P(n) \)이 참이다.
여기서 귀납 단계의 \( P(k) \)를 귀납 가설(induction hypothesis)이라고 부릅니다. 증명을 쓸 때 우리는 보통 "어떤 \( k \)에 대해 \( P(k) \)가 성립한다고 가정하자"라고 운을 떼고, 그 가정으로부터 \( P(k+1) \)을 끌어냅니다. 가정을 일단 하나 사 놓고, 그것을 사다리 삼아 한 칸 위로 올라가는 것이라고 봐도 됩니다.
예제 5.1.2 (가우스의 합 공식)
모든 자연수 \( n \ge 1 \)에 대해 다음이 성립함을 보입시다.
\[ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}. \]
풀이. \( P(n) \)을 위 등식이라고 두자.
(기저 단계) \( n = 1 \)일 때 좌변은 \( 1 \), 우변은 \( \frac{1 \cdot 2}{2} = 1 \). 같다. \( P(1) \) 참.
(귀납 단계) \( P(k) \)가 참이라고 가정하자. 즉 \( 1 + 2 + \cdots + k = \frac{k(k+1)}{2} \)라고 하자. 이때 \( P(k+1) \), 다시 말해 \( 1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2} \)임을 보이면 된다.
좌변을 귀납 가설로 치환하면
\[ \underbrace{1 + 2 + \cdots + k}_{\text{귀납 가설}} + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}. \]
이는 정확히 \( P(k+1) \)의 우변이다. 따라서 \( P(k) \implies P(k+1) \).
두 단계가 모두 성립하므로 모든 \( n \ge 1 \)에 대해 \( P(n) \)이 참이다. ∎
처음 보면 "어? 이게 정말로 모든 \( n \)을 증명하는 거 맞아?"라는 의심이 들 수 있습니다. 그도 그럴 것이, 우리는 어디에서도 "구체적인 \( n=27 \)일 때"를 따로 증명하지 않았으니까요. 비밀은 도미노의 사슬에 있습니다. \( P(1) \)이 참이고, \( P(1) \implies P(2) \)이니 \( P(2) \)도 참. 이어서 \( P(2) \implies P(3) \)이니 \( P(3) \)도 참. 이렇게 27단계를 거치면 \( P(27) \)에 도달합니다. 우리가 증명에서 한 일은 사실상 "어떤 \( k \)를 가져와도 다음 칸으로 넘어갈 수 있는 보편적인 한 줄짜리 사다리"를 만든 것이고, 그 사다리가 무한히 반복 사용 가능하기 때문에 모든 \( n \)이 자동으로 따라옵니다.
예제 5.1.3 (홀수의 합)
또 하나의 고전 예제로, 처음 \( n \)개의 홀수의 합이 완전제곱이 됨을 봅시다.
\[ 1 + 3 + 5 + \cdots + (2n-1) = n^2 \quad (n \ge 1). \]
(기저) \( n=1 \): 좌변 \( 1 \), 우변 \( 1^2 = 1 \). 참.
(귀납) \( 1 + 3 + \cdots + (2k-1) = k^2 \)이라고 가정하자. 양변에 \( 2(k+1)-1 = 2k+1 \)을 더하면
\[ 1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + 2k + 1 = (k+1)^2. \]
이는 \( P(k+1) \)의 형태이다. ∎
이제 학생들에게 정말 깊이 새겨야 할 위험한 함정을 하나 보여드리겠습니다. 귀납법의 두 단계 중 어느 한 곳이라도 부주의하면 명백히 거짓인 명제도 "증명"되는 듯 보인다는 점입니다.
주의: 모든 말은 같은 색이다(?)
다음은 유명한 잘못된 귀납입니다. \( P(n) \)을 "임의의 말 \( n \)마리는 모두 같은 색이다"라고 정의합시다.
(기저) \( n=1 \): 한 마리뿐이니 자기 자신과 같은 색. 자명.
(귀납) \( P(k) \)가 참이라고 가정. 말 \( k+1 \)마리를 일렬로 세워보자: \( h_1, h_2, \ldots, h_{k+1} \).
앞쪽 \( k \)마리 \( \{h_1, \ldots, h_k\} \)는 귀납 가설로 모두 같은 색.
뒤쪽 \( k \)마리 \( \{h_2, \ldots, h_{k+1}\} \)도 귀납 가설로 모두 같은 색.
두 집합은 \( h_2 \)부터 \( h_k \)까지 겹치므로, "같은 색"이라는 성질이 전염되어 모두 한 색!
따라서 모든 자연수 \( n \)에 대해 임의의 말 \( n \)마리는 같은 색. 결론: 세상 모든 말은 같은 색.
물론 결론은 거짓입니다. 어디가 잘못됐을까요? 핵심은 \( k=1 \)에서 \( k+1=2 \)로 넘어갈 때입니다. 말 두 마리 \( h_1, h_2 \)의 경우, 앞 1마리 집합은 \( \{h_1\} \), 뒤 1마리 집합은 \( \{h_2\} \). 두 집합은 겹치는 원소가 없습니다. "같은 색"을 전염시킬 다리가 없는 거예요. 즉 귀납 단계가 \( k \ge 2 \)일 때만 동작하는데, 우리는 그것을 모든 \( k \ge 1 \)에 대해 성립한다고 슬쩍 가정해버렸습니다. 도미노 사슬에 한 칸 빠진 곳이 있으면 그 너머는 무너지지 않습니다.
이 함정의 교훈은 분명합니다. 귀납 단계가 "모든 \( k \)에 대해" 성립한다고 주장할 때, 우리가 사용한 모든 보조 사실(여기서는 두 집합의 교집합이 비지 않는다는 사실)이 정말로 모든 \( k \)에서 통하는지 검증해야 합니다. 작은 \( k \)에서 한 번이라도 사슬이 끊기면 전체 증명이 무너집니다.
일반 귀납법은 \( P(k) \) 하나만으로 \( P(k+1) \)을 끌어내는 방식이었습니다. 그러나 어떤 명제는 한 칸 전이 아니라 지금까지 쌓아온 모든 결과를 동시에 활용해야 다음 칸을 증명할 수 있습니다. 이때 등장하는 게 강한 귀납법(strong induction)입니다. 이름이 거창하지만 사실은 가설을 더 풍부하게 사용해도 된다는 허락일 뿐이에요.
원리 5.2.1 (강한 귀납법)
자연수에 대한 명제 \( P(n) \)이 다음 두 조건을 만족한다고 하자.
(1) 기저 단계: \( P(0) \)이 참이다.
(2) 귀납 단계: 임의의 \( k \ge 0 \)에 대해, \( P(0), P(1), \ldots, P(k) \)이 모두 참이라고 가정하면 \( P(k+1) \)도 참이다.
그러면 모든 자연수 \( n \)에 대해 \( P(n) \)이 참이다.
일반 귀납법과의 차이를 다시 강조하자면, 귀납 가설로 사용할 수 있는 정보의 폭이 다릅니다. 일반 귀납법은 직전 한 칸 \( P(k) \)만 손에 쥐고 \( P(k+1) \)을 만들지만, 강한 귀납법은 \( P(0) \)부터 \( P(k) \)까지 전부 손에 쥐고 \( P(k+1) \)을 만듭니다. 무기고가 더 빵빵해진 셈이죠. 그래서 "더 강한" 귀납법이라고 부릅니다. 도미노 비유로는, 다음 도미노를 쓰러뜨릴 때 단지 직전 한 개의 도미노가 부딪힌 충격만이 아니라, 지금까지 쓰러진 모든 도미노가 만들어낸 누적 효과를 활용해도 된다는 뜻입니다.
강한 귀납법이 진가를 발휘하는 대표적인 예가 바로 정수론의 출발점, 소인수분해 존재성입니다.
정리 5.2.2 (소인수분해의 존재)
2 이상의 모든 자연수 \( n \)은 유한 개의 소수의 곱으로 표현할 수 있다. 즉 어떤 소수들 \( p_1, p_2, \ldots, p_m \)이 존재하여 \( n = p_1 p_2 \cdots p_m \)이다.
증명 (강한 귀납법)
\( P(n) \)을 "\( n \)이 소수들의 곱으로 표현 가능하다"는 명제라고 두자. \( n \ge 2 \)에 대해 강한 귀납법으로 증명한다.
(기저) \( n = 2 \): 2 자체가 소수이다. 자기 자신을 길이 1의 곱으로 보면 \( 2 = 2 \). 따라서 \( P(2) \) 참.
(귀납) 어떤 \( k \ge 2 \)에 대해 \( P(2), P(3), \ldots, P(k) \)이 모두 참이라고 가정하자. \( P(k+1) \)을 보이자. 즉 \( k+1 \)이 소수들의 곱임을 보이자.
경우를 나눈다.
(i) \( k+1 \)이 소수인 경우. 그 자체가 소수의 곱이므로 \( P(k+1) \) 참.
(ii) \( k+1 \)이 합성수인 경우. 정의상 \( k+1 = a \cdot b \)이고 \( 2 \le a \le b \le k \)인 자연수 \( a, b \)가 존재한다. 이때 \( a, b \)는 모두 \( k \) 이하이므로, 귀납 가설에 의해 \( a \)와 \( b \)는 각각 소수의 곱으로 표현된다. 두 표현을 이어 붙이면 \( k+1 = a \cdot b \) 또한 소수의 곱이다. 즉 \( P(k+1) \) 참.
두 경우 모두 성립하므로 귀납이 끝난다. ∎
여기서 결정적인 점은, \( P(k+1) \)을 증명하기 위해 우리가 \( P(k) \)가 아니라 \( P(a) \)와 \( P(b) \)를 가져다 썼다는 사실입니다. \( a \)와 \( b \)는 \( k+1 \)보다 작은 어떤 값일 뿐, 정확히 \( k \)는 아닙니다. 일반 귀납법에서는 직전 한 칸의 결과만 사용 가능하므로 이런 식의 증명을 곧장 쓰기가 어색하지만, 강한 귀납법에서는 자연스럽습니다.
예제 5.2.3 (체스 토너먼트 우승 트리)
\( n \)명의 선수가 토너먼트로 단판 승부를 합니다. 매 경기 후 한 명이 탈락한다고 할 때, 우승자가 결정되기까지 정확히 \( n-1 \)번의 경기가 필요함을 보입시다.
풀이. \( P(n) \): "\( n \)명 토너먼트에는 정확히 \( n-1 \)번의 경기가 있다."
(기저) \( n = 1 \): 경기 0번. 참.
(귀납) \( P(1), \ldots, P(k) \)가 참이라고 하자. \( k+1 \)명 토너먼트의 결승전 직전을 보면, 두 그룹 \( a \)명과 \( b \)명에서 각각 우승자가 결정되어 결승에 올라간다고 볼 수 있다 (\( a + b = k+1 \), \( 1 \le a, b \le k \)). 귀납 가설로 두 그룹은 각각 \( a-1 \), \( b-1 \)번의 경기를 거친다. 마지막 결승까지 더하면 \( (a-1) + (b-1) + 1 = a+b-1 = k \)번의 경기. 따라서 \( P(k+1) \) 참. ∎
한 가지 더 강조할 점이 있습니다. 강한 귀납법과 일반 귀납법은 결국 같은 결론을 증명할 수 있다는 의미에서 동치입니다. 강한 귀납법으로 증명되는 모든 명제는 일반 귀납법으로도 증명할 수 있고, 그 반대도 마찬가지입니다. 다만 강한 귀납법으로 쓰면 증명이 자연스럽고 깔끔해지는 경우가 많을 뿐입니다.
노트: 왜 동치인가
강한 귀납법으로 \( P(n) \)을 증명하고 싶다고 합시다. 새 명제 \( Q(n) := P(0) \land P(1) \land \cdots \land P(n) \)을 정의하면, \( Q \)에 대해 일반 귀납법을 써서 증명할 수 있습니다. \( Q(k) \implies Q(k+1) \)을 보이는 일이 곧 강한 귀납법의 귀납 단계와 같으니까요. 이렇게 가설을 묶어두는 트릭만으로 일반 귀납법이 강한 귀납법을 흉내낼 수 있습니다. 반대 방향은 더 자명합니다 — 강한 귀납법은 일반 귀납법의 가설을 포함하니까 더 적은 정보만 쓰면 일반 귀납과 다를 게 없습니다.
실전에서는 "이 문제는 일반 귀납이냐 강한 귀납이냐"를 너무 고민하지 말고, 증명 도중 \( k+1 \) 이전의 어떤 값을 가져다 쓰고 싶어지는지를 보고 자연스럽게 강한 귀납을 쓰면 됩니다. 컴퓨터과학에서 분할정복 알고리즘의 정당성 증명, 재귀 호출의 종료 증명, 자료구조의 불변식 증명 같은 데서 강한 귀납법이 거의 표준적으로 등장합니다.
4장에서 우리는 정렬원리(Well Ordering Principle)를 만났습니다. 다시 적어두면 다음과 같습니다.
원리 5.3.1 (정렬원리, Well Ordering Principle)
자연수 \( \mathbb{N} \)의 공집합이 아닌 모든 부분집합 \( S \subseteq \mathbb{N} \)는 최소 원소를 가진다.
그리고 이번 챕터에서 일반 귀납법과 강한 귀납법을 만났습니다. 놀랍게도 이 셋은 서로 동치입니다. 즉 셋 중 어느 하나라도 자연수 체계의 공리로 받아들이면 나머지 둘이 따라옵니다. "다른 모자를 쓴 같은 사람"이라고 부를 만합니다.
정리 5.3.2 (세 원리의 동치)
다음 세 명제는 자연수 \( \mathbb{N} \)에서 서로 동치이다.
(WO) 정렬원리
(SI) 강한 귀납법
(I) 일반 귀납법
증명의 큰 그림을 먼저 보고 갑시다. 서로 동치임을 보이려면 일반적으로 셋을 한 사이클로 잇는 함의를 보입니다. 즉
┌─── (WO) ───┐
│ │
▼ │
(SI) │
│ │
▼ │
(I) ─────────┘
방향으로 \( (WO) \implies (SI) \implies (I) \implies (WO) \)를 보이면, 어느 둘 사이의 함의도 사이클을 한 바퀴 돌아 얻을 수 있습니다.
증명 스케치
(WO) ⇒ (SI): 정렬원리를 가정. 어떤 \( P \)가 강한 귀납법의 두 조건(기저, 강한 귀납 단계)을 만족한다고 하자. \( P \)가 모든 자연수에서 참임을 보이고 싶다.
모순법을 쓰자. 만약 어떤 \( n \)에서 \( P(n) \)이 거짓이라고 하면, 반례 집합 \( S = \{ n \in \mathbb{N} : \lnot P(n) \} \)은 공집합이 아니다. 정렬원리로 \( S \)는 최소 원소 \( m \)을 가진다. \( m \neq 0 \)이다 (왜냐하면 기저 단계로 \( P(0) \)이 참). 따라서 \( m \ge 1 \), 그리고 \( m \)이 \( S \)의 최솟값이라는 사실에서 \( P(0), P(1), \ldots, P(m-1) \)은 모두 참. 그러면 강한 귀납 단계로 \( P(m) \)도 참이 되어야 하는데, 이는 \( m \in S \)와 모순이다. 따라서 \( S \)는 공집합이고 \( P \)는 어디서나 참이다.
(SI) ⇒ (I): 강한 귀납법을 가정. 어떤 \( P \)가 일반 귀납법의 두 조건을 만족한다고 하자. 그러면 특히 \( P(k) \implies P(k+1) \)이 성립하므로, "\( P(0), \ldots, P(k) \)가 모두 참"이라는 더 강한 가정으로부터도 당연히 \( P(k+1) \)이 따라온다 (사용 안 하는 가설이 늘었을 뿐). 그러므로 강한 귀납법의 두 조건도 만족하고, 강한 귀납법으로 \( P \)는 모든 \( n \)에서 참.
(I) ⇒ (WO): 일반 귀납법을 가정. 정렬원리를 보이고 싶다. 즉 공집합이 아닌 \( S \subseteq \mathbb{N} \)에 대해 최솟값이 존재함을 보이자.
대우로 가자. \( S \)에 최솟값이 없다고 가정하고 \( S = \emptyset \)임을 증명한다. 명제 \( Q(n) := \) "\( 0, 1, \ldots, n \)은 모두 \( S \)에 속하지 않는다"라고 정의하자. 이를 \( n \)에 대한 일반 귀납법으로 증명하면 \( Q \)가 모든 자연수에서 참, 즉 \( S \)에 어떤 자연수도 들어갈 수 없게 되어 \( S = \emptyset \)이 된다.
(기저) \( n=0 \): 만약 \( 0 \in S \)라면 0은 자연수의 최솟값이므로 \( S \)의 최솟값이 된다. 이는 가정에 어긋나므로 \( 0 \notin S \). 따라서 \( Q(0) \) 참.
(귀납) \( Q(k) \) 참이라고 하자, 즉 \( 0, 1, \ldots, k \)는 모두 \( S \)에 없다. \( k+1 \in S \)라면 \( k+1 \)은 \( S \)의 가장 작은 원소가 된다 (\( S \) 안에 \( k+1 \)보다 작은 원소가 \( k \) 이하 자연수 중 없으므로). 가정과 모순. 따라서 \( k+1 \notin S \)이며 \( Q(k+1) \) 참.
일반 귀납법으로 \( Q(n) \)이 모든 \( n \)에서 참, 즉 \( S = \emptyset \). ∎
이 사이클이 보여주는 바는 강력합니다. 자연수 위의 명제를 증명할 때 어떤 도구를 고를지는 사실 스타일의 문제이지 능력의 문제가 아닙니다. 정렬원리로 풀리는 모든 문제는 일반 귀납법으로도 풀 수 있고, 강한 귀납법으로 풀리는 모든 문제는 정렬원리로도 풀 수 있습니다. 다만 어떤 문제는 한쪽 옷이 더 잘 맞을 뿐이에요.
노트: 어떤 옷을 언제 입을까
대략적인 경험칙을 적어두면 다음과 같습니다.
(가) 닫힌 형태의 등식(예: \( \sum_{i=1}^n i = \frac{n(n+1)}{2} \))처럼 한 칸씩 차곡차곡 쌓이는 증명에는 일반 귀납법이 가장 깔끔합니다.
(나) 합성/분해를 동반하는 명제(소인수분해, 분할정복 알고리즘, 트리·그래프의 구조 분해)에는 강한 귀납법이 자연스럽습니다. 작은 부분문제로 쪼개진 결과들을 모두 끌어오는 일이 빈번하니까요.
(다) "이런 게 존재할 수 없다"식의 부정적 결론(예: 무리수성 증명, 무한강하법, 알고리즘 종료성 증명)에는 정렬원리가 단정합니다. "최소 반례를 잡고 그것이 또 작은 반례를 만들어내 모순"이라는 무한강하 패턴이 정렬원리 위에서 가장 자연스럽기 때문입니다.
마지막으로 한 가지 직관을 덧붙이고 싶습니다. 자연수가 "잘 정렬된" 집합이라는 사실 — 즉 비어 있지 않은 어떤 부분집합도 반드시 가장 작은 원소를 가진다는 사실 — 은 자연수 체계의 가장 본질적인 성질 중 하나입니다. 도미노가 줄지어 있다는 그림과, 부분집합에 항상 출발점이 있다는 그림은 결국 같은 그림의 두 얼굴입니다. 한쪽은 "처음을 미는 손가락"의 관점이고, 다른 한쪽은 "가장 처음에 있는 도미노"의 관점입니다. 우리가 원리 셋을 자유자재로 오갈 수 있게 되는 순간, 이 두 얼굴이 하나의 얼굴로 보이기 시작합니다.
이번 챕터의 도구들은 앞으로 그래프 이론, 알고리즘, 수론, 형식언어 어디에서나 다시 만날 겁니다. 한 번에 다 익숙해지지 않더라도, 새 단원에서 귀납을 다시 마주칠 때마다 이 챕터로 돌아와 도미노와 정렬, 그리고 "유한한 손가락질로 무한을 다루는 마법"을 떠올려보길 권합니다.