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

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

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

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

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

## 이번 주 목표

1. 귀납법을 **특수화 사슬을 한 줄로 대신하는 근거**로 다시 세운다 — 유한한 답안이 무한한 명제 목록을 덮는 통로가 어디인지 지목할 수 있다.
1. **귀납 단계 = 조건문 증명**으로 분해한다: 출발점 $P(n)$, 도착점 $P(n+1)$, 그 사이는 S2~S3주차의 후진과 전진.
1. **가정 소비처**를 만드는 표준 동작(쪼개기)을 익히고, 소비 점검 ㄱ$\cdot$ㄴ으로 자기 답안을 검사한다.
1. 약한 귀납$\cdot$강한 귀납$\cdot$최소 반례법 세 형태를 Solow의 언어로 정리하고, 셋 중 무엇을 고를지의 판정 기준을 세운다.

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

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

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

1. "정확히 하나 존재한다"를 두 개의 게임으로 분해하시오. 각 게임의 이름과 도착점을 쓰시오.
1. 간접 유일성의 서식을 재현하시오 — S13주차에서 이 서식이 어느 기법을 다시 쓴 것이었는가.
1. 조건문 $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주차까지의 도구만으로 한 과제를 밀어붙여 본다.

:::{admonition} 시도 — 특수화와 전건 긍정만으로
:class: quotebox

확보된 사실이 둘 있다. ① $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)$, …"
:::

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

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

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

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

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

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

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

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

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

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

:::{admonition} 이 주 전체의 기준
:class: quotebox

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

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

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

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

### 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}$ |

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

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

(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) [백지 암기 대상]

:::{container} quotebox
정수 $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)$도 참이다.
:::

:::{admonition} 표기 — $P(n)$
:class: quotebox

$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에서 이미 해 본 동작이다).

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

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

반칙이 아니다. 증명 대상은 "**모든** $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의 조건문 증명이고, 그 안이 다시 두 조각으로 나뉜다.

:::{admonition} 백지 암기 대상
:class: keybox

**귀납 답안의 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 — 기저를 지우면.** 걸음 ②를 지운 답안을 검사해 보자.

:::{admonition} 삭제 실험 1 — 기저가 없는 답안
:class: quotebox

명제: 모든 자연수 $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$이다."
:::

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

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

귀납 단계는 **참**이다. "$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 — 가정 소비를 지우면.** 이번에는 걸음 ③-나를 지운다.

:::{admonition} 삭제 실험 2 — 가정이 등장하지 않는 답안
:class: quotebox

명제: 모든 자연수 $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$에서 성립한다."
:::

:::{container} quotebox
**확인 5.** 이 답안에서 가정 $P(n)$은 어느 줄에서 쓰였는가. 인용된 "등차수열의 합 공식"은 근거 목록의 몇 번인가.
:::

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

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

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

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

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

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

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

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

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

:::{admonition} 백지 암기 대상
:class: keybox

**가정 소비 점검**

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

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

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

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

:::{container} quotebox
**확인 6.** 삭제 실험 1의 답안에 소비 점검 ㄱ$\cdot$ㄴ을 걸어 보자. 걸리는가.
:::

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

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

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

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

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

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

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

:::{admonition} 백지 암기 대상
:class: keybox

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

도착점의 식을 "$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)$의 식이 통째로 들어 있고, 다음 줄에서 가정의 등식을 대입하는 순간이 곧 소비처다. 귀납 단계에서 막히는 답안은 거의 전부 이 쪼개기가 없는 답안이다 — 소비할 자리를 만들지 않았으므로 소비할 수가 없다.

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

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

$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) [백지 암기 대상]

:::{container} quotebox
정수 $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$에서는 참조하는 항이 가정의 범위 아래로 떨어져 성립하지 않는다.

:::{admonition} 조각 삭제 실험 — 누적 가정을 지우면
:class: quotebox

조건 ②의 "$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$다.

:::{admonition} 주의 — 첨자가 등장하는 것과 가정을 소비하는 것은 다르다
:class: quotebox

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

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

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

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

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

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

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

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

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

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

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

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

(가) 약한 귀납. $\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)가 이 근거를 쓰는 자리다 |

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

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

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

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

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

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

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

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

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

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