03. Proof by Mathematical Induction

1. 수학적 귀납법이란?

우리가 일상에서 쓰는 귀납적 사고는 경험에 기반한다. "내가 본 백조는 다 흰색이었으니 모든 백조는 희다"는 식이다. 그런데 이건 반례 하나(검은 백조)로 무너진다. 경험적이고 논리적으로 엄밀하지 않다.

반면 수학적 귀납법(Mathematical Induction) 은 정수에 관한 명제를 엄밀하게 증명하는 기법이다. 무한히 많은 경우를 하나하나 확인하는 대신, 단 두 단계만으로 전체를 논리적으로 보장한다.

2. 구조: 세 단계

목표: P(n)이 모든 n ≥ n₀에 대해 참임을 증명한다.

① Base case: n = n₀일 때 P(n₀)가 참임을 직접 보인다. 보통 좌변과 우변에 값을 대입해서 같음을 확인한다.

② Induction hypothesis: 임의의 k에 대해 P(k)가 참이라고 가정한다.

③ Induction step: P(k)가 참이라는 가정 하에, P(k+1)도 참임을 증명한다. 즉 P(k) → P(k+1)이 성립함을 보인다.

첫 번째 도미노가 쓰러지고(base case), 앞 도미노가 쓰러지면 다음도 쓰러진다는 규칙을 보이면(induction step) — 전부 쓰러진다.

3. 왜 P(k)가 참이라고 가정해도 되는가?

Induction step에서 P(k)를 참이라고 가정하고 시작하는 게 왜 논리적으로 타당할까?

P → Q (implication)의 진리표를 보면:

P	Q	P→Q
T	T	T
T	F	F
F	T	T
F	F	T

P→Q가 거짓이 되는 경우는 딱 하나, P가 참인데 Q가 거짓인 경우뿐이다. P가 거짓이면 Q가 어떻든 P→Q는 자동으로 참이 된다.

직관적으로 이해하면: "시험에서 100점을 맞으면 아이패드를 사줄게." 존이 100점을 못 맞으면, 아이패드를 안 사줘도 약속을 어긴 게 아니다. 조건(P)이 거짓이면 약속(P→Q) 자체는 유효하다.

따라서 P(k) → P(k+1)을 증명할 때, P(k)가 거짓인 경우는 신경 쓰지 않아도 된다. P(k)가 참일 때 P(k+1)도 참인지만 보이면 충분하다. 그래서 induction hypothesis에서 P(k)를 참이라고 가정하고 시작하는 것이다.

4. 예제: 2의 거듭제곱의 합

Theorem: ∑(i=0~n-1) 2^i = 2^n - 1 이 모든 n ≥ 0에 대해 성립한다.


Base case (n = 0)
좌변은 empty sum이므로 0, 우변은 2⁰ - 1 = 0. 성립한다.
(empty sum: 합산 범위가 말이 안 되는 경우, 관례적으로 0으로 정의한다.)

Induction hypothesis
P(n): ∑(i=0~n-1) 2^i = 2^n - 1 이 참이라고 가정한다.

Induction step
P(n+1)의 좌변 ∑(i=0~n) 2^i 을 쪼개면:

∑(i=0~n-1) 2^i + 2^n

= (2^n - 1) + 2^n [induction hypothesis 적용]

= 2·2^n - 1

= 2^(n+1) - 1

이는 P(n+1)의 우변과 같다. 따라서 P(n) → P(n+1)이 성립하고, 귀납법에 의해 모든 n ≥ 0에 대해 참이다.

5. 응용: 비둘기집 원리 증명

수학적 귀납법은 숫자 공식뿐 아니라 비수치적 명제에도 적용된다. 비둘기집 원리가 대표적인 예다. 비둘기집 원리에는 귀납 변수 n이 명시되어 있지 않아서, 먼저 P(n)을 다음과 같이 재정의한다.


P(n): |X| = n이고 |X| > |Y|인 임의의 유한 집합 X, Y에 대해, f: X → Y이면 f(x₁) = f(x₂)인 서로 다른 x₁, x₂ ∈ X가 존재한다.


Base case (n = 2)
|X| = 2, |Y| = 1이면 두 원소가 반드시 같은 곳으로 매핑된다. P(2) 성립.

Induction step (경우 분석 활용)
|X| = n+1인 경우, 임의의 원소 x를 하나 골라 두 가지 경우로 나눈다.

• Case 1: x와 같은 값으로 매핑되는 다른 원소 x'가 존재한다 → 바로 P(n+1) 성립.
• Case 2: 그런 x'가 없다 → x와 f(x)를 제거하면 크기 n짜리 문제로 줄어든다. Induction hypothesis에 의해 P(n)이 참이므로, 남은 집합에서도 조건을 만족하는 쌍이 존재한다 → P(n+1) 성립.

두 경우 모두 P(n+1)이 성립하므로, 귀납법에 의해 모든 n ≥ 2에 대해 비둘기집 원리가 증명된다.

6. 주의할 점

• Base case를 빠뜨리거나 틀리면 전체 증명이 무너진다.
• Induction step이 모든 k에 대해 성립하는지 꼼꼼히 확인해야 한다.
• 귀납 변수 n이 명시되지 않은 경우, P(n)을 어떻게 정의할지부터 고민해야 한다.