# 35주차 — 귀납법 종합: 오류 박물관 + 백지 시험 (7부 총정리)

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 귀납 증명의 오류는 다섯 곳에 숨는다 — 기초, 보폭$\cdot$가정 범위, 전달의 첫 고리, 연결부, 가정 미사용.

**이 주의 위치**: 50주 과정의 35주차. 31~34주차(귀납$\cdot$강귀납$\cdot$점화)의 마지막 주 — 오류 다섯 관을 표로 굳히고, 가장 널리 알려진 가짜 귀납 증명("모든 말은 같은 색")을 해부한 뒤, 백지 시험으로 7부를 닫는다.

**원서 대응**: BoP(Book of Proof) 10장 종합 — 병행자 참고용. 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. **귀납 오류 박물관** 5관을 차례로 읽고, 각 오류의 탐지법을 체크리스트로 만든다.
1. "모든 말은 같은 색" 역설을 무너지는 지점까지 정확히 해부한다.
1. **백지 시험 20문항**으로 7부(귀납법)를 수료한다 (권장 150분).

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (34주차 복습)

1. 두 칸 **모드**(귀납 단계가 $P(k)$와 $P(k-1)$을 함께 쓰는 경우)의 귀납에 기초가 2개 필요한 이유를 쓰시오.
1. 추측 $\to$ 귀납 확정 사이클의 ④단계에서 가장 먼저 하는 일은 무엇인지 쓰시오.
1. 카시니 항등식을 $n = 3$에서 검산하시오.

:::{admonition} 답
:class: quotebox dropdown

**1.** 귀납 단계가 $P(k)$와 $P(k-1)$ 두 칸을 함께 쓰므로, 전달 장치는 두 칸이 이미 확보된 곳에서만 작동한다. 기초가 하나뿐이면 두 번째 항에서 이미 근거가 없다.

**2.** 점화식 대입이다. 추측한 닫힌 꼴을 $a_{k+1}$에 바로 넣는 것이 아니라, 점화식으로 $a_{k+1}$을 $a_k$로 바꾼 뒤에 귀납 가정을 투입한다.

**3.** $F_2 F_4 - F_3^2 = 1 \cdot 3 - 2^2 = -1 = (-1)^3$ ✓.
:::

### 자주 나오는 세 가지 답 — 1번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 규칙만 되풀이하기.** "보폭이 2이니까 기초도 2개"라고 적는다. 규칙

자체는 정확하고 34주차 §1.5가 그렇게 굳혔다(단, 세는 대상은 첨자가 아니라 **소비하는 가정**의 개수라는 단서가 붙는다 — 34주차 §1.5). 빠진 것은 그 규칙이 어디서 오는지다 — 규칙을 외운 답안은 보폭이 2가 아닌 15번 같은 문제(보폭 1인데 기초 2개)에서 기초 개수를 다시 틀린다.

- **유형 2 — 초기 조건의 개수로 답하기.** "수열 정의가 $b_1$과 $b_2$를 주니까

기초도 2개"라고 적는다. 관찰은 정확하다 — 두 칸 점화는 실제로 초기 조건 두 개를 요구한다. 다만 그것은 수열이 정의되기 위한 조건이고, 기초 개수를 정하는 것은 **귀납 단계가 작동하는 범위**다. 두 조건이 늘 같은 수인 것은 아니다.

- **유형 3 — 백지.** 무엇을 세어야 하는지가 정해져 있지 않아 손이 나가지 않는다.

셈은 기계적이다. 귀납 단계의 등식 $b_{k+1} = b_k + b_{k-1}$은 $k+1 \ge 3$에서만 뜻을 가지므로 이 장치가 만들어 내는 것은 $P(3), P(4), \dots$뿐이고, 남는 $P(1)$과 $P(2)$는 직접 확인하는 수밖에 없다. 이것이 기초 2개의 이유다.

## 개념 — 귀납 오류 박물관

### 1 오류 박물관 5관 [백지 암기 대상]

| **관** | **오류** | **대표 사례** | **탐지 질문** |
|---|---|---|---|
| 1관 | **기초 누락** | "$n = n+1$" (31주차 문제 17) | 기초를 실제로 계산$\cdot$확인했는가? |
| 2관 | **기초 부족 / 가정 범위 초과** | 두 칸 점화에 기초 1개 (33주차 문제 17); 보통 귀납으로 선언해 놓고 $P(k-1)$까지 사용 (34주차 문제 17 — 결함 2개: 기초 1개 + 가정 범위 초과) | 귀납 단계가 **소비하는 가정**이 몇 개인가(첨자에 $F_{k-1}$이 보이는 것과 $P(k-1)$을 가정으로 쓰는 것은 다르다 — 34주차 §1.5). 그만큼 기초가 있는가? 귀납 단계가 실제로 쓴 과거가 선언한 가정 안에 있는가($P(k)$만 가정하고 $P(k-1)$을 쓰지 않았는가)? |
| 3관 | **전달의 첫 고리 붕괴** | 모든 말은 같은 색 (§1.2) | $P(k) \Rightarrow P(k+1)$이 **모든** $k$에서 성립하는가 — 특히 가장 작은 $k$에서? |
| 4관 | **연결 부등식 생략** | "$2k^2 \ge (k+1)^2$은 당연" (32주차 문제 17) | 귀납 가정이 데려다준 중간값에서 목표까지의 다리를 실제로 놓았는가? |
| 5관 | **귀납 가정 미사용** | 귀납 껍데기 속 직접 증명 | "(귀납 가정)" 표시가 본문에 있는가? 없다면 귀납이 필요했는가? |

다섯 관은 답안을 읽는 순서와 같다 — 기초(1관$\cdot$2관) $\to$ 전달의 시작(3관) $\to$ 전달의 중간(4관) $\to$ 답안 전체(5관). 아래 확인 상자로 관 번호를 붙여 보자.

:::{container} quotebox
**확인 1.** 다음 답안이 무너진 곳은 몇 관인가. "명제: 모든 자연수 $n$에 대해 $n^2 + n$은 짝수이다. [귀납] $k^2 + k$가 짝수라고 가정하자. $(k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)$이므로 짝수이다. 따라서 모든 $n$에서 성립한다."
:::

:::{admonition} 답
:class: quotebox dropdown

1관(기초 누락)이다. 귀납 단계의 계산은 정확하지만 $n = 1$을 확인한 줄이 없다.

결론이 참인 명제라서 눈에 덜 띌 뿐, 논증의 구조는 31주차 문제 17의 "$n = n+1$"과

같다 — 고리만 있고 첫 고리를 걸 곳이 없다.
:::

:::{container} quotebox
**확인 2.** 점화식 $b_n = b_{n-1} + b_{n-2}$ ($n \ge 3$)를 쓰는 귀납에서 기초를 $P(1)$ 하나만 확인했다. 몇 관의 오류이며, 처음으로 근거를 잃는 $n$은 얼마인가?
:::

:::{admonition} 답
:class: quotebox dropdown

2관(기초 부족)이다. 귀납 단계는 $P(k+1)$을 만들기 위해 $P(k)$와 $P(k-1)$을 함께

쓰므로 $k + 1 \ge 3$, 곧 $k \ge 2$에서만 작동한다. 따라서 $P(2)$는 전달로 얻을 수

없고, 근거를 잃는 첫 자리는 $n = 2$다. 기초는 $P(1)$과 $P(2)$ 두 개여야 한다.
:::

:::{container} quotebox
**확인 3.** 3관과 4관은 둘 다 "전달이 안 된다"는 현상으로 보인다. 두 관을 가르는 기준을 한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

3관은 전달 논증이 어떤 작은 $k$에서 **실제로 성립하지 않는** 경우이고,

4관은 전달 논증의 한 단계를 **증명하지 않고** 넘어간 경우다. 3관은 거짓인 고리,

4관은 아직 증명되지 않은 고리다. 4관은 확인해 보면 참인 경우도 많다

(32주차 문제 17의 $2k^2 \ge (k+1)^2$이 그런 사례로, $k \ge 3$에서 실제로 참이다)

— 그래도 확인 전까지는 증명이 아니다.
:::

### 2 특별전 — "모든 말은 같은 색" 해부

**주장.** 모든 $n$에 대해, 임의의 말 $n$마리는 전부 같은 색이다. (참이라면 세상의 모든 말이 같은 색이라는 결론이 나온다.)

**가짜 증명.** [기초] $n = 1$: 말 1마리는 자기 자신과 같은 색 ✓. [귀납] 임의의 $k$마리가 같은 색이라고 가정하자. 말 $k+1$마리가 있을 때: 앞의 $k$마리 $\{1, \dots, k\}$는 귀납 가정에 의해 같은 색이고, 뒤의 $k$마리 $\{2, \dots, k+1\}$도 귀납 가정에 의해 같은 색이다. 두 무리는 말 $2, \dots, k$를 **공유**하므로, 공유 말을 다리 삼아 전체 $k+1$마리가 같은 색이다. $\blacksquare$(?)

**해부.** 귀납 단계의 다리는 "공유 말"인데, 공유 무리 $\{2, \dots, k\}$는 $k \ge 2$일 때만 비어 있지 않다. **$k = 1$일 때**는 앞 무리가 $\{1\}$, 뒤 무리가 $\{2\}$이고 공유 무리가 공집합이므로 두 무리를 이을 다리가 없다. 즉 전달 장치는 $k \ge 2$에서만 작동하고, **$P(1) \Rightarrow P(2)$라는 첫 고리가 성립하지 않는다**. 기초 $P(1)$은 참이고 $P(2) \Rightarrow P(3) \Rightarrow \cdots$도 전부 유효하지만, $P(2)$에 도달할 방법이 없으므로 그 뒤는 전부 근거를 잃는다. 실제로 $P(2)$ — "임의의 두 말은 같은 색" — 가 거짓이므로 결과도 맞아떨어진다.

:::{container} quotebox
**확인 4.** 이 역설에서 $P(1)$과 $P(2)$는 각각 참인가 거짓인가. 그리고 무너진 것은 기초인가 전달인가?
:::

:::{admonition} 답
:class: quotebox dropdown

$P(1)$은 참이다 — 말 1마리는 자기 자신과 같은 색이다. $P(2)$는 거짓이다 —

색이 다른 두 말이 실제로 존재한다. 따라서 무너진 것은 기초가 아니라 전달,

그중에서도 $P(1) \Rightarrow P(2)$라는 첫 고리 하나다. 이 역설을 "기초가 틀렸다"로

진단하는 경우가 많은데, 기초는 아무 문제가 없다.
:::

**교훈.** 귀납 단계를 증명할 때는 "**이 논증이 가장 작은 $k$에서도 작동하는가**"를 반드시 별도로 점검한다. 일반적인 $k$의 그림을 그려 놓고 논증하면 작은 $k$의 퇴화 상황(겹침이 빔, 항이 없음, 분모가 사라짐)을 놓치기 쉽다.