35주차 — 귀납법 종합: 오류 박물관 + 백지 시험 (7부 총정리)#
이 주의 길잡이
핵심 문장: 귀납 증명의 오류는 다섯 곳에 숨는다 — 기초, 보폭\(\cdot\)가정 범위, 전달의 첫 고리, 연결부, 가정 미사용.
이 주의 위치: 50주 과정의 35주차. 31~34주차(귀납\(\cdot\)강귀납\(\cdot\)점화)의 마지막 주 — 오류 다섯 관을 표로 굳히고, 가장 널리 알려진 가짜 귀납 증명(“모든 말은 같은 색”)을 해부한 뒤, 백지 시험으로 7부를 닫는다.
원서 대응: BoP(Book of Proof) 10장 종합 — 병행자 참고용. 원서 없이 읽을 수 있다.
이번 주 목표#
귀납 오류 박물관 5관을 차례로 읽고, 각 오류의 탐지법을 체크리스트로 만든다.
“모든 말은 같은 색” 역설을 무너지는 지점까지 정확히 해부한다.
백지 시험 20문항으로 7부(귀납법)를 수료한다 (권장 150분).
본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.
준비 운동 (34주차 복습)#
두 칸 모드(귀납 단계가 \(P(k)\)와 \(P(k-1)\)을 함께 쓰는 경우)의 귀납에 기초가 2개 필요한 이유를 쓰시오.
추측 \(\to\) 귀납 확정 사이클의 ④단계에서 가장 먼저 하는 일은 무엇인지 쓰시오.
카시니 항등식을 \(n = 3\)에서 검산하시오.
답
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관). 아래 확인 상자로 관 번호를 붙여 보자.
확인 1. 다음 답안이 무너진 곳은 몇 관인가. “명제: 모든 자연수 \(n\)에 대해 \(n^2 + n\)은 짝수이다. [귀납] \(k^2 + k\)가 짝수라고 가정하자. \((k+1)^2 + (k+1) = (k^2 + k) + 2(k+1)\)이므로 짝수이다. 따라서 모든 \(n\)에서 성립한다.”
답
1관(기초 누락)이다. 귀납 단계의 계산은 정확하지만 \(n = 1\)을 확인한 줄이 없다.
결론이 참인 명제라서 눈에 덜 띌 뿐, 논증의 구조는 31주차 문제 17의 “\(n = n+1\)”과
같다 — 고리만 있고 첫 고리를 걸 곳이 없다.
확인 2. 점화식 \(b_n = b_{n-1} + b_{n-2}\) (\(n \ge 3\))를 쓰는 귀납에서 기초를 \(P(1)\) 하나만 확인했다. 몇 관의 오류이며, 처음으로 근거를 잃는 \(n\)은 얼마인가?
답
2관(기초 부족)이다. 귀납 단계는 \(P(k+1)\)을 만들기 위해 \(P(k)\)와 \(P(k-1)\)을 함께
쓰므로 \(k + 1 \ge 3\), 곧 \(k \ge 2\)에서만 작동한다. 따라서 \(P(2)\)는 전달로 얻을 수
없고, 근거를 잃는 첫 자리는 \(n = 2\)다. 기초는 \(P(1)\)과 \(P(2)\) 두 개여야 한다.
확인 3. 3관과 4관은 둘 다 “전달이 안 된다”는 현상으로 보인다. 두 관을 가르는 기준을 한 문장으로 적어 보자.
답
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)\) — “임의의 두 말은 같은 색” — 가 거짓이므로 결과도 맞아떨어진다.
확인 4. 이 역설에서 \(P(1)\)과 \(P(2)\)는 각각 참인가 거짓인가. 그리고 무너진 것은 기초인가 전달인가?
답
\(P(1)\)은 참이다 — 말 1마리는 자기 자신과 같은 색이다. \(P(2)\)는 거짓이다 —
색이 다른 두 말이 실제로 존재한다. 따라서 무너진 것은 기초가 아니라 전달,
그중에서도 \(P(1) \Rightarrow P(2)\)라는 첫 고리 하나다. 이 역설을 “기초가 틀렸다”로
진단하는 경우가 많은데, 기초는 아무 문제가 없다.
교훈. 귀납 단계를 증명할 때는 “이 논증이 가장 작은 \(k\)에서도 작동하는가”를 반드시 별도로 점검한다. 일반적인 \(k\)의 그림을 그려 놓고 논증하면 작은 \(k\)의 퇴화 상황(겹침이 빔, 항이 없음, 분모가 사라짐)을 놓치기 쉽다.