# 35주차 · 강의 — 예제 · 연습 · 해설

## 백지 시험 (31~34주차, 20문항)

**규칙.** 교재를 덮고 150분 안에 푼다. 귀납 답안에는 [기초]/[귀납]과 "(귀납 가정)" 표시를 반드시 단다. 부등식 귀납에서는 연결 부등식을 별도의 줄로 표시한다.

### 기본 ●○○

**1.** [백지] (a) 수학적 귀납법의 원리 (b) 강한 귀납법의 원리 (c) 최소원리를 각각 진술하시오.

**2.** 모든 자연수 $n$에 대해 $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$임을 귀납법으로 증명하시오.

**3.** 모든 자연수 $n$에 대해 $1 + 3 + 5 + \cdots + (2n-1) = n^2$임을 귀납법으로 증명하시오.

**4.** $a_1 = 1$, $a_{n+1} = a_n + 5$로 정의된 수열의 닫힌 꼴을 추측하고 귀납으로 확정하시오.

**5.** 실험으로 기초 위치를 찾으시오 (증명 불필요): "$2^n > 10n$"은 어느 자연수부터 계속 성립하는가? ($n = 1, \dots, 7$ 대입)

**6.** 오류 박물관 1~5관의 이름(오류 유형)을 쓰고, 각 관의 탐지 질문을 한 줄씩 쓰시오.

### 표준 ●●○

**7.** 모든 자연수 $n$에 대해 $\displaystyle \sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}$임을 증명하시오.

**8.** $n \ge 4$인 모든 정수에 대해 $2^n \ge n^2$임을 증명하시오 (32주차 예제 2.1 백지 재현 — 연결 부등식 포함).

**9.** 모든 자연수 $n$에 대해 $9 \mid (10^n - 1)$임을 귀납법으로 증명하시오.

**10.** $a_1 = 2$, $a_{n+1} = 3a_n$의 닫힌 꼴을 추측하고 귀납으로 증명하시오.

**11.** 모든 자연수 $n$에 대해 $F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$임을 증명하시오 (짝수 번째 피보나치의 합).

**12.** $n \ge 12$인 모든 정수는 $3a + 7b$ ($a, b \ge 0$) 꼴임을 강한 귀납법으로 증명하시오 (기초 몇 개가 필요한지부터 판단할 것).

**13.** "모든 말은 같은 색" 가짜 증명을 요약해 쓰고, 전달이 무너지는 정확한 지점($k$ 값과 이유)을 해부하시오.

**14.** 연속한 두 피보나치 수는 서로소임을 귀납법으로 증명하시오 (34주차 문제 12 백지 재현).

### 도전 ●●●

**15.** $n \ge 1$인 모든 자연수에 대해 $3^n > n \cdot 2^n$임을 귀납법으로 증명하시오. (기초 위치와 개수를 실험으로 정하고, 연결 부등식 $3k \ge 2(k+1)$의 성립 범위를 확인하시오)

**16.** "모든 자연수 $n$에 대해 $n^2 + n$은 짝수"를 **최소 반례법**으로 증명하시오 (1주차 문제 16의 명제를 자연수로 제한한 형태의 세 번째 증명 — 귀납 없이 최소원리로).

**17.** (진단 — 결함 2개) 다음 답안의 결함을 지적하고 수정하시오.

:::{container} quotebox
"명제: $n \ge 1$에서 $4^n > n^2 + 3$. [기초] $n=1$: $4 > 4$는 성립하지 않으므로 $n = 2$: $16 > 7$ ✓부터 시작한다. [귀납] $4^k > k^2 + 3$ 가정. $4^{k+1} = 4 \cdot 4^k > 4(k^2+3)$이고, $4(k^2+3)$은 $(k+1)^2 + 3$보다 크니까 성립한다. $\blacksquare$"
:::

**18.** (진단 — 5관) 다음 답안을 진단하시오: 논리적 오류는 없는가? 그런데 왜 "나쁜 답안"인가? 어떻게 고쳐야 하는가?

:::{container} quotebox
"명제: 모든 자연수 $n$에 대해 $6 \mid (n^3 + 5n)$. 증명: 귀납법. [기초] $n=1$: $6 \mid 6$ ✓. [귀납] $6 \mid (k^3 + 5k)$ 가정. $(k+1)^3 + 5(k+1) = k^3 + 3k^2 + 8k + 6$. 그런데 $k^3 + 5k = k(k^2+5)$에서 $k$ 홀짝 케이스와 mod 3 케이스로 $k^3 + 5k = (k^3 - k) + 6k$이고 $6 \mid (k^3 - k)$(30주차)이므로 $6 \mid (k^3+5k)$ — 즉 임의의 $k+1$에서도 같은 논증으로 $6 \mid ((k+1)^3 + 5(k+1))$. $\blacksquare$"
:::

**19.** 모든 자연수 $n$에 대해 $3 \mid (n^3 + 2n)$임을 귀납법으로 증명하시오.

**20.** (서술) 자신의 "귀납 답안 자가 점검 체크리스트"를 다섯 항목(박물관 5관 대응)으로 작성하고, 이번 시험에서 실제로 걸린(틀릴 뻔한) 지점이 어느 관이었는지 기록하시오.

## 백지 복습 체크리스트 (시험 후)

- [ ] 세 원리(귀납$\cdot$강귀납$\cdot$최소원리)를 정확히 진술했다 (1번).
- [ ] 말 역설의 붕괴 지점($P(1) \to P(2)$)을 해부했다 (13번).
- [ ] 부등식 귀납(8$\cdot$15번)에서 연결 부등식을 별도 표시했다.
- [ ] 진단 문제(17$\cdot$18번)에서 오류를 빠짐없이 짚었다 — 17번은 **두 개**(명제 범위 불일치 + 4관), 18번은 5관.
- [ ] 오류 체크리스트 5항목을 자기 언어로 만들었다 (20번).

## 해설

틀린 문제는 **접근**만 읽고 재시도한 뒤 **풀이**를 확인한다.

### 문제 1

**접근.** 세 원리는 각각 31주차 §1.3, 33주차 §1.3$\cdot$§1.5의 암기 상자다. 채점의 초점은 낱말 하나하나에 있다 — 조각이 하나 빠지면 원리가 무엇을 보장하지 못하게 되는지까지 짚는다.

**풀이.** (a) **수학적 귀납법의 원리.** 자연수에 대한 명제 $P(n)$에 대해 ① $P(1)$이 참이고 ② 모든 $k \ge 1$에 대해 "$P(k)$가 참이면 $P(k+1)$도 참"이라는 것, 이 둘이 증명되면 모든 자연수 $n$에 대해 $P(n)$이 참이다. (b) **강한 귀납법의 원리.** ① $P(1)$이 참이고(필요하면 $P(1), P(2), \dots, P(n_0)$ 여러 개), ② 모든 $k$에 대해 "$P(1), P(2), \dots, P(k)$가 **전부** 참이면 $P(k+1)$도 참"이면, 모든 자연수 $n$에 대해 $P(n)$이 참이다. (c) **최소원리.** 공집합이 아닌 자연수의 부분집합은 반드시 최소원소를 가진다. (음이 아닌 정수의 부분집합에서도 같다.)

**복기.** (b)에서 "$P(1)$부터 $P(k)$까지 전부"를 "$P(k)$"로 줄여 쓰면 보통 귀납법이 되어, 12번처럼 여러 칸 과거를 참조하는 증명이 근거를 잃는다. (c)에서 "공집합이 아닌"을 빠뜨리면 원소가 없는 집합에 최소원소를 요구하게 되어 진술 자체가 거짓이 되고, "자연수의"를 빠뜨리면 $\{x \in \mathbb{Q} : x > 0\}$이 반례가 된다.

### 문제 2

**접근.** 31주차 예제 2.1과 같은 명제다. 합 공식의 귀납은 언제나 같은 두 동작으로 끝난다 — 좌변에서 마지막 항 $(k+1)$을 떼어내 귀납 가정을 끼우고, 남은 식을 $(k+1)$로 묶어 목표 꼴을 만든다.

**풀이.** **[기초]** $n = 1$: 좌변은 $1$, 우변은 $\frac{1 \cdot 2}{2} = 1$이므로 양변이 같다 ✓. **[귀납]** $k \ge 1$인 정수 $k$에 대해 $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$라고 가정하자. 목표는 $1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$이다.

$$
1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) \ \text{(귀납 가정)} = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}
$$

곧 $P(k+1)$이 참이다. 귀납법의 원리에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$

**복기.** 검산: $n = 4$에서 좌변 $1+2+3+4 = 10$, 우변 $\frac{4 \cdot 5}{2} = 10$ ✓.

### 문제 3

**접근.** 좌변은 홀수를 작은 것부터 더한 것이고, $n$번째 홀수가 $2n - 1$이다. $P(k+1)$의 좌변에서 마지막 항은 $2(k+1) - 1 = 2k+1$이다.

**풀이.** **[기초]** $n = 1$: 좌변은 $1$, 우변은 $1^2 = 1$ ✓. **[귀납]** $1 + 3 + \cdots + (2k-1) = k^2$이라고 가정하자. 목표는 $1 + 3 + \cdots + (2k+1) = (k+1)^2$이다.

$$
1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1) \ \text{(귀납 가정)} = (k+1)^2
$$

$\blacksquare$

**복기.** 검산: $n = 3$에서 $1 + 3 + 5 = 9 = 3^2$ ✓. 마지막 항을 $2k - 1$ 그대로 두고 계산하는 경우가 있는데, 도착점의 좌변은 $n$ 자리에 $k+1$을 넣은 것이므로 마지막 항도 $2(k+1) - 1$로 바뀐다.

### 문제 4

**접근.** 항을 계산하면 $a_1 = 1$, $a_2 = 6$, $a_3 = 11$, $a_4 = 16$ — 공차 5의 등차수열이다. 34주차 §1.6의 사이클대로 ①~③으로 추측을 만들고 ④에서 귀납으로 확정한다.

**풀이.** 추측: $a_n = 5n - 4$. **[기초]** $a_1 = 1$이고 $5 \cdot 1 - 4 = 1$ ✓. **[귀납]** $a_k = 5k - 4$라고 가정하자. 점화식을 먼저 대입하면

$$
a_{k+1} = a_k + 5 = (5k - 4) + 5 \ \text{(귀납 가정)} = 5k + 1 = 5(k+1) - 4
$$

곧 $P(k+1)$이 참이다. $\blacksquare$

**복기.** 귀납 단계에서 가장 먼저 하는 일은 추측식 대입이 아니라 **점화식 대입**이다. 점화식으로 $a_{k+1}$을 $a_k$로 바꾼 다음에야 귀납 가정을 끼울 자리가 생긴다. 검산: $a_4 = 16 = 5 \cdot 4 - 4$ ✓.

### 문제 5

**접근.** 증명이 아니라 기초 위치의 탐색이므로 대입 표를 정확히 채우는 것이 전부다. 한 번 성립한 뒤에 다시 끊기지 않는지까지 보아야 "계속 성립"을 말할 수 있다.

**풀이.**

| **$n$** | **1** | **2** | **3** | **4** | **5** | **6** | **7** |
|---|---|---|---|---|---|---|---|
| $2^n$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 |
| $10n$ | 10 | 20 | 30 | 40 | 50 | 60 | 70 |
| 판정 | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ |

따라서 **$n = 6$부터** 계속 성립한다.

**복기.** 이 뒤로 끊기지 않는 이유는 좌변이 2배씩 커지는 동안 우변은 10씩만 커지기 때문이다. 이 직관을 연결 부등식으로 굳히면 증명도 완성된다: $k \ge 6$에서 $2^{k+1} = 2 \cdot 2^k > 2 \cdot 10k = 10k + 10k \ge 10(k+1)$이다(마지막 부등호는 $10k \ge 10$, 곧 $k \ge 1$에서 성립).

### 문제 6

**접근.** 개념 절의 박물관 표를 백지에서 재현하는 문제다. 이름 다섯 개와 탐지 질문 다섯 개가 모두 필요하다.

**풀이.** **1관 기초 누락** — 기초를 실제로 계산$\cdot$확인했는가? **2관 기초 부족 / 가정 범위 초과** — 귀납 단계가 **소비하는 가정**이 몇 개인가(첨자에 $F_{k-1}$이 보이는 것과 $P(k-1)$을 가정으로 쓰는 것은 다르다 — 34주차 §1.5), 그만큼 기초가 있는가, 그리고 실제로 쓴 과거가 선언한 가정 안에 있는가($P(k)$만 가정하고 $P(k-1)$을 쓰지 않았는가)? **3관 전달의 첫 고리 붕괴** — $P(k) \Rightarrow P(k+1)$이 모든 $k$에서, 특히 가장 작은 $k$에서 성립하는가? **4관 연결 부등식 생략** — 귀납 가정이 데려다준 중간값에서 목표까지의 다리를 실제로 놓았는가? **5관 귀납 가정 미사용** — "(귀납 가정)" 표시가 본문에 있는가, 없다면 귀납이 필요했는가?

**복기.** 다섯 관의 순서는 답안을 읽어 내려가는 순서와 같다. 채점할 때도 위에서부터 차례로 물으면 빠뜨리는 관이 없다.

### 문제 7

**접근.** 합 공식이므로 마지막 항 $(k+1)(k+2)$를 떼어내 귀납 가정을 끼운다. 그다음 목표 꼴 $\frac{(k+1)(k+2)(k+3)}{3}$을 보고 공통인수 $(k+1)(k+2)$로 묶을 것을 미리 정해 둔다.

**풀이.** **[기초]** $n = 1$: 좌변 $1 \cdot 2 = 2$, 우변 $\frac{1 \cdot 2 \cdot 3}{3} = 2$ ✓. **[귀납]** $\sum_{i=1}^{k} i(i+1) = \frac{k(k+1)(k+2)}{3}$이라고 가정하자. 목표는 $\sum_{i=1}^{k+1} i(i+1) = \frac{(k+1)(k+2)(k+3)}{3}$이다.

$$
\sum_{i=1}^{k+1} i(i+1) = \frac{k(k+1)(k+2)}{3} + (k+1)(k+2) \ \text{(귀납 가정)} = (k+1)(k+2)\left(\frac{k}{3} + 1\right) = \frac{(k+1)(k+2)(k+3)}{3}
$$

목표 꼴과 일치한다. $\blacksquare$

**복기.** 검산: $n = 3$에서 좌변 $2 + 6 + 12 = 20$, 우변 $\frac{3 \cdot 4 \cdot 5}{3} = 20$ ✓.

### 문제 8

**접근.** 32주차 예제 2.1의 백지 재현이다. 부등식 귀납의 2단 구조를 그대로 쓴다 — ① 귀납 가정 투입으로 중간값 $2k^2$까지 간 뒤 ② 연결 부등식 $2k^2 \ge (k+1)^2$을 별도로 증명하고 ③ 추이성으로 잇는다. 가정 $k \ge 4$가 소비되는 곳이 어디인지 표시하는 것까지가 답안이다.

**풀이.** **[기초]** $n = 4$: $2^4 = 16$, $4^2 = 16$이므로 $16 \ge 16$ ✓ (등호이지만 부등호가 $\ge$이므로 성립한다). **[귀납]** $k \ge 4$인 정수 $k$에 대해 $2^k \ge k^2$이라고 가정하자. 목표는 $2^{k+1} \ge (k+1)^2$이다. ① $2^{k+1} = 2 \cdot 2^k \ge 2k^2$ (귀납 가정; 양변에 양수 $2$를 곱했으므로 16주차의 (W3)). ② 연결 부등식 $2k^2 \ge (k+1)^2$을 증명한다. 차를 계산하면

$$
2k^2 - (k+1)^2 = 2k^2 - (k^2 + 2k + 1) = k^2 - 2k - 1 = (k-1)^2 - 2
$$

이고, $k \ge 4$이면 $k - 1 \ge 3$이므로 $(k-1)^2 \ge 9$, 따라서 $(k-1)^2 - 2 \ge 7 > 0$이다. ③ 두 부등식을 추이성((W6))으로 이으면 $2^{k+1} \ge 2k^2 \ge (k+1)^2$. $\blacksquare$

**복기.** 가정 $k \ge 4$가 쓰이는 자리는 ②의 한 줄뿐이다. 연결 부등식 자체는 $k \ge 3$부터 참이므로 기초 위치 $n_0 = 4$와 어긋나지 않는다. ②를 생략하면 그대로 4관 오류가 된다(32주차 문제 17).

### 문제 9

**접근.** 목표 식 $10^{k+1} - 1$ 안에 귀납 가정의 식 $10^k - 1$이 보이도록 쪼갠다: $10^{k+1} - 1 = 10 \cdot 10^k - 1 = 10(10^k - 1) + 9$. 나누어떨어짐 귀납의 표준 동작이다.

**풀이.** **[기초]** $n = 1$: $10^1 - 1 = 9 = 9 \cdot 1$이므로 $9 \mid 9$ ✓. **[귀납]** $9 \mid (10^k - 1)$이라고 가정하자. 정의에 의해 $10^k - 1 = 9m$인 정수 $m$이 존재한다. 그러면

$$
10^{k+1} - 1 = 10 \cdot 10^k - 1 = 10(10^k - 1) + 9 = 10 \cdot 9m + 9 = 9(10m + 1)
$$

이고 $10m + 1$은 정수이므로 $9 \mid (10^{k+1} - 1)$이다. $\blacksquare$

**복기.** 마지막 두 줄을 "첫 항은 귀납 가정으로 9의 배수, 둘째 항 9도 9의 배수, 배수의 합도 배수(2주차 예제 2.2)"로 적어도 같은 증명이다. 31주차 문제 15(a)는 같은 사실을 합동으로 적은 것이다 — $10^k \equiv 1 \pmod 9$.

### 문제 10

**접근.** 항을 계산하면 $2, 6, 18, 54$ — 공비 3의 등비수열이다. 닫힌 꼴의 지수를 $n$이 아니라 $n-1$로 잡아야 $a_1 = 2$와 맞는다.

**풀이.** 추측: $a_n = 2 \cdot 3^{n-1}$. **[기초]** $a_1 = 2$이고 $2 \cdot 3^0 = 2$ ✓. **[귀납]** $a_k = 2 \cdot 3^{k-1}$이라고 가정하자. 점화식을 대입하면

$$
a_{k+1} = 3a_k = 3 \cdot 2 \cdot 3^{k-1} \ \text{(귀납 가정)} = 2 \cdot 3^{k}
$$

이고 $3^k = 3^{(k+1)-1}$이므로 $P(k+1)$이 참이다. $\blacksquare$

**복기.** 검산: $a_4 = 2 \cdot 3^3 = 54$ ✓. 지수를 $n$으로 잡아 $a_n = 2 \cdot 3^n$으로 추측하면 기초에서 $a_1 = 6 \ne 2$로 즉시 걸린다 — 기초 확인이 추측의 검산 역할까지 한다.

### 문제 11

**접근.** 좌변의 다음 항은 $F_{2(k+1)} = F_{2k+2}$이다. 귀납 가정을 끼우면 $F_{2k+1} + F_{2k+2}$가 남고, 이것이 정확히 피보나치 점화식의 좌변 꼴이므로 $F_{2k+3}$으로 접힌다.

**풀이.** **[기초]** $n = 1$: 좌변 $F_2 = 1$, 우변 $F_3 - 1 = 2 - 1 = 1$ ✓. **[귀납]** $F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1$이라고 가정하자. 목표는 $F_2 + \cdots + F_{2k+2} = F_{2k+3} - 1$이다.

$$
F_2 + \cdots + F_{2k} + F_{2k+2} = (F_{2k+1} - 1) + F_{2k+2} \ \text{(귀납 가정)} = (F_{2k+1} + F_{2k+2}) - 1 = F_{2k+3} - 1
$$

마지막 등호는 점화식 $F_{n} = F_{n-1} + F_{n-2}$를 $n = 2k+3$에 쓴 것이다. $F_{2k+3} = F_{2(k+1)+1}$이므로 목표 꼴과 일치한다. $\blacksquare$

**복기.** 검산: $n = 3$에서 좌변 $F_2 + F_4 + F_6 = 1 + 3 + 8 = 12$, 우변 $F_7 - 1 = 13 - 1 = 12$ ✓.

### 문제 12

**접근.** 귀납 단계에서 $k+1$을 만드는 가장 간단한 길은 3원짜리를 한 장 더 얹는 것이므로, 참조하는 과거는 $k+1-3 = k-2$ — 보폭이 3이다. 따라서 기초도 3개($12, 13, 14$) 필요하다.

**풀이.** **[기초]** $12 = 3 \cdot 4 + 7 \cdot 0$, $13 = 3 \cdot 2 + 7 \cdot 1$, $14 = 3 \cdot 0 + 7 \cdot 2$ ✓✓✓. **[귀납]** $k \ge 14$이고, $12 \le j \le k$인 모든 정수 $j$가 $3a + 7b$ 꼴이라고 가정하자(강한 귀납 가정). 목표는 $k+1$도 그 꼴임을 보이는 것이다. $k \ge 14$에서 $k + 1 \ge 15$이므로 $k - 2 = (k+1) - 3 \ge 12$이고, 또 $k - 2 \le k$이므로 $k-2$는 강한 가정의 범위 안에 있다. 따라서 $k - 2 = 3a + 7b$인 음이 아닌 정수 $a, b$가 존재한다(강한 귀납 가정). 그러면

$$
k + 1 = (k - 2) + 3 = 3a + 7b + 3 = 3(a+1) + 7b
$$

이고 $a + 1 \ge 0$, $b \ge 0$이므로 $k+1$도 목표 꼴이다. $\blacksquare$

**복기.** 기초를 12 하나만 두면 $k+1 = 13, 14$에서 참조할 과거($10, 11$)가 무대 밖이라 근거가 없다 — 2관 오류다. 참고로 $11 = 3 \cdot 7 - 3 - 7$이 3원$\cdot$7원으로 만들 수 없는 마지막 금액인데, 이는 33주차 문제 19의 복기에 나온, **서로소인** $m, n$에 대한 프로베니우스 수 $mn - m - n$과 같은 꼴이다(3과 7은 서로소다. 그때는 $4 \cdot 7 - 4 - 7 = 17$이었고 4와 7도 서로소다). 서로소 조건을 빼면 거짓이다 — $m = 4$, $n = 6$이면 공식값은 $14$지만 두 우표로는 홀수 금액을 아무리 큰 것이라도 만들 수 없어 "마지막 불가능 금액" 자체가 존재하지 않는다.

### 문제 13

**접근.** 요약과 해부 두 부분으로 나뉜다. 해부에서 먼저 할 일은 "기초는 참이고 $k \ge 2$의 전달도 유효하다"를 인정하는 것이다. 무엇이 멀쩡한지 확정해야 무너진 한 곳을 정확히 지목할 수 있다.

**풀이.** **요약.** 기초에서 $n = 1$을 확인한다(말 1마리는 자기 자신과 같은 색). 귀납 단계에서는 말 $k+1$마리를 앞 $k$마리 $\{1, \dots, k\}$와 뒤 $k$마리 $\{2, \dots, k+1\}$로 나누고, 각각 귀납 가정으로 단색이라 한 뒤, 두 무리가 공유하는 말을 다리 삼아 전체가 단색이라고 결론짓는다. **해부.** 무너지는 지점은 $k = 1$이다. 이때 앞 무리는 $\{1\}$, 뒤 무리는 $\{2\}$이고 공유 무리 $\{2, \dots, k\}$는 공집합이므로, 두 무리의 색을 이을 다리가 존재하지 않는다. 즉 이 논증은 $k \ge 2$에서만 작동하고 $P(1) \Rightarrow P(2)$라는 고리가 성립하지 않는다. 기초 $P(1)$은 참이며 $P(2) \Rightarrow P(3) \Rightarrow \cdots$도 전부 유효하지만, $P(2)$에 도달할 길이 없으므로 그 뒤 전부가 근거를 잃는다. 실제로 $P(2)$는 거짓이다.

**복기.** 채점의 세 지점: ① 기초와 $k \ge 2$의 전달이 유효함을 인정했는가 ② 무너지는 것이 $P(1) \Rightarrow P(2)$ 한 고리임을 지목했는가 ③ 원인이 "겹침이 비는" 퇴화 상황임을 명시했는가. 이 역설을 "기초가 틀렸다"로 적으면 진단이 어긋난다.

### 문제 14

**접근.** 34주차 문제 12의 백지 재현이다. 공약수 $d$를 잡고, 점화식의 차를 이용해 $d$를 한 칸 아래 피보나치 수의 약수로 내려보낸 뒤 귀납 가정을 쓴다. 필요한 부품은 "$d \mid x$이고 $d \mid y$이면 $d \mid (x - y)$"(2주차 문제 7)뿐이다.

**풀이.** 명제 $P(n)$을 "$F_n$과 $F_{n+1}$의 공약수는 $\pm 1$뿐이다"로 둔다. **[기초]** $n = 1$: $F_1 = F_2 = 1$이고, $1$의 약수는 $\pm 1$뿐이므로 공약수도 $\pm 1$뿐이다 ✓. **[귀납]** $F_k$와 $F_{k+1}$의 공약수가 $\pm 1$뿐이라고 가정하자. $d$를 $F_{k+1}$과 $F_{k+2}$의 임의의 공약수라 하자. $d \mid F_{k+2}$이고 $d \mid F_{k+1}$이므로

$$
d \mid (F_{k+2} - F_{k+1}) = F_k
$$

이다(2주차 문제 7과 점화식 $F_{k+2} = F_{k+1} + F_k$). 따라서 $d$는 $F_k$와 $F_{k+1}$의 공약수이고, 귀납 가정에 의해 $d = \pm 1$이다. 곧 $F_{k+1}$과 $F_{k+2}$의 공약수도 $\pm 1$뿐이다. $\blacksquare$

**복기.** 점화식을 앞으로 밀지 않고 **뒤로 감아** 귀납 가정이 있는 자리로 내려온 것이 이 증명의 전부다. 이 명제의 $P(n)$은 $F_n$과 $F_{n+1}$을 한 문장으로 묶은 것이므로 $P(k)$ 하나만 소비된다 — 두 칸 점화 수열인데도 기초가 $n = 1$ 하나인 이유다(34주차 §1.5). 검산: $F_5 = 5$, $F_6 = 8$의 공약수는 $\pm 1$ ✓.

### 문제 15

**접근.** 먼저 실험한다. $n = 1$: $3 > 2$ ✓, $n = 2$: $9 > 8$ ✓ — 처음부터 성립한다. 그다음 연결 부등식을 미리 계산해 유효 범위를 본다: $3k \cdot 2^k \ge (k+1) 2^{k+1}$은 양변을 $2^k$로 나누면 $3k \ge 2(k+1)$, 곧 $k \ge 2$와 같다. 연결이 $k \ge 2$부터만 작동하므로 기초는 $n = 1$과 $n = 2$ 두 개를 놓아야 한다.

**풀이.** **[기초]** $n = 1$: $3^1 = 3 > 1 \cdot 2^1 = 2$ ✓. $n = 2$: $3^2 = 9 > 2 \cdot 2^2 = 8$ ✓. **[귀납]** $k \ge 2$인 정수 $k$에 대해 $3^k > k \cdot 2^k$라고 가정하자. 목표는 $3^{k+1} > (k+1) \cdot 2^{k+1}$이다. ① $3^{k+1} = 3 \cdot 3^k > 3k \cdot 2^k$ (귀납 가정; 양변에 양수 $3$을 곱했으므로 (W3)). ② 연결 부등식: $k \ge 2$이면 $3k - 2(k+1) = k - 2 \ge 0$이므로 $3k \ge 2(k+1)$이고, 양변에 양수 $2^k$를 곱하면

$$
3k \cdot 2^k \ge 2(k+1) \cdot 2^k = (k+1) \cdot 2^{k+1}
$$

③ ①과 ②를 추이성((W6))으로 이으면 $3^{k+1} > (k+1) \cdot 2^{k+1}$이다. $\blacksquare$

**복기.** 기초가 2개인 이유는 보폭 때문이 아니다 — 보폭은 1칸이다. 이유는 **연결 부등식의 유효 범위가 $k \ge 2$**라는 것이고, 그래서 $P(2)$는 전달로 얻을 수 없어 직접 확인해야 한다. 기초 개수는 "보폭"과 "연결부의 요구 조건" 두 곳에서 온다.

### 문제 16

**접근.** 최소 반례법의 뼈대는 정해져 있다 — 반례가 있다고 가정하고, 최소원리로 최소 반례 $m$을 잡고, 가장 작은 값에서 $m$을 배제한 뒤, $m - 1$이 반례가 아니라는 사실로부터 $m$도 반례가 아님을 끌어내 모순을 만든다. 필요한 관계식은 $m^2 + m$과 $(m-1)^2 + (m-1)$의 차다.

**풀이.** 모순을 위해 반례가 존재한다고 가정하자. 반례가 되는 자연수를 모두 모은 집합 $S$는 공집합이 아닌 자연수의 부분집합이므로, 최소원리에 의해 최소원소 $m = \min S$가 존재한다. $1^2 + 1 = 2$는 짝수이므로 $1 \notin S$이고, 따라서 $m \ge 2$이다. 그러면 $m - 1$은 자연수이면서 $m$보다 작으므로 $m - 1 \notin S$, 곧 $(m-1)^2 + (m-1)$은 짝수다. 한편

$$
m^2 + m = \big((m-1)^2 + (m-1)\big) + 2m
$$

이다(전개 확인: $(m-1)^2 + (m-1) + 2m = m^2 - 2m + 1 + m - 1 + 2m = m^2 + m$ ✓). 우변은 짝수와 짝수의 합이므로 짝수이고(2주차 예제 2.2), 따라서 $m^2 + m$도 짝수다. 이는 $m \in S$, 곧 $m$이 반례라는 것과 모순이다. 그러므로 반례는 존재하지 않는다. $\blacksquare$

**복기.** 같은 명제의 세 번째 증명이다 — 1주차 문제 16은 연속한 두 정수의 곱으로, 17주차 §3 훈련 1은 $n$의 홀짝 케이스로, 이번은 최소원리로 증명했다. 기법이 달라도 뼈대는 같지만, **무대는 같지 않다** — 최소원리는 자연수(음이 아닌 정수)의 부분집합에만 쓸 수 있으므로 이번 증명이 덮는 것은 자연수 $n$뿐인 반면, 앞의 두 증명은 모든 정수를 덮는다. 음의 정수까지 넓히려면 $n \le -1$에서 $m = -(n+1) \ge 0$으로 옮겨 $n^2 + n = m^2 + m$임을 확인하거나, 1주차 문제 16의 연속 곱 논증을 그대로 인용해야 한다.

### 문제 17

**접근.** 결함은 두 개다. 하나는 기초를 $n = 2$로 옮겨 놓고 명제의 범위는 $n \ge 1$인 채로 둔 것이고, 다른 하나는 연결 부등식을 "크니까"로 넘어간 것(4관)이다. 둘 다 지적하고, 4관 쪽은 실제로 증명해 메워야 수정이 끝난다.

**풀이.** **결함 ① — 기초 이동의 뒤처리 누락.** $n = 1$에서 $4^1 = 4$이고 $1^2 + 3 = 4$이므로 등호이고, 원명제의 부등호는 $>$이므로 $P(1)$은 **거짓**이다. 답안은 $P(1)$이 거짓임을 알아차렸지만 거기서 멈췄다 — 기초를 옮겼으면 명제의 주장 범위도 함께 옮겨야 한다. 명제 자체를 "$n \ge 2$인 모든 자연수에 대해 $4^n > n^2 + 3$"으로 고쳐 선언해야 한다. 그러지 않으면 증명이 확보하는 범위($n \ge 2$)와 명제가 주장하는 범위($n \ge 1$)가 어긋난 채로 남는다. **결함 ② — 4관(연결 부등식 생략).** "$4(k^2+3)$은 $(k+1)^2 + 3$보다 크니까"는 증명이 아니라 주장이다. 차를 계산해 메운다.

$$
4(k^2 + 3) - \big((k+1)^2 + 3\big) = (4k^2 + 12) - (k^2 + 2k + 4) = 3k^2 - 2k + 8
$$

$k \ge 1$이면 $3k^2 \ge 3k \ge 2k$이므로 $3k^2 - 2k \ge 0$이고, 따라서 $3k^2 - 2k + 8 \ge 8 > 0$이다. (완전제곱으로 처리해도 된다: $3k^2 - 2k + 8 = 3\left(k - \tfrac13\right)^2 + \tfrac{23}{3} > 0$.) 곧 $4(k^2+3) > (k+1)^2 + 3$이다. **수정된 증명.** **[기초]** 새 명제의 무대가 $n \ge 2$이므로 기초는 $n = 2$다: $4^2 = 16$이고 $2^2 + 3 = 7$이며 $16 > 7$ ✓. (원답안이 적은 "$n = 2$: $16 > 7$"은 $n \ge 1$ 명제의 기초로 잘못 붙어 있던 줄인데, 명제를 $n \ge 2$로 고쳐 선언하고 나면 그 줄이 제자리를 찾아 그대로 재사용된다.) **[귀납]** $k \ge 2$에서 $4^k > k^2 + 3$을 가정하면, $4^{k+1} = 4 \cdot 4^k > 4(k^2 + 3)$ (귀납 가정, (W3))이고 위 연결 부등식에 의해 $4(k^2+3) > (k+1)^2 + 3$이므로, 추이성((W6))으로 $4^{k+1} > (k+1)^2 + 3$이다. $\blacksquare$

**복기.** 4관 오류라고 해서 연결 부등식이 거짓인 것은 아니다 — 여기서는 모든 $k \ge 1$에서 참이었다. 결함은 참$\cdot$거짓이 아니라 **확인하지 않았다는 것**이다.

### 문제 18

**접근.** 몸통을 한 줄씩 따라가며 "(귀납 가정)"이 소비되는 자리를 찾는다. 찾을 수 없다면 그 답안은 귀납의 껍데기 안에 직접 증명을 넣은 것이다(5관). 22주차 §1.7 기법 선택 가이드 ④의 귀납판이다.

**풀이.** **논리적 오류는 없다.** 각 문장은 참이고 결론도 참이다. (다만 "$k$ 홀짝 케이스와 mod 3 케이스로"는 예고만 하고 한 경우도 다루지 않은 빈 구절이다 — 실제로 쓰인 근거는 30주차 문제 17이고, 케이스 분석은 필요조차 없다. 참인 문장들 사이에 낀 이런 빈 구절도 지적 대상이다.) 그런데도 나쁜 답안인 이유는 **5관(귀납 가정 미사용)**이다. 가정 "$6 \mid (k^3 + 5k)$"가 본문 어디에서도 쓰이지 않았고, 실제로 사용된 논증 — $n^3 + 5n = (n^3 - n) + 6n$이고 $6 \mid (n^3 - n)$(30주차 문제 17), $6 \mid 6n$이므로 합도 6의 배수 — 은 임의의 자연수 $n$에 대해 그대로 성립하는 직접 증명이다. 답안은 그 직접 증명을 $k$에 한 번, $k+1$에 한 번 반복했을 뿐이며, 귀납의 틀은 아무 일도 하지 않는다. **수정 (직접 증명으로).** "임의의 자연수 $n$에 대해 $n^3 + 5n = (n^3 - n) + 6n$이다. $6 \mid (n^3 - n)$이고(30주차 문제 17) $6 \mid 6n$이므로, 배수의 합도 배수여서(2주차 예제 2.2) $6 \mid (n^3 + 5n)$이다. $\blacksquare$" — 세 줄로 끝난다.

**복기.** 굳이 귀납으로 쓰고 싶다면 귀납 가정이 실제로 소비되도록 식을 배치하면 된다: $(k+1)^3 + 5(k+1) = (k^3 + 5k) + 3k^2 + 3k + 6 = (k^3 + 5k) + 3k(k+1) + 6$에서 첫 항은 귀납 가정으로 6의 배수, $3k(k+1)$은 $k(k+1)$이 짝수이므로(1주차 문제 16) 6의 배수, $6$도 6의 배수다. 이렇게 쓰면 "(귀납 가정)" 표시가 실제 근거가 된다.

### 문제 19

**접근.** $(k+1)^3 + 2(k+1)$을 전개한 뒤, 귀납 가정의 식 $k^3 + 2k$가 통째로 드러나도록 재배열한다. 남는 항이 3의 배수임을 보이면 끝난다.

**풀이.** **[기초]** $n = 1$: $1^3 + 2 \cdot 1 = 3$이고 $3 \mid 3$ ✓. **[귀납]** $3 \mid (k^3 + 2k)$라고 가정하자. 목표는 $3 \mid \big((k+1)^3 + 2(k+1)\big)$이다.

$$
(k+1)^3 + 2(k+1) = k^3 + 3k^2 + 3k + 1 + 2k + 2 = (k^3 + 2k) + 3(k^2 + k + 1)
$$

첫 항은 귀납 가정에 의해 3의 배수이고, 둘째 항은 $k^2 + k + 1$이 정수이므로 그 자체로 3의 배수다. 배수의 합도 배수이므로(2주차 예제 2.2) $3 \mid \big((k+1)^3 + 2(k+1)\big)$이다. $\blacksquare$

**복기.** 검산: $n = 2$에서 $8 + 4 = 12 = 3 \cdot 4$ ✓, $n = 3$에서 $27 + 6 = 33 = 3 \cdot 11$ ✓. $n^3 + 2n = n(n^2 + 2)$를 $n$의 나머지 세 경우로 갈라 증명할 수도 있다(17주차 §3 훈련 1의 방식) — 기법 선택은 늘 복수다.

### 문제 20

**접근.** 박물관 5관을 그대로 다섯 문항으로 옮기되, 남의 표현이 아니라 답안을 검사할 때 실제로 던질 질문 꼴로 적는다. 그리고 이번 시험에서 걸린 자리를 관 번호로 기록해 둔다.

**풀이.** (예시 답안) ① 기초를 실제로 계산했는가 — 좌변과 우변을 각각 계산해 비교했는가? ② 귀납 단계가 **소비하는 가정**이 몇 개인지 세고(첨자에 $F_{k-1}$이 보이는 것과 $P(k-1)$을 가정으로 쓰는 것은 다르다 — 34주차 §1.5), 그 수만큼(그리고 연결부의 유효 범위가 요구하는 만큼) 기초를 놓았는가 — 또 그 과거가 선언한 가정 안에 들어 있는가($P(k)$만 가정하고 $P(k-1)$을 쓰지 않았는가)? ③ 전달 논증이 가장 작은 $k$에서도 작동하는가 — 겹침$\cdot$항$\cdot$분모가 비거나 사라지지 않는가? ④ (부등식) 귀납 가정이 데려다준 중간값에서 목표까지의 연결 부등식을 별도로 증명했는가? ⑤ "(귀납 가정)" 표시가 본문에 실제로 있는가 — 없다면 직접 증명으로 다시 쓸 것.

**복기.** 기록 예시: "15번에서 기초를 1개만 두려다 연결부의 $k \ge 2$ 조건에 걸렸다 — 2관과 4관의 복합." 이렇게 관 번호로 적어 두면 다음 복습에서 어느 주차로 돌아갈지가 바로 정해진다.

## 채점 가이드와 7부 수료

- **수료 기준**: 1번(원리 진술)을 만점으로 쓰고, 증명 문항(2~4, 7~12, 14~16, 19) 중 9개 이상을 서식$\cdot$논리 무결로, 진단(13, 17, 18) 중 2개 이상을 정확히 짚었으면 7부 수료로 보고 36주차로 넘어간다.
- 부등식(8, 15)에서 연결부 누락이 반복되면 32주차를 재복습한다.
- 기초 개수를 잘못 잡았다면(12, 15) 33주차 문제 17을 재복습한다. 보통 귀납으로 선언해 놓고 $P(k-1)$을 쓴 줄이 나왔다면 34주차 문제 17을 재복습한다 — 그 답안은 기초를 하나 더 놓아도 선언이 보통 귀납인 한 $P(k-1)$을 쓸 권리가 없다(33주차 §1.4).
- 13번(말 역설)을 "기초가 틀렸다"로 진단했다면 §1.2를 다시 읽는다 — 이 역설의 기초는 **참**이다.

**7부까지의 지도.** 직접$\cdot$케이스$\cdot$대우$\cdot$귀류에 귀납까지, 증명의 다섯 기법이 모두 갖추어졌다. 남은 것은 기법이 아니라 **대상**이다: 관계(36~39주), 함수(40~44주), 극한(45~47주), 무한(48~49주) — 대학 수학이 실제로 다루는 무대들이다.

---

**다음 주 예고:** 8부 개막 — 관계(relation). "$x < y$", "$a \equiv b$", "$A \subseteq B$"처럼 **두 대상 사이의 관계**를 집합(데카르트 곱의 부분집합)으로 정의하고, 반사$\cdot$대칭$\cdot$추이라는 세 성질로 분류한다. 20주차에서 합동이 등호처럼 굴던 이유가 여기서 이름을 얻는다.