S14주차 — 귀납법: 귀납 단계 안의 전진-후진

이 주의 길잡이

핵심 문장: 귀납 단계는 조건문 \(P(n) \Rightarrow P(n+1)\) 하나를 증명하는 일이고, 그 안에서는 전진-후진의 모든 절차가 그대로 작동한다 — 귀납이 새로 요구하는 것은 가정 \(P(n)\)을 어디서 소비하는가 하나뿐이다.

이 주의 위치: 1학기 20주 과정의 S14주차. 1권 31~35주차에서 서식으로 익힌 귀납법이 여기서 두 가지를 새로 얻는다 — 귀납 단계를 조건문 증명으로 분해하는 눈, 그리고 그 안에서 막혔을 때 무엇을 검사하는가의 절차. S7주차 문제 19에서 “999단계가 필요하다”고 적어 둔 특수화 사슬이 이번 주에 한 문장으로 대체된다.

원서 대응: Solow 12장. 주간 루틴 1일차에 원서 12장을 통독한 뒤 이 문서로 온다.

이번 주 목표

1. 귀납법을 특수화 사슬을 한 줄로 대신하는 근거로 다시 세운다 — 유한한 답안이 무한한 명제 목록을 덮는 통로가 어디인지 지목할 수 있다.

2. 귀납 단계 = 조건문 증명으로 분해한다: 출발점 \(P(n)\), 도착점 \(P(n+1)\), 그 사이는 S2~S3주차의 후진과 전진.

3. 가정 소비처를 만드는 표준 동작(쪼개기)을 익히고, 소비 점검 ㄱ\(\cdot\)ㄴ으로 자기 답안을 검사한다.

4. 약한 귀납\(\cdot\)강한 귀납\(\cdot\)최소 반례법 세 형태를 Solow의 언어로 정리하고, 셋 중 무엇을 고를지의 판정 기준을 세운다.

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

준비 운동 (S13주차 복습)

노트에 먼저 적은 뒤 아래를 읽는다.

1. “정확히 하나 존재한다”를 두 개의 게임으로 분해하시오. 각 게임의 이름과 도착점을 쓰시오.

2. 간접 유일성의 서식을 재현하시오 — S13주차에서 이 서식이 어느 기법을 다시 쓴 것이었는가.

3. 조건문 \(A \Rightarrow B\)를 증명할 때 답안의 첫 문장을 쓰시오 (S1주차). 이번 주 귀납 단계의 첫 문장이 정확히 그 문장이다.

이어서 다음 과제를 해 보자. 명제 “모든 자연수 \(n\)에 대해 \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\)이다”를 증명해 보자. 이 명제는 1권 31주차 예제 2.1에서 이미 증명한 그 명제다. 그러므로 과제를 이렇게 한정한다 — 답안을 적은 뒤, 그 답안에서 가정 \(P(n)\)이 정확히 어느 줄에서 쓰였는지 밑줄로 표시해 보자. 이미 아는 명제를 다시 꺼내는 이유는 §0의 마지막에서 밝힌다.

자주 나오는 세 가지 답

이 자리에서 나오는 답은 대개 다음 세 유형 중 하나다. 셋 다 1권 31~35주차를 제대로 익힌 사람에게서 나오는 답이고, 셋 다 이번 주가 메울 정확한 간격이 있다.

• 유형 1 — 1권 31주차의 서식을 그대로 재현한다. “기초 단계에서 \(n = 1\)을

확인하고, 귀납 단계에서 \(P(k)\)를 가정해 \(P(k+1)\)을 보인다”를 적고 계산까지 완주한다. 이 답안은 옳고 완전하다. 밑줄도 대개 정확한 자리에 그어진다. 빠진 것은 답안이 아니라 절차다 — 이 서식이 통하지 않는 명제 앞에서, 곧 계산이 막히는 자리에서 무엇을 먼저 검사할지가 아직 목록으로 정리되어 있지 않다. 이번 주의 몫은 그 목록을 만드는 일이다.

• 유형 2 — 값을 확인하고 사슬로 설명한다. \(n = 1, 2, 3, 4\)에서 등식이 맞는

것을 확인하고 “\(P(1)\)이 \(P(2)\)를 부르고 \(P(2)\)가 \(P(3)\)을 부르니 계속 이어진다”고 적는다. 사슬이 이어진다는 관찰은 옳고, 실제로 귀납 공리가 형식화하는 것이 그 관찰이다. 다만 그 서술 자체는 아직 유한하다 — S7주차 문제 19에서 \(P(4)\)를 얻는 데 특수화와 전건 긍정이 세 번씩 필요했고, \(P(1000)\)에는 999번이 필요했다. 답안의 줄 수가 유한한 이상 이 방식은 언제나 어느 \(N\)에서 끝난다. 그 유한한 답안을 무한한 목록으로 바꾸는 통로가 정확히 무엇인지가 §1.1의 주제다.

• 유형 3 — 가정을 쓰지 않고 결론을 다시 계산한다. 귀납 서식을 적어 놓고,

귀납 단계에서는 \(1 + 2 + \cdots + (n+1)\)을 등차수열의 합 공식으로 한 번에 계산해 버린다. 도착점을 정확히 의식한 것은 옳다. 그러나 밑줄을 그으려 하면 그을 자리가 없다 — 가정 \(P(n)\)이 답안 어디에도 등장하지 않는다. 이런 답안이 왜 귀납이 아닌지, 그리고 어떤 검사로 잡히는지가 §1.4의 주제다.

이번 주가 새로 주는 것. 세 유형을 늘어놓으면 이번 주의 몫이 도구가 아니라는 것이 보인다. 귀납법이라는 도구는 유형 1이 이미 쥐고 있다. 비어 있는 것은 두 가지다 — 유한한 답안이 무한을 덮는 통로가 어디인지(§1.1과 §1.4의 걸음 ④), 그리고 귀납 단계 안에서 막혔을 때 검사할 항목이 무엇인지(§1.4의 소비 점검과 §1.5의 쪼개기). 1권에서 서식으로 익힌 자리가 이번 주에 절차가 된다.

개념 — 귀납법

1 특수화만으로 밀어붙이면 어디서 막히는가

새 원리를 세우기 전에, S7주차까지의 도구만으로 한 과제를 밀어붙여 본다.

시도 — 특수화와 전건 긍정만으로

확보된 사실이 둘 있다. ① \(P(1)\)은 참이다. ② 모든 자연수 \(n\)에 대해 “\(P(n)\)이면 \(P(n+1)\)이다”가 참이다.

“②를 \(n = 1\)에 특수화하면 ‘\(P(1)\)이면 \(P(2)\)’를 얻는다. ①과 전건 긍정으로 \(P(2)\)를 얻는다.

②를 \(n = 2\)에 특수화하면 ‘\(P(2)\)이면 \(P(3)\)’을 얻는다. 방금 얻은 \(P(2)\)와 전건 긍정으로 \(P(3)\)을 얻는다.

②를 \(n = 3\)에 특수화하면 … 이렇게 계속하면 \(P(4)\), \(P(5)\), \(P(6)\), …”

여기서 답안이 끝나 버린다. 마지막 줄의 “…”이 근거가 아니기 때문이다.

확인 1. 위 답안이 실제로 확보한 명제는 어느 것들인가. 확보되지 않은 채 남는 것은 무엇인가.

답

확보된 것은 \(P(1)\)부터 답안이 실제로 적은 마지막 번호 \(P(N)\)까지의 유한 개다.

답안의 줄 수가 유한하고 한 줄이 한 칸씩만 전진하므로, 어떤 답안을 적어도

도달하는 곳은 어느 유한한 \(N\)이다. 남는 것은 \(P(N+1), P(N+2), \dots\) — 여전히

무한히 많다. S7주차 문제 19가 \(P(1000)\)에 999단계가 필요하다고 셌던 것이

정확히 이 사정이고, 그 문제의 마지막 물음(“이 사슬을 한 번에 처리하는 원리가

무엇인가”)이 이번 주로 넘어온 빚이다.

빚을 갚는 방법은 하나뿐이다. 사슬을 한 칸씩 걷는 대신, 사슬 전체를 한 번에 근거로 인정하는 문장을 근거 목록에 올린다. 그 문장이 귀납 공리다.

이 주 전체의 기준

이번 주에 새로 들어오는 것은 계산 기법이 아니라 근거 하나다. 그 근거는

“기저와 귀납 단계가 확보되면 목록 전체가 확보된다”는 한 문장이고, 답안에서

그 근거를 인용하는 자리는 마지막 한 줄이다. 나머지 — 기저 검증과 귀납 단계 —

는 전부 이미 아는 증명 기법으로 처리된다.

2 사례 표를 채워 보기

귀납 단계가 실제로 어떤 모양인지 보기 전에, 그 단계의 재료를 먼저 만들어 본다. 아래 표는 \(n\) 자리의 식과 \(n+1\) 자리의 식을 나란히 놓고, 오른쪽 식을 왼쪽 식이 통째로 들어 있는 꼴로 다시 쓰는 표다.

\(n\) 자리의 식	\(n+1\) 자리의 식	“\(n\) 자리의 식 \(+\) 나머지” 또는 “\(n\) 자리의 식 \(\times\) 나머지”로 다시 쓴 꼴
\(\sum_{k=1}^{n} k\)	\(\sum_{k=1}^{n+1} k\)	\(\left(\sum_{k=1}^{n} k\right) + (n+1)\)
\(2^n\)	\(2^{n+1}\)	\(\underline{\quad(1)\quad}\)
\(n!\)	\((n+1)!\)	\(\underline{\quad(2)\quad}\)
\(n^3 - n\)	\((n+1)^3 - (n+1)\)	\((n^3 - n) + \underline{\quad(3)\quad}\)

확인 2. 빈칸 (1)~(3)을 채우고, 네 줄이 공통으로 하는 일을 한 문장으로 적어 보자.

답

(1) \(2^n \cdot 2\) (2) \((n+1) \cdot n!\) (3) \(3n^2 + 3n\).

(3)의 유도: \((n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3n^2 + 3n\).

공통으로 하는 일: \(n+1\) 자리의 식을, \(n\) 자리의 식이 그대로 보이도록 쪼갠다.

식 자체에 새로운 것은 없다 — 전개와 묶기(근거 ③)뿐이다. 새로운 것은 이 쪼개기를

왜 하는가이고, 그 답이 §1.5에 있다.

이 관찰에 정식 이름과 형식을 붙인다.

정의 14.1 — 수학적 귀납법 (mathematical induction) [백지 암기 대상]

정수 \(n_0\) 이상의 각 정수 \(n\)마다 명제 \(P(n)\)이 정해져 있다고 하자. 다음 두 가지가 성립하면, \(n_0\) 이상의 모든 정수 \(n\)에 대해 \(P(n)\)이 참이다.

① 기저(base step): \(P(n_0)\)이 참이다.

② 귀납 단계(inductive step): \(n_0\) 이상의 임의의 정수 \(n\)에 대해, \(P(n)\)이 참이면 \(P(n+1)\)도 참이다.

표기 — \(P(n)\)

\(P(n)\)은 “\(n\)에 대한 명제”에 붙인 이름이고 “피 엔”이라고 읽는다. \(n\)을 하나

고정할 때마다 참\(\cdot\)거짓이 정해지는 문장 하나를 가리키므로, \(P(n)\) 자체는 수가

아니다. “\(P(3)\)”은 \(P(n)\)의 \(n\) 자리에 3을 넣어 만든 문장을 뜻한다. 1권 31~35주차는

귀납 변수를 \(k\)로 적었고 이 문서는 \(n\)으로 적는다 — 문자만 다르고 하는 일은 같다.

정의 14.1의 ①과 ②는 각각 하나의 증명 과제다. ①은 값을 넣어 계산하는 일이고, ②는 조건문 하나를 증명하는 일이다. 이번 주의 내용은 거의 전부 ②에 있다.

3 귀납 단계는 조건문 하나다

1권에서 서식의 한 칸이던 자리가 여기서 이름을 얻는다. 1권 31주차는 “귀납 단계”를 서식의 둘째 칸으로 익혔지만, 그 칸 안에서 하는 일이 무엇인지는 하나로 묶여 있었다. Solow의 언어로 다시 읽으면 그 칸은 통째로 조건문 \(P(n) \Rightarrow P(n+1)\)의 증명이고, S1~S3주차에서 세운 게임 관리가 그 안에서 그대로 작동한다.

	보통의 조건문 증명	귀납 단계
출발점 (가정)	\(A\)	\(P(n)\) — 임의로 고정한 한 \(n\)에서
도착점 (결론)	\(B\)	\(P(n+1)\)
개시 문장	“\(A\)라 하자”	“\(n \ge n_0\)인 정수 \(n\)을 하나 임의로 고정하고, \(P(n)\)이 참이라 하자”
몸통	정의 풀기 \(\cdot\) 후진 \(\cdot\) 전진 \(\cdot\) 선택 \(\cdot\) 구성	같음 — 새 기법이 들어오지 않는다
이 게임에만 있는 것	—	출발점의 식이 도착점의 식 안에 숨어 있다

마지막 줄이 귀납 단계의 특징을 전부 담고 있다. 보통의 조건문에서는 \(A\)와 \(B\)가 서로 다른 대상을 말하는 일이 많지만, 귀납 단계에서 \(P(n)\)과 \(P(n+1)\)은 같은 모양의 식을 한 칸 차이로 말한다. 그래서 후진의 첫 걸음이 언제나 같은 모양이 된다 — 도착점의 식을 출발점의 식이 보이도록 쪼갠다(§1.2에서 이미 해 본 동작이다).

확인 3. 귀납 단계에서 “\(P(n)\)이 참이라 하자”라고 적는 것은 증명할 것을 미리 가정하는 반칙이 아닌가. 한 문장으로 답해 보자.

답

반칙이 아니다. 증명 대상은 “모든 \(n \ge n_0\)에서 \(P(n)\)”이고, 귀납 단계에서

가정하는 것은 “임의로 고정한 하나의 \(n\)에서 \(P(n)\)”이다. 둘은 다른 문장이다.

게다가 귀납 단계가 주장하는 것은 \(P(n+1)\)의 참이 아니라 “\(P(n)\)이면 \(P(n+1)\)”이라는

조건문이다. 전건이 거짓인 행에서는 조건문이 자동으로 참이므로(1권 8주차 진리표 —

근거 ⑤, S1주차 §1.4의 책임 범위), 전건이 실제로는 언제나 거짓이라는 사실이 이

조건문의 참을 해치지 않는다 — 실제로 문제 17의 답안이 그런 경우다.

4 절차 해부 — 걸음마다 하는 일

귀납 답안은 네 걸음으로 적는다. 걸음 ③이 §1.3의 조건문 증명이고, 그 안이 다시 두 조각으로 나뉜다.

백지 암기 대상

귀납 답안의 4단 서식

① 이름 붙이기: “\(n\)에 대한 귀납법으로 증명한다. \(P(n)\)을 ‘…’이라 하자.”

② 기저 검증: “\(P(n_0)\): (좌변 계산) \(=\) (우변 계산)이므로 참이다.”

③ 귀납 단계: “\(n \ge n_0\)인 정수 \(n\)을 하나 임의로 고정하고, \(P(n)\)이 참이라 하자.” \(\to\) 쪼개기 \(\to\) 가정 소비 \(\to\) “따라서 \(P(n+1)\)이 참이다.”

④ 결론 선언: “기저와 귀납 단계에 의해 모든 \(n \ge n_0\)에서 \(P(n)\)이 참이다.”

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 이름 붙이기	귀납 변수와 명제 지정	무엇에 대한 귀납인지 정해지지 않아 \(P(n+1)\)이 어떤 문장인지 확정되지 않는다 — 문자가 두 개 이상인 명제에서 곧바로 어긋난다
② 기저 검증	목록의 시작점 확보	귀납 단계가 모두 참이어도 확보되는 명제가 하나도 없다 (아래 삭제 실험 1)
③-가 “\(n\)을 하나 임의로 고정”	귀납 단계의 범위 선언	일부 \(n\)에서만 전달이 보장되어 사슬이 그 자리에서 끊긴다 (문제 18)
③-나 가정 소비	\(P(n)\)의 등식을 실제로 대입	귀납 서식을 두른 다른 증명이 된다 (아래 삭제 실험 2)
③-다 도착 선언	\(P(n+1)\)에 정확히 닿았음을 확인	\(P(n+1)\)과 비슷한 다른 식에서 멈춰도 통과된다 (문제 7의 마지막 줄이 그 검사 지점이다)
④ 결론 선언	귀납 공리 인용	증명된 것은 \(P(n_0)\)과 조건문 하나뿐이고 원명제는 아직 증명되지 않은 상태로 남는다

걸음 삭제 실험 1 — 기저를 지우면. 걸음 ②를 지운 답안을 검사해 보자.

삭제 실험 1 — 기저가 없는 답안

명제: 모든 자연수 \(n\)에 대해 \(n = n + 1\)이다.

“\(P(n)\)을 ‘\(n = n+1\)’이라 하자. 자연수 \(n\)을 하나 임의로 고정하고, \(P(n)\)이 참이라 하자. 양변에 1을 더하면 \(n + 1 = n + 2\)이고, 이것이 \(P(n+1)\)이다. 따라서 귀납 단계가 모든 \(n\)에서 성립한다. 그러므로 모든 자연수 \(n\)에서 \(n = n+1\)이다.”

확인 4. 이 답안의 귀납 단계는 참인가. 명제는 참인가. 두 답이 어긋난다면 그 어긋남은 어디서 오는가.

답

귀납 단계는 참이다. “\(n = n+1\)이면 \(n+1 = n+2\)”는 양변에 1을 더하는

조작(근거 ③)만으로 유도되는 참인 조건문이고, 전건이 거짓이라는 사실은 조건문의

참을 해치지 않는다(확인 3). 그러나 명제는 거짓이다 — \(1 \neq 2\).

어긋남은 걸음 ②가 없다는 데서 온다. 기저 \(P(1)\)은 “\(1 = 2\)”이고 이것은 거짓이므로,

정의 14.1의 조건 ①이 성립하지 않는다. 조건 ② 하나만으로는 정의 14.1을 인용할

수 없고, 따라서 마지막 줄의 결론 선언에 근거가 없다. 이 답안은 1권 31주차 문제

17이자 1권 35주차 오류 박물관 1관의 사례이고, 이번 주 문제 17에서 다시 해부한다.

걸음 삭제 실험 2 — 가정 소비를 지우면. 이번에는 걸음 ③-나를 지운다.

삭제 실험 2 — 가정이 등장하지 않는 답안

명제: 모든 자연수 \(n\)에 대해 \(\sum_{k=1}^{n} (2k-1) = n^2\)이다.

“\(P(n)\)을 ‘\(\sum_{k=1}^{n}(2k-1) = n^2\)’이라 하자. (기저) \(n = 1\): 좌변 \(= 1\), 우변 \(= 1\)이므로 참이다. (귀납 단계) 자연수 \(n\)을 하나 임의로 고정하고, \(P(n)\)이 참이라 하자. \(\sum_{k=1}^{n+1}(2k-1)\)은 첫째 항 1부터 마지막 항 \(2n+1\)까지의 등차수열의 합이므로, 등차수열의 합 공식에 의해 \(\frac{(n+1)(1 + (2n+1))}{2} = (n+1)^2\)이다. 따라서 \(P(n+1)\)이 참이다. 그러므로 모든 \(n\)에서 성립한다.”

확인 5. 이 답안에서 가정 \(P(n)\)은 어느 줄에서 쓰였는가. 인용된 “등차수열의 합 공식”은 근거 목록의 몇 번인가.

답

\(P(n)\)은 어느 줄에서도 쓰이지 않았다. 개시 문장에서 선언만 되고 그대로 버려졌다.

인용된 등차수열의 합 공식은 근거 목록의 어디에도 없다 — 근거 ④에 오르려면 먼저

증명되어야 하는데, 그 공식의 특수한 경우가 바로 지금 증명하려는 명제다.

결함은 둘이 겹쳐 있다: 가정 미소비와 근거 없는 인용. 앞의 것은 1권 35주차

오류 박물관 5관이고, 뒤의 것은 S7주차 문제 18\(\cdot\)S11주차 문제 12에서 본 순환이다.

가정이 소비되지 않은 귀납은 S11주차의 무늬만 귀류와 같은 모양이다 — 그쪽은 부정

가정 \(\neg B\)가, 이쪽은 귀납 가정 \(P(n)\)이 유도 사슬에서 한 번도 소비되지 않는다.

삭제 실험 2가 잡아낸 것을 검사 항목으로 못 박는다.

백지 암기 대상

가정 소비 점검

ㄱ. 답안에 \(P(n)\)의 식이 그대로 등장하는 줄이 있는가?

ㄴ. 그 줄에서 \(P(n)\)의 등식(또는 부등식)을 실제로 대입했는가?

둘 중 하나라도 아니면 그 답안은 귀납이 아니다. 귀납 서식을 벗기고 남는 것이

곧 그 답안의 정체이고, 대개는 미완의 직접 증명이거나 순환이다.

확인 6. 삭제 실험 1의 답안에 소비 점검 ㄱ\(\cdot\)ㄴ을 걸어 보자. 걸리는가.

답

걸리지 않는다. ㄱ: “\(n = n+1\)”이 그대로 등장한다. ㄴ: 양변에 1을 더하는 조작이

그 등식을 실제로 소비한다. 소비 점검은 통과하는데도 답안이 무너진다는 것이

요점이다 — 이 점검은 걸음 ③-나만 검사하고 걸음 ②는 검사하지 않는다. 두 검사는

서로를 대신하지 않으므로 답안을 읽을 때 순서대로 둘 다 건다.

5 소비처 만들기 — 쪼개기의 표준 동작

소비 점검 ㄱ이 요구하는 것은 “\(P(n)\)의 식이 그대로 등장하는 줄”이다. 그 줄은 저절로 생기지 않는다. 도착점 \(P(n+1)\)의 식을 손으로 쪼개서 만들어야 하고, 그 쪼개기는 §1.2에서 이미 네 번 해 본 동작이다.

백지 암기 대상

쪼개기 — 소비처를 만드는 표준 동작

도착점의 식을 “\(P(n)\)의 식 + 나머지” 또는 “\(P(n)\)의 식 \(\times\) 나머지”로 다시 쓴다.

합이면 마지막 항을 떼어 낸다: \(\sum_{k=1}^{n+1} = \left(\sum_{k=1}^{n}\right) + (n{+}1\text{번째 항})\).

거듭제곱이면 한 인수를 떼어 낸다: \(a^{n+1} = a^n \cdot a\).

곱\(\cdot\)계승이면 마지막 인수를 떼어 낸다: \((n+1)! = (n+1) \cdot n!\).

나누어떨어짐이면 \(f(n)\) 덩어리가 보이도록 전개하고 재그룹한다: \(f(n+1) = f(n) + (\text{나머지})\).

쪼개기가 끝나면 그 줄에 \(P(n)\)의 식이 통째로 들어 있고, 다음 줄에서 가정의 등식을 대입하는 순간이 곧 소비처다. 귀납 단계에서 막히는 답안은 거의 전부 이 쪼개기가 없는 답안이다 — 소비할 자리를 만들지 않았으므로 소비할 수가 없다.

확인 7. \(P(n)\)이 “\(4 \mid (5^n - 1)\)”일 때, 도착점의 식 \(5^{n+1} - 1\)을 \(5^n - 1\)이 보이도록 쪼개 보자. 검산까지 한다.

답

\(5^{n+1} - 1 = 5 \cdot 5^n - 1 = 5(5^n - 1) + 4\).

검산: \(5(5^n - 1) + 4 = 5 \cdot 5^n - 5 + 4 = 5^{n+1} - 1\) ✓.

거듭제곱의 쪼개기(\(5^{n+1} = 5 \cdot 5^n\))를 먼저 하고, \(-1\)을 \(-5 + 4\)로 갈라

\(5^n - 1\) 덩어리를 완성한 것이다. 이 쪼개기가 §3 훈련 2의 몸통이 된다.

6 세 형태 — 약한 · 강한 · 최소 반례

정의 14.1의 귀납 단계는 직전 한 칸만 가정한다. 그것으로 부족한 명제가 있고, 같은 내용을 귀류 쪽에서 적는 서식도 있다. 세 형태를 한 표로 정리한다.

형태	귀납 단계에서 가정하는 것	이 형태를 고르는 신호
약한 귀납	\(P(n)\) 하나	\(P(n+1)\)이 직전 한 칸에만 의존한다
강한 귀납	\(P(n_0), P(n_0{+}1), \dots, P(n)\) 전부	\(P(n+1)\)이 직전이 아닌 이전 칸에 의존한다 — 분해형(합성수 \(n+1 = ab\))이거나 고정 보폭형(\(n+1\)을 \(n-3\)에서 만든다)
최소 반례법	(가정 대신) 반례 집합의 최소원 \(n^*\)을 잡고, \(n^*\)보다 작은 곳은 반례가 아님을 쓴다	결론이 “존재하지 않는다” 꼴이거나, 귀류의 개시가 더 자연스러운 경우

정의 14.2 — 강한 귀납법 (strong induction) [백지 암기 대상]

정수 \(n_0\) 이상의 각 정수 \(n\)마다 명제 \(P(n)\)이 정해져 있고, \(d\)는 1 이상의 정수(보폭)라 하자. 다음 두 가지가 성립하면, \(n_0\) 이상의 모든 정수 \(n\)에 대해 \(P(n)\)이 참이다.

① 기저: \(P(n_0), P(n_0+1), \dots, P(n_0 + d - 1)\)이 모두 참이다.

② 귀납 단계: \(n \ge n_0 + d - 1\)인 모든 정수 \(n\)에 대해, \(n_0 \le k \le n\)인 모든 \(k\)에서 \(P(k)\)가 참이면 \(P(n+1)\)도 참이다.

\(d = 1\)인 경우가 기저 하나\(\cdot\)범위 \(n \ge n_0\)의 보통 꼴이다.

두 조각이 서식의 어느 걸음에 붙는지는 하나씩 대응한다 — 조건 ①(기저 \(d\)개)은 걸음 ②가, 조건 ②(누적 가정 \(n_0 \le k \le n\)과 그 범위 \(n \ge n_0 + d - 1\))는 걸음 ③-가가 맡는다. 보폭 \(d\)를 ②의 범위에 적어 두는 이유는 훈련 3과 문제 19가 보여 준다 — 그 두 답안의 귀납 단계는 \(n \ge 10\), \(n \ge 15\)에서만 세워지고, \(n = n_0\)에서는 참조하는 항이 가정의 범위 아래로 떨어져 성립하지 않는다.

조각 삭제 실험 — 누적 가정을 지우면

조건 ②의 “\(n_0 \le k \le n\)인 모든 \(k\)”를 “\(P(n)\) 하나”로 줄이고 문제 13의

분해형을 적어 보자. \(n + 1 = 100 = 4 \cdot 25\)에서 참조하는 \(a = 4\)는 직전 칸

\(n = 99\)가 아니므로 \(P(n)\) 하나로는 덮이지 않는다. \(P(4)\)를 꺼내는 줄에 근거가

없어지고, 답안은 가정한 적 없는 것을 인용한 상태로 끝난다. 누적 범위는 그

인용 자격을 만들어 내는 조각이고, 이 조각을 지우면 분해형은 통째로 무너진다.

강한 귀납은 약한 귀납의 가정을 누적 확장한 것이고, 최소 반례법은 같은 내용을 귀류로 뒤집어 적은 것이다 — S11주차와 S12주차에서 본 귀류와 대우의 관계와 같은 모양이다. 셋이 하나의 원리(자연수의 최소원리)의 세 서술이라는 것은 1권 33주차 문제 14와 문제 20에서 확인했고, 이 과정에서는 그 원리를 근거 ④로 채택해 쓴다.

기저의 개수에는 규칙이 하나 붙는다. 보폭 \(d\)는 (도착 첨자 \(n+1\)) \(-\) (귀납 단계가 참조하는 가장 작은 첨자)이고, 기저를 \(d\)개 확인한다. 시작 부분의 \(d\)개는 전달 장치가 만들어 내지 못하기 때문이다(1권 33주차 §1.4의 보폭 규칙). 훈련 3은 \(n+1\)에서 \(n-2\)를 참조하므로 \(d = 3\), 문제 19는 \(n+1\)에서 \(n-3\)을 참조하므로 \(d = 4\), 피보나치(문제 15)는 \(n+2\)에서 \(n\)을 참조하므로 \(d = 2\)다.

주의 — 첨자가 등장하는 것과 가정을 소비하는 것은 다르다

1권 34주차 §1.5는 \(P(n)\)이 \(F_n\) 하나에 대한 문장인 상황에서, 첨자에 \(F_{k-1}\)이

보인다는 것만으로 보폭을 2로 세지 않는다는 좁은 용도로 “세는 대상은 소비하는

가정의 개수”라고 적었다. 그 문장은 그 맥락에서만 통한다. 훈련 3은 가정을

\(P(n-2)\) 하나만 소비하지만 보폭은 3이고, 문제 19도 \(P(n-3)\) 하나만 소비하지만

보폭은 4다. 소비하는 가정의 개수로 기저를 세면 두 문제 모두 기저가 하나가 되고,

확보되지 않은 자리를 남긴 채 결론을 선언하게 된다. 기저의 개수를 정하는 기준은

언제나 참조하는 가장 먼 첨자까지의 거리 하나다.

확인 8. 다음 세 명제에 세 형태 중 무엇이 자연스러운가. 각각 신호를 지목해 보자.

(가) 모든 자연수 \(n\)에서 \(\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\)

(나) 2 이상의 모든 정수는 소수이거나 소수들의 곱이다

(다) 12 이상의 모든 정수는 \(4a + 5b\) (\(a, b\)는 음이 아닌 정수) 꼴이다

답

(가) 약한 귀납. \(\sum^{n+1}\)은 \(\sum^{n}\)에 한 항을 더한 것이므로 의존이 직전

한 칸이다. (나) 강한 귀납 — 분해형. \(n+1\)이 합성수이면 \(n+1 = ab\)이고 \(a, b\)는

직전 칸이 아니라 훨씬 작은 값일 수 있어 \(P(n)\) 하나로는 덮이지 않는다.

(다) 강한 귀납 — 고정 보폭형. \(n+1\)을 만들 때 \(n - 3\)의 표현에 4를 더하므로

보폭이 4이고, 따라서 기저도 네 개(\(12, 13, 14, 15\))다. (다)는 1권 33주차 문제

12와 같은 명제이고 이번 주 문제 19에서 다시 다룬다.

7 근거 목록 갱신

근거의 칸은 이번 주에도 다섯 개다(S1주차 §1.7에서 ⑤가 목록에 올랐다). 이번 주가 채우는 것은 ①과 ④다.

근거	이번 주에 추가\(\cdot\)갱신되는 것	이번 주에는 이렇게 쓴다
① 정의	정의 14.1(수학적 귀납법) \(\cdot\) 정의 14.2(강한 귀납법)	명제 목록에 \(P(n)\)이라는 이름을 붙이고, 서식의 네 걸음을 지정한다. 몸통에서는 짝수\(\cdot\)홀수\(\cdot\)나누어떨어짐(1권 1~2주차)과 부등식의 기존 정의를 그대로 푼다
② 닫힘성	변화 없음	“\(m + n^2 + n\)은 정수이므로”를 별도 설명 없이 쓴다. 나누어떨어짐 귀납의 마지막 줄이 언제나 이 근거로 닫힌다
③ 등식\(\cdot\)부등식의 성질	변화 없음	쪼개기(전개\(\cdot\)재그룹\(\cdot\)묶기)와 대입이 전부 이 근거다. 부등식 귀납에서는 1권 16주차 (W2)(W3) 양변 연산과 (W6) 추이성이 연결 부등식을 잇는 데 쓰인다
④ 이미 증명한 명제\(\cdot\)채택한 사실	귀납 공리(정의 14.1의 결론부)가 결론 선언의 근거로 소비된다. 최소원리(1권 33주차 §1.5)는 최소 반례법의 개시 근거다. 몸통의 부품: 합성수의 분해(문제 13), 피보나치 점화식(문제 15), (W1) \(x^2 \ge 0\)(1권 16주차, 문제 16), 홀짝의 배타성(1권 22주차 문제 5, 예제 2.3 답안 2), 연속한 두 정수의 곱은 짝수(1권 1주차 문제 16)	“귀납 공리에 의해”\(\cdot\)”1권 33주차 최소원리에 의해”처럼 출처를 대고 한 줄로 끝낸다
⑤ 논리 규칙	변화 없음	조건문의 참\(\cdot\)거짓 판정을 진리표로 정당화한다(1권 8주차) — 확인 3과 문제 17 (a)가 이 근거를 쓰는 자리다

목록 밖의 것은 이번 주에도 근거가 되지 않는다.

확인 9. 어떤 답안에 다음 두 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) “기저와 귀납 단계에 의해 모든 자연수 \(n\)에서 \(P(n)\)이 참이다.”

(나) “등차수열의 합 공식에 의해 \(\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\)이다.”

답

(가) 허용 — 근거 ④. 인용하는 것은 정의 14.1이 주는 귀납 공리이고, 이 한 줄이

유한한 답안을 무한한 명제 목록으로 옮기는 유일한 통로다(§1.1).

(나) 불허. 그 공식은 근거 ④에 오른 적이 없고, 이번 주에는 오히려 증명 대상이다.

증명하려는 것을 근거로 인용하면 순환이 되고, 답안은 삭제 실험 2와 같은 자리에서

무너진다. 이 문장이 실제로 답안에 나타난 사례가 문제 12다.