Induction and Recursion

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 4

Intuition

수학적 귀납법은 도미노가 쓰러지는 원리와 같다. 첫 번째 도미노가 쓰러지고($P(1)$), 임의의 도미노가 쓰러질 때 다음 도미노가 반드시 쓰러짐($P(k) \to P(k+1)$)을 보장하면 모든 도미노가 쓰러진다.

One-liner

수학적 귀납법과 재귀적 정의를 통해 무한한 정수 집합이나 복잡한 구조체의 성질을 엄밀하게 증명하고, 알고리즘의 타당성을 검증한다.

Prerequisites

• 고교 수학 수준의 수열과 합: $\sum$ 기호 및 등차/등비수열의 이해 (Ch. 2).
• 기초 논리: 조건문($p \to q$), 전칭 정량자($\forall$), 추론 규칙의 이해 (Ch. 1).
• 집합론: 부분집합, 멱집합, 정수 집합의 기본 성질 (Ch. 2).

Goals

• 수학적 귀납법의 두 단계(기초 단계, 귀납 단계)를 이해하고 다양한 등식과 부등식을 증명한다.
• 강한 귀납법과 정렬성(Well-ordering)의 관계를 파악하고 이를 소인수분해 등에 응용한다.
• 함수, 집합, 문자열을 재귀적으로 정의하고 구조적 귀납법으로 그 성질을 증명한다.
• 재귀 알고리즘의 동작 원리를 이해하고 프로그램의 부분 correctness를 검증한다.

Core Concepts

4.1 Mathematical Induction (수학적 귀납법)

모든 양의 정수에 대해 성립하는 명제 $P(n)$을 증명하는 표준적인 도구이다.

Definition

Principle of Mathematical Induction (수학적 귀납법의 원리): 양의 정수의 영역에서 $P(1)$이 참이고, 모든 양의 정수 $k$에 대해 $P(k) \to P(k+1)$이 참이면, 모든 양의 정수 $n$에 대해 $P(n)$은 참이다. (p.265)

$$[P(1) \wedge \forall k(P(k) \rightarrow P(k+1))] \rightarrow \forall n P(n)$$

• Basis Step (기초 단계): $P(1)$이 참임을 보인다.
• Inductive Step (귀납 단계): $P(k)$가 참이라고 가정(Inductive Hypothesis)했을 때, $P(k+1)$이 반드시 참임을 보인다.

4.2 Strong Induction and Well-Ordering (강한 귀납법과 정렬성)

기존 귀납법보다 더 강력한 가정을 사용하는 증명 방식이다.

Definition

Strong Induction (강한 귀납법): $P(1)$이 참이고, $1$부터 $k$까지의 모든 정수에 대해 $P(j)$가 참이라는 가정 하에 $P(k+1)$이 참임을 보이면, 모든 $n$에 대해 $P(n)$이 참이다. (p.284)

$$[P(1) \wedge \forall k(\bigwedge_{j=1}^{k} P(j) \rightarrow P(k+1))] \rightarrow \forall n P(n)$$

• Well-Ordering Property (정렬 원리): 비어 있지 않은 모든 비음수 정수의 집합은 반드시 최소 원소를 갖는다. (p.290)

4.3 Recursive Definitions (재귀적 정의)

객체 자신을 사용하여 객체를 정의하는 방식이다.

• Recursive Function: 초기값($f(0)$)을 지정하고, 이전 값을 이용하여 다음 값을 찾는 규칙을 제공한다. (p.296)
• Recursive Set: 기초 단계에서 초기 원소를 명시하고, 귀납 단계에서 기존 원소로부터 새로운 원소를 생성하는 규칙을 제시한다. (p.299)
• Structural Induction (구조적 귀납법): 재귀적으로 정의된 집합의 모든 원소가 특정 성질을 가짐을 증명할 때 사용한다. (p.304)

4.4 Recursive Algorithms (재귀 알고리즘)

문제를 더 작은 동일 문제의 인스턴스로 줄여서 해결하는 알고리즘이다. (p.311)

• Merge Sort (병합 정렬): 리스트를 절반으로 나누고 각각을 정렬한 뒤 병합하는 $O(n \log n)$ 복잡도의 알고리즘이다. (p.318)

4.5 Program Correctness (프로그램 정당성)

프로그램이 의도한 대로 동작함을 수학적으로 증명한다.

• Hoare Triple: $p\{S\}q$ 형식으로 표기하며, 초기 조건 $p$가 참일 때 프로그램 $S$가 종료되면 종료 조건 $q$가 참임을 의미한다. (p.323)
• Loop Invariant (루프 불변성): 루프 본체가 실행되기 전과 후에 항상 참으로 유지되는 성질이다. (p.326)

Key Theorems & Formulas

Theorem 1 (Lamé's Theorem)

조건: $a, b$가 $a \ge b$인 양의 정수일 때, 유클리드 호제법을 통해 $gcd(a, b)$를 구하는 데 필요한 나눗셈의 횟수 $n$.

결론:

$$n \le 5 \times (\text{decimal digits in } b)$$

유클리드 호제법의 시간 복잡도는 $O(\log b)$이다. (p.298)

Theorem 2 (Full Binary Trees)

조건: 높이가 $h$인 전진 이진 트리(Full Binary Tree) $T$의 정점 수 $n(T)$.

결론:

$$n(T) \le 2^{h+1} - 1$$

이 정리는 구조적 귀납법을 통해 증명된다. (p.306)

Worked Examples

Example 1: 등식의 증명 (4.1)

문제: 모든 양의 정수 $n$에 대해 $1 + 2 + \dots + n = \frac{n(n+1)}{2}$임을 증명하라.

핵심 단계:

1. Basis: $n=1 \to 1 = \frac{1(1+1)}{2}$이므로 참.
2. Hypothesis: $n=k$일 때 $S_k = \frac{k(k+1)}{2}$라고 가정.
3. Inductive Step: $S_{k+1} = S_k + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$.

요점: 귀납 단계에서 가정을 사용하여 $k+1$ 형태를 유도하는 것이 핵심이다.

Example 2: 우편 요금 문제 (4.2)

문제: 12센트 이상의 모든 우편 요금을 4센트와 5센트 우표로 만들 수 있음을 증명하라.

핵심 단계:

1. Basis: 12(4x3), 13(4x2+5), 14(4+5x2), 15(5x3)에 대해 성립함을 확인.
2. Strong Induction: $12, \dots, k$센트가 가능하다고 가정.
3. Step: $k+1$센트는 $(k-3)$센트 요금에 4센트 우표 하나를 추가하여 만들 수 있다. ($k-3 \ge 12$여야 하므로 기초 단계에서 4개를 확인한 것)

Example 3: Merge Sort (4.4)

문제: 리스트 $[8, 2, 4, 6, 9, 7, 10, 1, 5, 3]$을 정렬하라.

핵심 단계:

1. Divide: 각 리스트 원소가 1개가 될 때까지 이분 분할한다.
2. Merge: 정렬된 두 리스트의 가장 작은 원소를 비교하며 새로운 리스트를 만든다.
3. Complexity: 각 층에서 $O(n)$의 병합 작업이 일어나며 층수는 $\log n$이므로 전체 $O(n \log n)$.

Common Pitfalls

Pitfall

귀납 단계의 논리적 공백: $P(k) \to P(k+1)$ 증명 시, $k$의 범위에 따라 논리가 달라질 수 있다. 예를 들어 "모든 말의 색깔이 같다"는 가짜 증명에서는 $k=1 \to 2$로 넘어갈 때 두 세트의 교집합이 존재한다는 가정이 깨진다. (p.281)

Pitfall

루프 종료성 간과: 부분 정당성(Partial Correctness)만 증명하고 프로그램이 실제로 종료됨을 증명하지 않으면 전체 정당성을 보장할 수 없다. (p.323)

Connections

• 선행 개념: Ch. 1 기초 논리, Ch. 2 집합과 함수.
• 후속 개념: Ch. 7 점화식의 해법, Ch. 3 알고리즘의 복잡도 분석, Ch. 9 그래프 · Ch. 10 트리 이론.
• 응용 분야: 컴파일러 설계(재귀 구문 분석), 하드웨어 검증, 데이터 구조(트리 탐색).

Critical Notes

교재가 강조하는 것

• 귀납법은 공식이나 정리를 발견하는 도구가 아니라, 이미 알려진 추측을 증명하는 도구이다. (p.264)
• 수학적 귀납법, 강한 귀납법, 정렬 원리는 모두 동치(Equivalent)이다.

실제로 중요한 것

• Strong Induction의 필요성: $P(k)$만으로 $P(k+1)$을 설명할 수 없는 경우(예: 피보나치 수열, 소인수분해) 강한 귀납법을 자연스럽게 떠올려야 한다.
• Structural Induction: 컴퓨터 과학에서는 정수보다 트리나 문자열 같은 구조체에 대한 귀납법이 훨씬 빈번하게 사용된다.

교재가 생략하거나 얼버무리는 것

• 조르단 곡선 정리(Jordan Curve Theorem)와 같이 "직관적으로는 당연해 보이지만 증명이 매우 복잡한" 기하학적 명제들을 언급하며, 엄밀한 증명의 어려움을 시사한다. (p.288)