# C8주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 세 형태를 함께 만들기 완성된 답안을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 약한 귀납: 홀수의 합 **Result.** 모든 자연수 $n$ 에 대해 $\displaystyle\sum_{i=1}^n (2i-1) = n^2$ 이다. **설계 — 쓰기 전에 정하는 두 가지.** 귀납 답안도 다른 증명과 같다. 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 수식으로 옮긴다. 귀납에서 특별한 점은 이 번역을 **귀납 단계 안에서** 한다는 것뿐이다. | | **말** | **수식 번역** | |---|---|---| | 형태 판정 | $P(n+1)$ 이 요구하는 이전 항 | $\underline{\quad(1)\quad}$ | | 기저 | $n = 1$ 에서 성립 | 좌변 $= 1$, 우변 $= 1^2$ | | 가정 (출발점) | $P(n)$ | $\sum_{i=1}^n (2i-1) = n^2$ | | 목표 (도착점) | $P(n+1)$ | $\sum_{i=1}^{n+1}(2i-1) = \underline{\quad(2)\quad}$ | :::{container} quotebox **확인 12.** 표의 (1)과 (2)를 채워 보자. (1)은 §1.6의 세 물음 중 첫째 물음에 답하는 칸이고, (2)는 $P(n)$ 의 식에서 $n$ 을 $n+1$ 로 바꾸어 얻는 칸이다. ::: :::{admonition} 답 :class: quotebox dropdown (1) $P(n)$ 하나. 합의 마지막 항 하나만 떼면 $\sum_{i=1}^n$ 이 그대로 드러나므로 직전 항으로 충분하다 — 약한 귀납이다. (2) $(n+1)^2$. $P(n)$ 의 우변 $n^2$ 에서 $n$ 자리에 $n+1$ 을 넣은 것이다. 도착점을 먼저 적어 두지 않으면 계산을 어디서 멈춰야 할지 알 수 없다. ::: **1단계 — 기저를 확인한다.** 사다리의 첫 칸을 실제로 놓는다. 좌변과 우변을 각각 따로 계산해 값이 같음을 보인다. :::{container} quotebox **확인 13.** 기저 문장을 완성해 보자. "$n = 1$ 일 때 좌변은 $\sum_{i=1}^1 (2i-1) = \underline{\quad}$ 이고 우변은 $1^2 = \underline{\quad}$ 이다." ::: :::{admonition} 답 :class: quotebox dropdown 좌변 $= 2 \cdot 1 - 1 = 1$, 우변 $= 1$. 두 값이 같으므로 $P(1)$ 이 참이다. 기저에서 좌변과 우변을 한꺼번에 "당연히 같다"로 처리하지 않는다 — 각각 계산해 값을 적는 것까지가 걸음 ①이다. ::: **2단계 — 가정을 선언한다.** 귀납 단계는 조건문 $P(n) \Rightarrow P(n+1)$ 하나를 증명하는 일이고, 그 조건문의 출발점을 무대에 올리는 문장이다(S14주차). **3단계 — 쪼갠다.** 도착점의 좌변 $\sum_{i=1}^{n+1}(2i-1)$ 안에서 가정의 좌변 $\sum_{i=1}^n (2i-1)$ 이 보이도록 재그룹한다. 이 줄이 귀납의 관절이다. :::{container} quotebox **확인 14.** 쪼개기 줄을 완성해 보자. "$\displaystyle\sum_{i=1}^{n+1}(2i-1) = \left(\sum_{i=1}^{n}(2i-1)\right) + \underline{\qquad}$" — 떼어 낸 마지막 항은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 마지막 항은 $2(n+1) - 1 = 2n+1$ 이다. 합의 일반항 $2i-1$ 에서 $i$ 자리에 $n+1$ 을 넣어 얻는다. 마지막 항을 $2n-1$ 로 적는 경우가 많은데, 그것은 $i = n$ 일 때의 항이다 — 떼어 내야 할 것은 새로 **늘어난** 항이다. ::: **4단계 — 가정을 소비하고 도착점의 꼴로 정리한다.** 쪼개기로 드러난 자리에 가정을 대입한 뒤, 도착점 $(n+1)^2$ 이 나올 때까지 밀어붙인다. :::{container} quotebox **확인 15.** 이어지는 두 줄을 완성해 보자. "$= \underline{\quad} + (2n+1)$ [가정 소비] $= \underline{\qquad}$." ::: :::{admonition} 답 :class: quotebox dropdown $= n^2 + (2n+1) = n^2 + 2n + 1 = (n+1)^2$. 첫 등호가 가정 소비처다 — $\sum_{i=1}^n (2i-1)$ 을 $n^2$ 으로 바꾼 그 순간에만 가정 $P(n)$ 이 쓰였다. 둘째 등호는 완전제곱 정리이고 근거 ③이다. ::: **5단계 — 결론을 선언한다.** 두 걸음이 갖춰졌음을 밝히고 명제를 선언한다. :::{container} quotebox **확인 16.** 마지막 문장을 완성해 보자. "기저 단계와 $\underline{\qquad}$ 가 모두 성립하므로, 귀납의 원리에 의해 $\underline{\qquad}$. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown "기저 단계와 **귀납 단계**가 모두 성립하므로, 귀납의 원리에 의해 **모든 자연수 $n$ 에 대해 $\sum_{i=1}^n (2i-1) = n^2$ 이다.** $\blacksquare$" 결론 문장에서 원 명제를 다시 적는다. "따라서 성립한다"로 끝내면 무엇이 증명되었는지가 답안에 남지 않는다. ::: **완성본.** 방금 만든 다섯 걸음을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $P(n)$ 을 "$\sum_{i=1}^n (2i-1) = n^2$" 이라 하자. | 무엇을 $n$ 에 대해 세울지 문장으로 고정한다. 이 선언이 없으면 아래의 "가정"이 무엇을 가리키는지 정해지지 않는다. | | (기저) $n = 1$ 일 때 좌변은 $2 \cdot 1 - 1 = 1$, 우변은 $1^2 = 1$ 로 같다. 따라서 $P(1)$ 이 참이다. | 걸음 ①. 사다리의 첫 칸이다. 이것이 없으면 확인 2의 삭제 실험처럼 전달만 남는다. | | (귀납 단계) $n$ 을 자연수라 하고 $P(n)$ 을 가정하자. | 걸음 ②. 조건문 $P(n) \Rightarrow P(n+1)$ 의 출발점을 무대에 올린다(S14주차). | | $\displaystyle\sum_{i=1}^{n+1}(2i-1) = \left(\sum_{i=1}^{n}(2i-1)\right) + (2n+1)$ | 걸음 ③ 쪼개기. 새로 늘어난 항 $2(n+1)-1$ 을 떼어 내 가정의 좌변을 드러낸다. 관절은 이 한 줄이다. | | $= n^2 + (2n+1) = n^2 + 2n + 1 = (n+1)^2$ | 걸음 ④ 가정 소비. 첫 등호에서만 가정이 쓰였다. 나머지는 전개와 완전제곱(근거 ③)이다. | | 곧 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 $n$ 에 대해 $\sum_{i=1}^n (2i-1) = n^2$ 이다. $\blacksquare$ | 걸음 ⑤. 도착점에 닿았음을 밝히고 원 명제를 다시 선언한다. | **검산.** $n = 4$ 에서 좌변은 $1 + 3 + 5 + 7 = 16$ 이고 우변은 $4^2 = 16$ 이다. 검산은 증명이 아니지만 쪼개기를 잘못 적었을 때 곧바로 걸린다. ### 예제 2.2 — 강한 귀납: 소인수분해의 존재 **Result.** 2 이상의 모든 정수는 소수이거나 소수들의 곱이다. 준비 운동 4번이 바로 이 명제였고, §1.1의 시도 1이 여기서 막혔다. 이번에는 설계만 함께 하고 본문은 완성본으로 본다. :::{container} quotebox **확인 17.** 설계표를 채워 보자. (1) $P(n+1)$ 이 요구하는 이전 항은 무엇이고 따라서 형태는 무엇인가. (2) 기저는 몇 개가 필요한가. (3) 목표(도착점)는 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown (1) $n+1$ 이 합성수일 때 $n+1 = ab$ 로 쪼개지므로 필요한 것은 $P(a)$ 와 $P(b)$ 이고, $a$ 와 $b$ 가 $2$ 와 $n$ 사이 어디인지 미리 알 수 없다. §1.6의 둘째 물음에 걸리므로 **강한 귀납**이다. (2) 하나면 된다. 되돌아보는 보폭이 정해져 있지 않고 $2$ 부터 $n$ 까지 **전부**를 가정하므로, 그 구간의 시작점 $P(2)$ 만 손으로 채우면 된다. 보폭이 고정된 확인 5의 동전 무대와 여기가 다른 점이다. (3) $n+1$ 이 소수이거나 소수들의 곱임을 보이는 것. 이 결론은 두 갈래이므로 답안도 두 경우로 나뉜다. ::: | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $P(n)$ 을 "$n$ 은 소수이거나 소수들의 곱이다" 라 하고, $n \ge 2$ 에서 $P(n)$ 을 강한 귀납으로 보인다. | 형태를 답안 첫 줄에 밝힌다. 읽는 쪽이 아래의 가정 폭을 어디까지로 읽을지가 여기서 정해진다. | | (기저) $n = 2$ 는 소수이므로 $P(2)$ 가 참이다. | 걸음 ①. 구간의 시작점 하나면 충분하다(확인 17). | | (귀납 단계) $n \ge 2$ 라 하고, $2 \le i \le n$ 인 모든 정수 $i$ 에 대해 $P(i)$ 가 참이라고 가정하자. | 걸음 ②. 출발점이 $P(n)$ 하나가 아니라 구간 전체다 — 이 폭이 §1.1의 막힘을 푸는 유일한 차이다. | | $n+1$ 이 소수인 경우: $P(n+1)$ 이 그대로 참이다. | 결론의 첫 갈래가 이미 성립하는 경우다. 경우 나누기의 한쪽을 여기서 닫는다. | | $n+1$ 이 합성수인 경우: 합성수의 정의에 의해 $n+1 = ab$ 이면서 $1 < a < n+1$, $1 < b < n+1$ 인 정수 $a, b$ 가 존재한다. 정수이므로 $2 \le a \le n$ 이고 $2 \le b \le n$ 이다. | 걸음 ③ 쪼개기. 근거 ①(합성수의 정의)이다. 부등식을 $2 \le a \le n$ 으로 정리하는 이 줄이 $a$ 를 가정의 사정권 안으로 넣는다. | | $a$ 와 $b$ 는 모두 $2$ 이상 $n$ 이하이므로, 가정에 의해 각각 소수이거나 소수들의 곱이다. | 걸음 ④ 가정 소비. 여기서 소비한 것은 $P(a)$ 와 $P(b)$ 이고, 약한 귀납의 가정에는 이 둘이 들어 있지 않다. | | 두 표현을 곱으로 이어 붙이면 $n+1 = ab$ 도 소수들의 곱이다. 곧 $P(n+1)$ 이 참이다. | 도착점 도달. 이어 붙이기에는 유일성이 필요하지 않다(확인 11의 (나)). | | 기저 단계와 귀납 단계가 모두 성립하므로, 강한 귀납법에 의해 2 이상의 모든 정수는 소수이거나 소수들의 곱이다. $\blacksquare$ | 걸음 ⑤. 인용한 원리의 이름을 "강한 귀납법"으로 정확히 적는다. | **복기.** 이 증명이 약한 귀납으로 안 되는 이유는 계산이 어려워서가 아니라 **가정의 폭이 모자라서**다. 합성수의 두 인수는 $\sqrt{n+1}$ 근처까지 작아질 수 있어 $P(n)$ 하나로는 덮이지 않는다(S14주차 문제 13). 여기서 얻은 것은 산술의 기본정리의 **존재** 파트이고, 유일성 파트는 C15주차에서 청산한다. ### 예제 2.3 — 최소 반례법: 같은 명제, 다른 서식 **Result.** 모든 자연수 $n$ 에 대해 $\displaystyle\sum_{i=1}^n i = \frac{n(n+1)}2$ 이다. 이번에는 설계부터 스스로 해 보자. 이 명제는 §1.6의 첫째 물음에서 이미 약한 귀납으로 판정되는 것이고(1권 31주차 예제 2.1), 여기서는 일부러 최소 반례법으로 적는다. 같은 명제를 두 서식으로 적어 보면 두 서식의 대응이 눈에 들어온다. :::{container} quotebox **확인 18.** 정의 8.3의 다섯 걸음을 이 명제에 맞춰 각각 한 줄로 적어 보자. ① 무엇을 가정하는가 ② 무엇을 최소로 잡는가 ③ 무엇을 확인해 $m$ 의 아래끝을 올리는가 ④ 최소성에서 무엇을 얻어 무엇과 충돌시키는가 ⑤ 무엇을 선언하는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 이 공식이 성립하지 않는 자연수가 존재한다고 가정한다. ② 그런 자연수들의 집합에서 최소원소 $m$ 을 잡는다 [최소원리]. ③ $n = 1$ 에서 공식이 성립함을 확인해 $m \neq 1$, 곧 $m \ge 2$ 를 얻는다. ④ 최소성에서 $\sum_{i=1}^{m-1} i = \frac{(m-1)m}2$ 을 얻고, 여기에 $m$ 을 더해 $\sum_{i=1}^{m} i = \frac{m(m+1)}2$ 을 유도한다. 이것은 "$m$ 은 반례다"와 충돌한다. ⑤ 반례가 없으므로 모든 자연수에서 공식이 성립한다. ::: **증명.** 이 공식이 성립하지 않는 자연수가 존재한다고 가정하자. 그런 자연수 전체의 집합을 $R$ 이라 하면 $R$ 는 공집합이 아닌 자연수 집합이므로, 최소원리에 의해 $R$ 에는 최소원소가 존재한다. 그것을 $m$ 이라 하자. $n = 1$ 일 때 좌변은 $1$ 이고 우변은 $\frac{1 \cdot 2}2 = 1$ 로 같으므로 $1 \notin R$ 이고, 따라서 $m \ge 2$ 이다. 곧 $m - 1$ 은 자연수다. $m$ 이 $R$ 의 최소원소이고 $m-1 < m$ 이므로 $m - 1 \notin R$, 곧 $$ \sum_{i=1}^{m-1} i = \frac{(m-1)m}{2} $$ 이다. 양변에 $m$ 을 더하면 $$ \sum_{i=1}^{m} i = \frac{(m-1)m}{2} + m = \frac{m^2 - m + 2m}{2} = \frac{m(m+1)}{2} $$ 이므로 $m \notin R$ 이다. 이것은 $m \in R$ 라는 사실과 충돌하므로 모순이다. 따라서 $R$ 는 공집합이고, 모든 자연수 $n$ 에 대해 $\sum_{i=1}^n i = \frac{n(n+1)}2$ 이다. $\blacksquare$ 이번 증명은 표 없이 **산문**으로 적었다. 표는 연습 단계의 장치이고, 원서와 실전의 증명은 처음부터 끝까지 이런 산문이다. 이번 주의 목표는 이 산문을 백지에서 재현하는 것이다. **검산.** $n = 5$ 에서 좌변은 $1+2+3+4+5 = 15$ 이고 우변은 $\frac{5 \cdot 6}2 = 15$ 이다. ### 관찰 — 세 예제의 같은 뼈대 예제 2.1, 2.2, 2.3은 형태가 다르지만 하는 일이 같다. 대응표의 빈칸을 채워 보자. | **항목** | **예제 2.1 (약한)** | **예제 2.2 (강한)** | **예제 2.3 (최소 반례)** | |---|---|---|---| | 첫 칸을 놓은 줄 | 기저 $n = 1$ | 기저 $n = 2$ | $\underline{\quad(1)\quad}$ | | 가정으로 받은 것 | $P(n)$ 하나 | $\underline{\quad(2)\quad}$ | $m$ 보다 작은 곳은 전부 참 | | 한 칸을 만든 계산 | 마지막 항 분리 후 대입 | 인수 분해 후 두 가정 대입 | $\underline{\quad(3)\quad}$ | | 마무리 | 원 명제 선언 | 원 명제 선언 | 모순 지목 후 원 명제 선언 | :::{container} quotebox **확인 19.** 표의 (1)(2)(3)을 채우고, 세 예제가 공통으로 만든 것을 한 낱말로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) "$n = 1$ 에서 성립하므로 $1 \notin R$" — 기저를 확인해 최소 반례의 아래끝을 올린 줄이다. 위치만 옮겼을 뿐 계산은 예제 2.1의 기저와 같다. (2) $2$ 부터 $n$ 까지 전부, 곧 $P(2), \ldots, P(n)$. (3) $\sum_{i=1}^{m-1} i$ 에 $m$ 을 더해 $\sum_{i=1}^{m} i$ 를 얻은 계산 — 예제 2.1의 쪼개기를 $n \to n+1$ 대신 $m-1 \to m$ 으로 적은 것이다. 공통으로 만든 것: **한 칸**. 세 예제 모두 "바로 아래에서 참이면 여기서도 참"이라는 한 칸을 만들고, 그 칸을 어느 방향으로 쓰는지만 다르다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **귀납 답안의 공통 뼈대** 어느 형태를 쓰든 답안에는 세 가지가 반드시 있다. ① **첫 칸** — 기저 확인(최소 반례법에서는 기저 배제로 나타난다). ② **한 칸** — 아래에서 여기로 오는 계산. 이 계산의 재료가 되는 이전 항이 몇 개냐가 형태를 정한다. ③ **원리 인용과 선언** — 어느 원리로 무한을 덮었는지 이름을 밝히고 원 명제를 다시 적는다. 세 가지 중 하나라도 없으면 형태와 무관하게 미완성이다. ::: ## 빈칸 사다리 — 지지대를 하나씩 빼며 예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **Result.** 모든 자연수 $n$ 에 대해 $\displaystyle\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}6$ 이다. **증명.** $P(n)$ 을 위 등식이라 하고 약한 귀납으로 보인다. **(기저)** $n = 1$ 일 때 좌변은 $1^2 = 1$, 우변은 $\frac{1 \cdot 2 \cdot 3}6 = \underline{\quad(1)\quad}$ 이므로 $P(1)$ 이 참이다. **(귀납 단계)** $P(n)$ 을 가정하자. 마지막 항을 떼어 내면 $$ \sum_{i=1}^{n+1} i^2 = \left(\sum_{i=1}^{n} i^2\right) + \underline{\quad(2)\quad} = \frac{n(n+1)(2n+1)}6 + (n+1)^2 $$ 이고, 공통 인수 $(n+1)$ 로 묶으면 $$ = (n+1) \cdot \frac{n(2n+1) + 6(n+1)}6 = (n+1) \cdot \frac{2n^2 + 7n + 6}6 $$ 이다. 여기서 $2n^2 + 7n + 6 = (n+2)\big(\underline{\quad(3)\quad}\big)$ 이므로 $$ \sum_{i=1}^{n+1} i^2 = \frac{(n+1)(n+2)(2n+3)}6 = \frac{(n+1)\big((n+1)+1\big)\big(2(n+1)+1\big)}6 $$ 이고, 이것이 곧 $P(n+1)$ 이다. 기저 단계와 귀납 단계가 성립하므로 귀납의 원리에 의해 모든 자연수에서 등식이 성립한다. $\blacksquare$ 이 증명의 가정 소비처는 첫 등호 뒤에서 $\sum_{i=1}^n i^2$ 을 $\underline{\quad(4)\quad}$ 로 바꾼 순간이다. 검산: $n = 3$ 에서 좌변은 $1 + 4 + 9 = 14$ 이고 우변은 $\frac{3 \cdot 4 \cdot 7}6 = \underline{\quad(5)\quad}$ 이다. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장, 걸음 번호도 빈칸이다. **Result.** 모든 자연수 $n$ 에 대해 $4 \mid (5^n - 1)$ 이다. **증명.** 이 명제가 거짓인 자연수가 존재한다고 가정하고, 그런 자연수 전체의 집합을 $R$ 라 하자. $R$ 는 공집합이 아닌 자연수 집합이므로 $\underline{\quad(1)\quad}$ 에 의해 최소원소 $m$ 이 존재한다. $n = 1$ 일 때 $5^1 - 1 = 4$ 이고 $4 \mid 4$ 이므로 $1 \notin R$ 이다. 따라서 $\underline{\quad(2)\quad}$ 이고, $m - 1$ 은 자연수다 [걸음 $\underline{\quad(3)\quad}$]. $m$ 의 최소성에 의해 $m - 1 \notin R$ 이므로 $4 \mid (5^{m-1} - 1)$ 이고, 나누어떨어짐의 정의에 의해 $5^{m-1} - 1 = 4k$ 인 정수 $k$ 가 존재한다. 그러면 $$ 5^m - 1 = 5 \cdot 5^{m-1} - 1 = 5\big(\underline{\quad(4)\quad}\big) - 1 = 20k + 4 = \underline{\quad(5)\quad} $$ 이고, $5k + 1$ 은 정수이므로 [근거 $\underline{\quad(6)\quad}$] $4 \mid (5^m - 1)$ 이다. 곧 $m \notin R$ 이며, 이것은 $m \in R$ 와 충돌하므로 모순이다. 따라서 $R = \varnothing$ 이고, $\underline{\quad(7)\quad}$. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 형태를 고르는 것부터 시작한다. §1.6의 세 물음과 확인 5의 보폭 계산이 그대로 필요하다. **Result.** $24$ 이상의 모든 정수 $n$ 은 $n = 5a + 7b$ 인 음이 아닌 정수 $a, b$ 로 나타낼 수 있다. $23$ 까지는 이렇게 되지 않는 정수가 있다 — 예컨대 $23$ 은 $5a + 7b$ 꼴이 아니다 ($b = 0, 1, 2, 3$ 을 각각 넣어 보면 $23, 16, 9, 2$ 중 어느 것도 $5$ 의 배수가 아니다). **증명의 뼈대.** 각 칸을 통째로 채운다. - ① 형태 판정과 그 이유: $\underline{\quad(1)\quad}$ - ② 기저: 몇 개를 두어야 하는지와 각각의 표현: $\underline{\quad(2)\quad}$ - ③ 귀납 단계: $\underline{\quad(3)\quad}$ - ④ 마무리: $\underline{\quad(4)\quad}$ (문제 12가 같은 뼈대를 3원$\cdot$5원 무대에서 다룬다 — 보폭이 달라지면 기저 개수가 어떻게 달라지는지 두 문제를 나란히 놓고 확인한다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. 형태마다 채점 항목이 정해져 있다. 약한 귀납: 기저의 좌$\cdot$우변 계산 + 쪼개기 줄 + **가정 소비처를 짚을 수 있는가** + 원리 인용. 강한 귀납: 가정의 폭을 "$n_0 \le i \le n$ 인 모든 $i$" 로 정확히 적었는가 + 기저 개수가 보폭과 맞는가 + 쓴 항이 가정 안에 있는지 확인했는가. 최소 반례법: 다섯 걸음 전부 + 최소원리 인용 + **충돌한 두 문장의 지목** + 기저 배제. 어느 형태든 "가정에 의해"라고 적힌 줄을 손가락으로 짚을 수 없으면 미완성이다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 약한 귀납의 원리, 강한 귀납법, 최소 반례법의 다섯 걸음, 그리고 §1.6의 세 형태 대응표를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 서식은 걸음의 목록만 외우면 절반이다. 걸음마다 "이것을 빼면 무엇이 무너지는가"를 함께 적어 두면, 일부를 잊었을 때 나머지에서 복구할 수 있다. §1.2와 §1.4의 두 해부 표가 그 복구의 재료다. ::: **2.** 다음 각 명제에 어느 형태(약한 귀납 / 강한 귀납 / 최소 반례법)가 자연스러운지 판정하고, 판정의 이유를 한 줄씩 쓰시오 (증명은 하지 말 것). (a) $\displaystyle\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2$ (b) 모든 정수 $n \ge 2$ 는 소수들의 곱이다 (c) 피보나치 수열에서 $F_n < 2^n$ (d) $4a + 5b$ ($a, b$ 는 음이 아닌 정수) 꼴로 표현되지 않는 최대 정수는 $11$ 이다 :::{admonition} 힌트 :class: quotebox dropdown 판정의 절차는 §1.6의 세 물음이다. 각 명제에서 $P(n+1)$ 을 쪼개는 첫 줄만 적어 보고, 그 줄이 요구하는 이전 항이 몇 개이며 그중 직전이 아닌 것이 있는지 세면 된다. (d)는 다른 셋과 성격이 다르다 — "최대"라는 낱말이 요구하는 것이 두 가지임에 유의한다. ::: **3.** 예제 2.1(홀수의 합)을 백지에 재현하시오. 쪼개기 줄과 가정 소비처를 각각 표시하시오. :::{admonition} 힌트 :class: quotebox dropdown 다섯 걸음 중 쪼개기는 확인 14가 만든 줄이고, 가정 소비처는 확인 15의 첫 등호다. 쪼개기에서 떼어 내는 항은 새로 늘어난 항 $2(n+1)-1$ 이지 $2n-1$ 이 아니다. 마지막 줄에서 원 명제를 다시 적었는지까지가 채점 대상이다. ::: **4.** 빈칸 사다리의 훈련 1~3을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 1은 (4)가 유일한 가정 소비처이므로 그 한 줄을 먼저 정하고 나머지를 맞춘다. 훈련 2는 (4)가 최소성 소비처이고, 그 앞의 (2) 기저 배제가 없으면 그 줄이 뜻을 잃는다. 훈련 3은 §1.6의 세 물음으로 형태를 고른 뒤 확인 5의 보폭 계산으로 기저 개수를 정한다. ::: **5.** 예제 2.3(최소 반례법)을 백지에 재현하고, 예제 2.1과 나란히 놓아 다섯 걸음이 약한 귀납의 어느 걸음에 대응하는지 표로 대조하시오. :::{admonition} 힌트 :class: quotebox dropdown 대조표의 행은 확인 8에서 이미 두 개를 만들었다. 나머지 걸음(①②⑤)이 약한 귀납의 어디에 해당하는지 — 또는 대응하는 것이 없는지 — 를 채우면 표가 완성된다. ::: **6.** 모든 자연수 $n$ 에 대해 $3 \mid (n^3 - n)$ 임을 약한 귀납으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 쪼개기 줄은 S14주차 예제 2.2가 다룬 그 계산이다. $(n+1)^3 - (n+1)$ 을 전개한 뒤 $n^3 - n$ 덩어리가 그대로 보이도록 재그룹하면 남는 것이 $3n^2 + 3n$ 이다. 나머지 항이 $3$ 의 배수임을 별도로 보이는 것이 가정 소비 다음의 일이다. ::: ### 표준 ●●○ **7.** 모든 자연수 $n$ 에 대해 $\displaystyle\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2$ 임을 약한 귀납으로 증명하시오 (S14주차 문제 8). :::{admonition} 힌트 :class: quotebox dropdown 가정을 대입하면 $\left(\frac{n(n+1)}2\right)^2 + (n+1)^3$ 이 된다. 공통 인수 $(n+1)^2$ 으로 묶으면 남는 것이 $\frac{n^2}4 + (n+1)$ 이고, 통분하면 완전제곱이 나온다. ::: **8.** 모든 정수 $n \ge 4$ 에 대해 $2^n \ge n^2$ 임을 귀납으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 기저는 $n = 4$ 다 ($16 \ge 16$). 귀납 단계에서 가정을 소비하면 $2^{n+1} \ge 2n^2$ 까지만 간다. 도착점은 $(n+1)^2$ 이므로 $2n^2 \ge (n+1)^2$ 을 **따로** 보여 이어 붙여야 한다 — 1권 32주차에서 연결 부등식이라 부른 그 조각이다. 정리하면 $n^2 - 2n - 1 \ge 0$, 곧 $(n-1)^2 \ge 2$ 를 보이는 문제가 된다. ::: **9.** $F_1 = F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$ 으로 정의된 피보나치 수열에 대해, 모든 자연수 $n$ 에서 $F_n \le 2^{n-1}$ 임을 증명하시오. 기저가 두 개 필요한 이유도 쓰시오 (S14주차 문제 15의 상계를 조인 판이다). :::{admonition} 힌트 :class: quotebox dropdown 점화식이 두 항을 참조하므로 보폭이 $2$ 이고, 따라서 기저도 두 개다(확인 5의 계산). 귀납 단계에서 $2^n + 2^{n-1}$ 을 $2^{n-1}$ 로 묶으면 $3 \cdot 2^{n-1}$ 이 되고, 도착점 $2^{n+1} = 4 \cdot 2^{n-1}$ 과 계수만 비교하면 끝난다. ::: **10.** 다음 제시된 증명을 C5주차의 증명 평가 다섯 걸음으로 채점하시오. 판정은 옳음$\cdot$틀림$\cdot$불완전 가운데 하나로 적고, 결함이 있는 줄을 지목한 뒤 병명(S11주차의 어휘)과 수리를 덧붙이시오. :::{container} quotebox **Result.** 모든 자연수 $n$ 에 대해 $\displaystyle\sum_{i=1}^n i = \frac{n(n+1)}2$ 이다. **증명.** 귀납 단계에서 $\sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}2$ 임을 보이자. 등차수열의 합 공식에 의해 이는 참이다. $\blacksquare$ ::: :::{admonition} 힌트 :class: quotebox dropdown 검사할 질문은 둘이다. 다섯 걸음 중 몇 개가 답안에 실제로 있는가. 그리고 인용된 "등차수열의 합 공식"은 근거 목록의 몇 번이며, 이 과정에서 증명된 적이 있는가. 확인 3이 같은 답안을 다루었다. ::: **11.** 모든 자연수 $n$ 에 대해 $\displaystyle\sum_{i=1}^n (2i-1) = n^2$ 임을 최소 반례법으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.3의 다섯 걸음을 그대로 옮기고 재료만 바꾼다. 걸음 ④에서 더할 항은 $2m - 1$ 이다 — 확인 14에서 본 대로, 떼어 낼 항은 새로 늘어난 항이다. 기저 배제(걸음 ③)를 빼면 확인 7의 붕괴가 재연된다. ::: **12.** $8$ 이상의 모든 정수는 3원 동전과 5원 동전으로 지불할 수 있음을 강한 귀납으로 증명하시오. 기저를 몇 개 잡아야 하는지 결정한 근거도 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 기저 개수는 §1.3의 삭제 실험(확인 5)이 이미 계산했다. 귀납 단계에서 쓸 항은 $P(n-2)$ 이므로, 그 항이 가정의 사정권 안에 있으려면 $n - 2 \ge 8$, 곧 $n + 1 \ge 11$ 이어야 한다. 그 아래 세 값을 손으로 채운다. ::: **13.** 모든 자연수 $n$ 에 대해 $6 \mid (n^3 + 5n)$ 임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 쪼개기 줄에서 $(n+1)^3 + 5(n+1)$ 을 전개해 $n^3 + 5n$ 덩어리를 드러내면 남는 것이 $3n^2 + 3n + 6$ 이다. $3n^2 + 3n = 3n(n+1)$ 이고, $n(n+1)$ 이 짝수라는 사실(§1.7의 목록, 1권 1주차 문제 16)을 쓰면 이 항이 $6$ 의 배수임이 나온다. ::: **14.** $x^2 = 3y^2$ 인 양의 정수 $x, y$ 는 존재하지 않음을 무한강하로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown C7주차 문제 17의 $\sqrt2$ 판을 $\sqrt3$ 으로 옮긴 것이다. 최소로 잡을 양은 $x$ 다. $3 \mid x^2$ 에서 $3 \mid x$ 로 가는 줄에 유클리드 보조정리($p = 3$)를 인용한다. $x = 3x'$ 을 대입하고 정리하면 $y^2 = 3x'^2$ 이 되어 같은 논증이 $y$ 에서 한 번 더 돈다. ::: ### 도전 ●●● **15.** 모든 정수 $n \ge 2$ 는 소수인 약수를 가짐을 강한 귀납으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2와 형태도 무대도 같지만 결론이 더 약하다 — 분해 전체가 아니라 소인수 **하나**만 있으면 된다. 그래서 합성수 $n+1 = ab$ 에서 $a$ 에만 가정을 쓰면 되고, 마지막에 $p \mid a$ 와 $a \mid (n+1)$ 을 이어 붙이는 데 나누어떨어짐의 추이성 (1권 2주차)이 필요하다. 이 명제는 S11주차 문제 15(소수의 무한성)가 부품으로 쓰는 사실이고, 1권 33주차 문제 6이 같은 것을 따름정리로 유도한다. ::: **16.** 어느 세 점도 한 직선 위에 있지 않은 $n$ 개의 점에 대해, 그들을 서로 잇는 선분의 개수가 $\binom n2$ 임을 귀납으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 기저는 $n = 2$ 다. 귀납 단계에서 $n+1$ 번째 점을 추가하면 기존 $n$ 개 각각과 새 선분이 하나씩 생기므로 늘어나는 개수가 $n$ 이다. 남는 일은 $\binom n2 + n = \binom{n+1}2$ 을 §1.7의 이항계수 값으로 계산해 확인하는 것뿐이다. (C16주차 조합론의 예고편이다.) ::: **17.** $x > -1$ 인 모든 실수 $x$ 와 모든 자연수 $n$ 에 대해 $(1+x)^n \ge 1 + nx$ 임을 증명하시오 (베르누이 부등식). 조건 $x > -1$ 이 귀납 단계의 어느 줄에서 소비되는지 명시하시오. :::{admonition} 힌트 :class: quotebox dropdown 가정의 양변에 $1+x$ 를 곱하는 것이 쪼개기다. 부등식의 양변에 곱할 때는 곱하는 수의 **부호**를 먼저 밝혀야 부등호 방향이 보존된다 — 조건 $x > -1$ 이 소비되는 자리가 정확히 거기다. 곱한 뒤 남는 $nx^2$ 을 버리는 것이 마지막 걸음이다. ::: **18.** 다음 제시된 증명의 결함을 찾고, 무엇이 무너졌는지 지적하시오. :::{container} quotebox **Result.** 모든 자연수 $n$ 에 대해 $n < 100$ 이다. **증명.** 강한 귀납으로 보인다. 기저는 $n = 1$ 이고 $1 < 100$ 이다. 귀납 단계에서 $1, \ldots, n$ 이 모두 $100$ 보다 작다고 가정하면 $n < 100$ 이므로 $n + 1 \le 100$ 이고, 따라서 성립한다. $\blacksquare$ ::: :::{admonition} 힌트 :class: quotebox dropdown 결론이 명백히 거짓이므로 오류는 반드시 있다. 그런데 기저는 옳으니 남은 곳은 귀납 단계뿐이다. 귀납 단계는 "**모든** $n$ 에 대해" 성립해야 하는 조건문임을 떠올리고, $n$ 에 구체적인 값을 하나씩 넣어 조건문이 거짓이 되는 $n$ 을 찾는다. 답안이 도착한 곳($n+1 \le 100$)과 도착해야 할 곳($n+1 < 100$)의 차이도 함께 본다. ::: **19.** 모든 자연수 $n$ 에 대해 $n! \ge 2^{n-1}$ 임을 (a) 약한 귀납으로 (b) 최소 반례법으로 각각 증명하고, 어느 쪽이 자연스러운지 이유와 함께 논하시오. :::{admonition} 힌트 :class: quotebox dropdown 두 풀이의 계산은 같다. $(n+1)! = (n+1) \cdot n!$ 이라는 쪼개기가 (a)의 관절이고, $m! = m \cdot (m-1)!$ 이 (b)의 관절이다. 가정을 대입한 뒤 $n + 1 \ge 2$ (또는 $m \ge 2$)를 써서 계수를 $2$ 로 눌러 놓는 줄이 양쪽 모두에 필요하다. 논의에서는 §1.6의 첫째 물음이 어느 쪽을 가리키는지를 근거로 삼는다. ::: **20.** (서술) (a) "귀납 단계 = 조건문 증명"(S14주차)을 예제 2.1의 특정 줄로 뒷받침하고, "최소 반례법 = 귀납의 귀류판"을 예제 2.3의 특정 줄로 뒷받침한 뒤, 두 서식이 같은 명제를 증명한다는 것을 세 문장 이내로 쓰시오. (b) 강한 귀납이 필요한 이유(직전이 아닌 이전 항에 대한 의존)를 예제 2.2로 두 문장 이내로 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown 서술 문항의 답안은 개념 절의 문장을 옮겨 적는 것이 아니라, **지정된 예제의 어느 줄이 그 개념의 근거인지** 짚는 글이다. (a)는 예제 2.1에서 "가정을 선언한 줄"과 "가정을 소비한 줄", 예제 2.3에서 "기저를 배제한 줄"과 "최소성을 소비한 줄"을 각각 짚어야 점수가 된다. (b)는 예제 2.2에서 "부등식을 $2 \le a \le n$ 으로 정리한 줄"이 왜 필요했는지를 짚는다. ::: ## 백지 재현 — 복습 프로토콜 이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Chartrand 6장 통독 — 모르는 문장은 표시만 하고 통과한다 | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다 | | 3일차 | 원서 6장 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다 | | 4일차 | 교안 §3 빈칸 사다리와 §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | **1차 시도 — 틀 카드 허용.** 세 형태의 원리(정의 8.1$\cdot$8.2$\cdot$8.3)와 §1.6의 세 물음만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 본문과 계산은 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 정의 8.1(약한 귀납)과 정의 8.2(강한 귀납)를 $n_0$ 을 명시한 꼴로 썼고, 두 정의의 차이가 어디인지 손가락으로 짚었다. - [ ] 최소 반례법의 다섯 걸음을 순서대로 썼고, 걸음 ③을 빼면 무엇이 무너지는지 한 문장으로 적었다. - [ ] 예제 2.1을 재현하면서 쪼개기 줄과 가정 소비처를 각각 표시했다. - [ ] 예제 2.2를 재현했고, 약한 귀납으로 안 되는 이유를 "가정의 폭"이라는 말로 적었다. - [ ] 예제 2.3을 산문으로 재현했고, 충돌한 두 문장을 이름으로 지목했다. - [ ] 세 형태의 대응표(§1.6)를 그렸고, 셋의 논리적 힘이 같다는 것과 그 근거를 적었다. - [ ] 강한 귀납에서 기저 개수를 정하는 것이 무엇인지 쓰고, 3원$\cdot$5원 무대에서 그 개수를 계산했다. - [ ] 무한강하가 최소 반례법의 어느 걸음의 변주인지 적었다. - [ ] 원서 6장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 어느 형태를 쓸지 정하지 못한다 | §1.6의 세 물음 — $P(n+1)$ 을 쪼개는 첫 줄만 적어 보면 필요한 이전 항이 드러난다 | | 귀납 단계에서 다음 줄이 나오지 않는다 | §1.2의 걸음 ③ — 막히는 자리의 대부분이 쪼개기다. 도착점의 식에서 가정의 식을 찾는다 | | 답안을 다 썼는데 가정 소비처를 못 짚는다 | 확인 3 — 병명은 가정 미소비다. 그 답안은 순환일 가능성이 높다 | | 기저를 몇 개 잡아야 할지 모른다 | 확인 5 — 귀납 단계의 목표가 $P(N)$ 이고 그것이 쓰는 가장 깊은 항이 $P(N-s)$ 이면 보폭은 $s$ 이고 기저도 $s$ 개다 | | 최소 반례법의 첫 문장이 나오지 않는다 | 정의 8.3의 걸음 ①② — 개시문은 "반례가 존재한다고 가정하자"와 "최소원리에 의해" 두 줄로 정해져 있다 | | 모순이라고 적었는데 당사자를 못 짚는다 | 예제 2.3의 마지막 두 줄 — 충돌한 두 문장은 "$m \in R$" 과 "$m \notin R$" 이다 | | 부등식 귀납에서 도착점에 못 닿는다 | 문제 8의 힌트 — 가정 소비 뒤에 연결 부등식을 따로 세워 이어 붙인다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $1$ (2) $(n+1)^2$ (3) $2n+3$ (4) $\frac{n(n+1)(2n+1)}6$ (5) $14$ ※ (2)에서 떼어 낼 항은 $i = n+1$ 일 때의 항이므로 $(n+1)^2$ 이다. $n^2$ 으로 적으면 $i = n$ 일 때의 항이 되어 아무것도 늘지 않는다. (3)의 인수분해는 $2n^2 + 7n + 6 = (n+2)(2n+3)$ 이고, 곱을 전개해 $2n^2 + 3n + 4n + 6 = 2n^2 + 7n + 6$ 으로 검산한다. (4)가 이 훈련의 가정 소비처이고, 훈련 전체에서 가정 $P(n)$ 이 쓰인 자리는 여기 한 곳뿐이다. ### 빈칸 사다리 — 훈련 2 (1) 최소원리 (정렬성) (2) $m \ge 2$ (3) ③ (기저 배제) (4) $4k+1$ (5) $4(5k+1)$ (6) ② (닫힘성) (7) 모든 자연수 $n$ 에 대해 $4 \mid (5^n - 1)$ 이다 ※ (4)는 가정 소비처다 — $5^{m-1} - 1 = 4k$ 를 $5^{m-1} = 4k+1$ 로 옮겨 대입한 순간에만 최소성이 쓰였다. (5)에서 $20k + 4 = 4(5k+1)$ 로 묶는 것이 도착점의 꼴 "$4 \times (\text{정수})$" 를 만드는 줄이고, 그 괄호 안이 정수임을 밝히는 것이 (6)이다. 검산: $n = 3$ 에서 $5^3 - 1 = 124 = 4 \cdot 31$ 이다. ### 빈칸 사다리 — 훈련 3 (1) **강한 귀납.** $n+1$ 을 $(n+1) - 5$ 로 되돌려 가정을 쓰므로 귀납 단계가 실제로 사용하는 항은 $P(n-4)$ 이고, 이것은 직전 항이 아니다. §1.6의 둘째 물음에 걸린다. (2) **기저는 다섯 개** — $24, 25, 26, 27, 28$. 되돌아보는 보폭이 $5$ 이므로 그만큼의 칸을 손으로 채워야 재귀가 돈다(확인 5의 계산). 각각의 표현은 $24 = 5 \cdot 2 + 7 \cdot 2$, $25 = 5 \cdot 5$, $26 = 5 + 7 \cdot 3$, $27 = 5 \cdot 4 + 7$, $28 = 7 \cdot 4$ 이다. (3) **귀납 단계.** $n \ge 28$ 이라 하고, $24 \le i \le n$ 인 모든 정수 $i$ 가 $5a+7b$ 꼴이라고 가정하자. 이때 $n + 1 \ge 29$ 이므로 $(n+1) - 5 = n - 4 \ge 24$ 이고, 가정에 의해 $n - 4 = 5a' + 7b'$ 인 음이 아닌 정수 $a', b'$ 이 존재한다. 그러면 $n + 1 = (n-4) + 5 = 5(a'+1) + 7b'$ 이고 $a' + 1$ 과 $b'$ 은 음이 아닌 정수이므로 $P(n+1)$ 이 참이다. (4) **마무리.** 기저 단계와 귀납 단계가 모두 성립하므로, 강한 귀납법에 의해 $24$ 이상의 모든 정수는 $5a + 7b$ 꼴이다. $\blacksquare$ ※ 문제 12와 나란히 놓으면 보폭과 기저 개수의 관계가 보인다. 3원$\cdot$5원 무대에서는 작은 동전이 $3$ 이라 보폭이 $3$ 이고 기저가 셋($8, 9, 10$)이며, 5원$\cdot$7원 무대에서는 작은 동전이 $5$ 라 보폭이 $5$ 이고 기저가 다섯이다. ### 문제 1 **접근.** 백지 문항의 채점은 문장의 유무가 아니라 **조각의 유무**로 한다. 네 항목 각각에서 빠지면 무너지는 조각이 무엇인지 §1.2와 §1.4의 해부 표로 확인해 두면, 일부를 잊었을 때 나머지에서 복구할 수 있다. **풀이.** 아래 네 항목이 모두 있어야 만점이다. **① 약한 귀납의 원리(정의 8.1).** "정수 $n_0$ 이상의 모든 $n$ 에 대해 $P(n)$ 을 보이려면 ㉠ $P(n_0)$ 이 참이고 ㉡ $n_0$ 이상의 모든 $n$ 에 대해 $P(n) \Rightarrow P(n+1)$ 임을 보이면 충분하다." 채점 조각은 $n_0$ 의 명시와 ㉡의 "모든 $n$ 에 대해"다. ㉡에서 "모든"이 빠지면 문제 18의 결함을 진단할 수 없다. **② 강한 귀납법(정의 8.2).** 귀납 단계의 출발점이 "$n_0 \le i \le n$ 인 모든 $i$ 에 대한 $P(i)$" 이고, 기저가 여러 개일 수 있다는 것. 채점 조각은 가정의 폭을 구간으로 적었는가와 기저 개수를 보폭이 정한다고 적었는가다. **③ 최소 반례법의 다섯 걸음(정의 8.3).** 귀류 개시 $\to$ 최소 반례 확보(최소원리) $\to$ 기저 배제 $\to$ 최소성 소비와 모순 $\to$ 결론 복귀. 채점 조각은 걸음 ③의 존재다 — 이것이 없으면 확인 7의 붕괴가 재연된다. **④ 세 형태의 대응표(§1.6).** 형태 $\cdot$ 귀납 단계의 출발점 $\cdot$ 논법의 방향 세 열을 채우고, 셋이 최소원리에서 나오며 논리적 힘이 같다는 문장을 덧붙인다. **복기.** 서식 암기의 검사법은 "빼면 무엇이 무너지는가"를 걸음마다 한 줄씩 말해 보는 것이다. 말할 수 있으면 그 걸음은 외운 것이고, 말할 수 없으면 적어만 둔 것이다. ### 문제 2 **접근.** 판정 절차는 §1.6의 세 물음이다. 명제마다 $P(n+1)$ 을 쪼개는 첫 줄만 적어 보고, 그 줄이 요구하는 이전 항의 개수와 위치를 센다. 증명을 하지 않고도 판정만으로 답이 되는 문항이므로, 이유 한 줄이 곧 채점 대상이다. **풀이.** **(a) 약한 귀납.** 쪼개기 줄은 $\sum_{i=1}^{n+1} i^3 = \left(\sum_{i=1}^{n} i^3\right) + (n+1)^3$ 이다. 요구하는 이전 항은 $P(n)$ 하나이고 그것이 직전이므로 첫째 물음에서 걸린다. **(b) 강한 귀납.** 쪼개기 줄은 $n+1 = ab$ ($2 \le a \le n$, $2 \le b \le n$)이다. 요구하는 항이 $P(a)$ 와 $P(b)$ 둘이고, 그것이 구간의 어디인지 미리 알 수 없다. 둘째 물음에 걸린다. **(c) 강한 귀납.** 쪼개기 줄은 점화식 $F_{n+2} = F_{n+1} + F_n$ 자체다. 요구하는 항이 $P(n)$ 과 $P(n+1)$ 둘이므로 둘째 물음에 걸리고, 보폭이 $2$ 이므로 기저도 두 개다. **(d) 강한 귀납 + 유한 검사.** "최대"라는 낱말은 두 가지를 요구한다. ㉠ $11$ 자신이 $4a+5b$ 꼴이 아님 — 이것은 $b = 0, 1, 2$ 에서 각각 $11, 6, 1$ 이 되어 어느 것도 $4$ 의 배수가 아니라는 유한 검사로 끝난다. ㉡ $12$ 이상의 모든 정수는 그 꼴임 — 이쪽이 무한 주장이고, 귀납 단계가 $P(n-3)$ 을 쓰므로 보폭 $4$ 의 강한 귀납이다(기저 $12, 13, 14, 15$). 1권 33주차 문제 12가 ㉡을 다룬다. **복기.** 판정에서 최소 반례법이 답이 되는 경우는 (d)처럼 "최대"$\cdot$"없다"가 들어간 명제이거나, 사다리를 걸 변수 자체가 없는 명제다. (d)의 ㉡은 사다리가 있으므로 굳이 귀류로 갈 이유가 없다 — 형태 선택은 답안이 짧아지는 쪽을 고르는 일이다. ### 문제 3 **접근.** 재현 문항의 채점 대상은 결과가 아니라 걸음이다. 다섯 걸음이 모두 있는가, 그리고 쪼개기 줄과 가정 소비처를 스스로 지목할 수 있는가를 본다. **풀이.** $P(n)$ 을 "$\sum_{i=1}^n (2i-1) = n^2$" 이라 하자. **(기저)** $n = 1$ 일 때 좌변은 $2 \cdot 1 - 1 = 1$, 우변은 $1^2 = 1$ 이므로 $P(1)$ 이 참이다. **(귀납 단계)** $n$ 을 자연수라 하고 $P(n)$ 을 가정하자. 그러면 $$ \sum_{i=1}^{n+1}(2i-1) = \left(\sum_{i=1}^{n}(2i-1)\right) + \big(2(n+1)-1\big) = n^2 + (2n+1) = (n+1)^2 $$ 이므로 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 $n$ 에 대해 $\sum_{i=1}^n (2i-1) = n^2$ 이다. $\blacksquare$ **표시.** 쪼개기 줄은 첫 등호가 있는 줄이고, 가정 소비처는 둘째 등호에서 $\sum_{i=1}^n (2i-1)$ 을 $n^2$ 으로 바꾼 지점이다. 셋째 등호는 완전제곱 정리이므로 근거 ③이며 가정과 무관하다. **검산.** $n = 4$ 에서 $1+3+5+7 = 16 = 4^2$ 이다. ### 문제 4 **접근.** 사다리의 자가 채점은 답을 맞혔는가가 아니라 **관절을 짚었는가**로 한다. 훈련마다 관절이 하나씩 있고, 그 줄을 틀리면 나머지가 다 맞아도 증명이 서지 않는다. **풀이.** 답은 위의 "빈칸 사다리 — 훈련 1~3" 항목에 있다. 대조할 때 다음 세 가지를 확인한다. **훈련 1의 관절 — (2).** 떼어 낼 항이 $(n+1)^2$ 인가. $n^2$ 으로 적었다면 새로 늘어난 항이 아니라 이미 합 안에 있던 항을 떼어 낸 것이므로, 그 아래의 계산 전체가 무너진다. **훈련 2의 관절 — (2)와 (3).** 기저 배제를 적었는가. $m \ge 2$ 를 확보하지 않으면 $m - 1$ 이 자연수라는 보장이 없고, 그러면 "$m-1$ 은 반례가 아니다"라는 문장이 아무것도 말하지 못한다(확인 7). **훈련 3의 관절 — (2)의 개수.** 기저를 다섯 개 두었는가. 하나만 두면 $n+1$ 이 $25, 26, 27, 28$ 일 때 $(n+1) - 5$ 가 $24$ 보다 작아 가정의 사정권 밖으로 나간다 — 확인 5의 삭제 실험이 그대로 재연된다. **복기.** 세 관절은 각각 "쪼개기", "기저 배제", "기저 개수"다. §1.2$\cdot$§1.4의 해부 표에서 "빼면 무너지는 것"으로 적혀 있던 항목이 사다리에서 그대로 채점 항목이 된다. ### 문제 5 **접근.** 대조표를 만들려면 먼저 두 증명을 각각 재현해야 한다. 재현한 뒤에는 걸음 단위로 줄을 짝지어 본다 — 계산이 같고 방향만 다른 짝이 두 개 나온다(확인 8). **풀이 — 재현.** 예제 2.3의 증명은 다음과 같다. 공식이 성립하지 않는 자연수 전체의 집합을 $R$ 라 하고 $R \neq \varnothing$ 이라 가정하자. 최소원리에 의해 $R$ 에 최소원소 $m$ 이 있다. $n = 1$ 에서 $1 = \frac{1 \cdot 2}2$ 이므로 $1 \notin R$ 이고 $m \ge 2$ 이다. 최소성에 의해 $m - 1 \notin R$ 이므로 $\sum_{i=1}^{m-1} i = \frac{(m-1)m}2$ 이고, $$ \sum_{i=1}^{m} i = \frac{(m-1)m}{2} + m = \frac{m(m+1)}{2} $$ 이므로 $m \notin R$ 이다. $m \in R$ 와 충돌하므로 모순이고, 따라서 $R = \varnothing$ 이다. $\blacksquare$ **풀이 — 대조표.** | **최소 반례법 (예제 2.3)** | **약한 귀납 (예제 2.1)** | **관계** | |---|---|---| | ① 반례가 존재한다고 가정 | 대응하는 것 없음 | 귀류 개시는 최소 반례법에만 있다 | | ② 최소원리로 최소 반례 $m$ 확보 | 대응하는 것 없음 | 최소원리를 명시적으로 인용하는 유일한 걸음 | | ③ $1 \notin R$ 확인 $\to$ $m \ge 2$ | 기저 $P(1)$ 확인 | **계산이 같다.** 쓰는 곳만 다르다 | | ④ $P(m-1) \Rightarrow P(m)$ 유도 후 모순 | $P(n) \Rightarrow P(n+1)$ 유도 | **계산이 같다.** 방향만 뒤집혔다 | | ⑤ 반례 없음 $\to$ 원 명제 | 원리 인용 $\to$ 원 명제 | 결론 선언은 양쪽 모두에 있다 | **복기.** 두 서식의 실질적 차이는 ①②의 두 줄뿐이다. 같은 계산을 위로 타고 올라가면 귀납이고, 아래에서 이미 참이었다는 사실로 최소성을 깨뜨리면 최소 반례법이다. 그래서 최소 반례법을 귀납의 귀류판이라 부른다(S14주차 문제 14). ### 문제 6 **접근.** 나누어떨어짐 명제이므로 $P(n)$ 을 "$n^3 - n = 3m$ 인 정수 $m$ 이 존재한다"로 번역해 두고 시작한다. 쪼개기는 $(n+1)^3 - (n+1)$ 을 전개해 $n^3 - n$ 덩어리를 드러내는 일이고, 남는 항이 $3$ 의 배수임을 별도로 밝히는 것이 마무리다. **풀이.** $P(n)$ 을 "$3 \mid (n^3 - n)$" 이라 하자. **(기저)** $n = 1$ 일 때 $n^3 - n = 1 - 1 = 0$ 이고 $0 = 3 \cdot 0$ 이므로 $3 \mid 0$ 이다. 따라서 $P(1)$ 이 참이다. **(귀납 단계)** $n$ 을 자연수라 하고 $P(n)$ 을 가정하자. 곧 $n^3 - n = 3m$ 인 정수 $m$ 이 존재한다. 전개하면 $$ (n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3n^2 + 3n $$ 이고, 가정을 대입하면 $$ (n+1)^3 - (n+1) = 3m + 3n^2 + 3n = 3\big(m + n^2 + n\big) $$ 이다. $m$ 과 $n$ 이 정수이므로 $m + n^2 + n$ 도 정수이고 [근거 ②], 따라서 $3 \mid \big((n+1)^3 - (n+1)\big)$ 이다. 곧 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 $n$ 에 대해 $3 \mid (n^3 - n)$ 이다. $\blacksquare$ **복기.** 나누어떨어짐 귀납의 리듬은 세 박자다 — 전개 $\to$ 가정의 덩어리 드러내기 $\to$ 남는 항에서 공통 인수 묶기. S14주차 예제 2.2가 같은 리듬이고, 문제 13이 이 리듬을 $6$ 으로 확장한다. **검산.** $n = 3$ 에서 $27 - 3 = 24 = 3 \cdot 8$ 이다. ### 문제 7 **접근.** 가정을 대입하면 $\left(\frac{n(n+1)}2\right)^2 + (n+1)^3$ 이 되고, 도착점은 $\left(\frac{(n+1)(n+2)}2\right)^2$ 이다. 양쪽 모두 $(n+1)^2$ 을 인수로 가지므로 그것으로 묶어 놓고 나머지를 비교하는 것이 계산량이 가장 적다. **풀이.** $P(n)$ 을 "$\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2$" 이라 하자. **(기저)** $n = 1$ 일 때 좌변은 $1^3 = 1$, 우변은 $\left(\frac{1 \cdot 2}2\right)^2 = 1$ 이므로 $P(1)$ 이 참이다. **(귀납 단계)** $P(n)$ 을 가정하자. 마지막 항을 떼어 내고 가정을 대입하면 $$ \sum_{i=1}^{n+1} i^3 = \left(\sum_{i=1}^{n} i^3\right) + (n+1)^3 = \left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3 $$ 이다. $(n+1)^2$ 으로 묶으면 $$ = (n+1)^2\left(\frac{n^2}{4} + (n+1)\right) = (n+1)^2 \cdot \frac{n^2 + 4n + 4}{4} = (n+1)^2 \cdot \frac{(n+2)^2}{4} $$ 이고, 이것은 $\left(\frac{(n+1)(n+2)}{2}\right)^2$ 이다. $n+2 = (n+1)+1$ 이므로 이 식은 $P(n+1)$ 의 우변과 같다. 곧 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 $n$ 에 대해 $\sum_{i=1}^n i^3 = \left(\frac{n(n+1)}2\right)^2$ 이다. $\blacksquare$ **복기.** 도착점의 식을 먼저 적어 두면 "무엇으로 묶을지"가 저절로 정해진다. 여기서는 도착점에 $(n+1)^2$ 이 들어 있는 것이 보였으므로 그것을 묶었다. 도착점을 적지 않고 좌변만 밀면 $\frac{n^2(n+1)^2 + 4(n+1)^3}4$ 에서 길을 잃기 쉽다. **검산.** $n = 3$ 에서 좌변은 $1 + 8 + 27 = 36$ 이고 우변은 $\left(\frac{3 \cdot 4}2\right)^2 = 36$ 이다. ### 문제 8 **접근.** 부등식 귀납은 2단이다. 가정을 소비하면 중간값까지만 가고, 거기서 도착점까지는 **연결 부등식**을 따로 세워 이어 붙인다(1권 32주차). 여기서 중간값은 $2n^2$ 이고 도착점은 $(n+1)^2$ 이므로, 세워야 할 연결 부등식은 $2n^2 \ge (n+1)^2$ 이다. **풀이.** $P(n)$ 을 "$2^n \ge n^2$" 이라 하고 $n_0 = 4$ 로 둔다. **(기저)** $n = 4$ 일 때 $2^4 = 16$ 이고 $4^2 = 16$ 이므로 $2^4 \ge 4^2$ 이다. 따라서 $P(4)$ 가 참이다. **(연결 부등식)** $n \ge 3$ 인 모든 정수에서 $2n^2 \ge (n+1)^2$ 이다. 실제로 $$ 2n^2 - (n+1)^2 = n^2 - 2n - 1 = (n-1)^2 - 2 $$ 이고, $n \ge 3$ 이면 $(n-1)^2 \ge 4 > 2$ 이므로 이 값은 양수다. **(귀납 단계)** $n \ge 4$ 라 하고 $P(n)$ 을 가정하자. 그러면 $$ 2^{n+1} = 2 \cdot 2^n \ge 2n^2 \ge (n+1)^2 $$ 이다. 첫 부등호가 가정 소비처이고, 둘째 부등호가 방금 세운 연결 부등식이다 ($n \ge 4 \ge 3$ 이므로 적용 조건이 충족된다). 곧 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 $4$ 이상의 모든 정수 $n$ 에 대해 $2^n \ge n^2$ 이다. $\blacksquare$ **복기.** 부등식 귀납에서 답안이 미완성이 되는 가장 흔한 자리는 연결 부등식을 세우지 않고 "$2n^2 \ge (n+1)^2$ 이므로"로 넘어가는 곳이다. 그 부등식은 자명하지 않고 $n \ge 3$ 에서만 성립하므로, 별도의 문단으로 증명하고 적용 조건까지 밝혀야 한다. **검산.** $n = 5$ 에서 $32 \ge 25$, $n = 6$ 에서 $64 \ge 36$ 이다. 참고로 $n = 3$ 에서는 $8 < 9$ 이므로 기저를 $4$ 로 잡은 것이 필수였다. ### 문제 9 **접근.** 점화식이 두 항을 참조하므로 되돌아보는 보폭이 $2$ 이고, 확인 5의 계산에 따라 기저도 두 개다. 귀납 단계에서는 $F_{n+2}$ 를 얻는 데 $P(n)$ 과 $P(n+1)$ 이 함께 필요하므로 가정의 폭을 구간으로 잡는다. **풀이.** $P(n)$ 을 "$F_n \le 2^{n-1}$" 이라 하자. **(기저)** $F_1 = 1$ 이고 $2^{1-1} = 2^0 = 1$ 이므로 $F_1 \le 2^0$ 이다. $F_2 = 1$ 이고 $2^{2-1} = 2$ 이므로 $F_2 \le 2^1$ 이다. 따라서 $P(1)$ 과 $P(2)$ 가 참이다. **(귀납 단계)** $n \ge 1$ 이라 하고, $1 \le i \le n+1$ 인 모든 $i$ 에 대해 $P(i)$ 를 가정하자. 특히 $F_n \le 2^{n-1}$ 과 $F_{n+1} \le 2^n$ 을 쓸 수 있다. 점화식에 의해 $$ F_{n+2} = F_{n+1} + F_n \le 2^n + 2^{n-1} = 2^{n-1}(2 + 1) = 3 \cdot 2^{n-1} $$ 이고, $3 < 4$ 이므로 $$ 3 \cdot 2^{n-1} < 4 \cdot 2^{n-1} = 2^{n+1} = 2^{(n+2)-1} $$ 이다. 따라서 $F_{n+2} \le 2^{(n+2)-1}$ 이고 $P(n+2)$ 가 참이다. 기저 두 개와 귀납 단계가 성립하므로, 강한 귀납법에 의해 모든 자연수 $n$ 에 대해 $F_n \le 2^{n-1}$ 이다. $\blacksquare$ **기저가 두 개 필요한 이유.** 귀납 단계가 만드는 것은 $P(n+2)$ 이고 그 재료가 $P(n)$ 과 $P(n+1)$ 이다. 기저를 $P(1)$ 하나만 두면 $P(2)$ 를 만들 재료가 없다 — $P(2)$ 는 $P(0)$ 과 $P(1)$ 을 요구하는데 $P(0)$ 은 무대 밖이다. 보폭이 $2$ 이므로 손으로 채워야 할 칸도 두 개다(S14주차 문제 15). **검산.** $F_5 = 5$ 이고 $2^4 = 16$ 이므로 $5 \le 16$ 이다. 부등식이 헐겁다는 것은 증명이 틀렸다는 뜻이 아니라, 이 상계가 성기다는 뜻이다. ### 문제 10 **접근.** 증명 평가는 C5주차의 평가 다섯 걸음으로 검사하고, 판정은 옳음$\cdot$틀림$\cdot$불완전 가운데 하나로 적는다. 답안에는 판정 뒤에 결함 줄 지목과 병명(S11주차의 어휘), 수리를 덧붙인다. 귀납 답안의 평가에서 먼저 세는 것은 §1.2의 걸음 다섯 개 중 몇 개가 실제로 있는가이고, 그 다음이 인용된 근거가 목록 안에 있는가이다. **풀이.** **판정 — 틀림.** 인용한 근거가 증명 대상 자신이므로 결함이 있는 줄이 특정된다 (평가 다섯 걸음의 ② 논리와 ③ 가정 사용에서 걸린다). 빠진 걸음까지 함께 보면 불완전이기도 하지만, 순환은 틀린 줄이므로 판정 낱말은 틀림으로 적는다. 이 답안은 증명이 아니다. **결함 줄.** "등차수열의 합 공식에 의해 이는 참이다"라는 줄. 그리고 그 앞에 있어야 할 쪼개기 줄과 기저 확인 줄이 통째로 없다. **병명 — 가정 미소비에 의한 순환.** 답안에 기저(걸음 ①)가 없고, 귀납 가정을 선언한 줄(걸음 ②)도 없으며, $\sum_{i=1}^{n+1} i$ 를 $\left(\sum_{i=1}^n i\right) + (n+1)$ 로 재그룹한 줄(걸음 ③)도 없다. 따라서 가정 $P(n)$ 이 한 번도 쓰이지 않았다. 그 자리를 메운 "등차수열의 합 공식"은 지금 증명하려는 명제 자신이므로, 결론을 다른 이름으로 인용한 것이다 — 근거 목록의 ④가 되려면 그 명제가 **이미** 증명되어 있어야 하는데 그렇지 않다(S14주차 문제 12). **수리.** 약한 귀납으로 고치려면 예제 2.1(또는 1권 31주차 예제 2.1)의 서식을, 최소 반례법으로 고치려면 예제 2.3의 서식을 따른다. 아래에 적는 것은 앞쪽 갈래다. 기저에서 $n = 1$ 의 좌$\cdot$우변을 각각 계산하고, 귀납 단계에서 $$ \sum_{i=1}^{n+1} i = \left(\sum_{i=1}^{n} i\right) + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2} $$ 으로 적는다. 둘째 등호가 가정 소비처이며, 이 한 줄이 있어야 답안이 순환에서 벗어난다. **복기.** 귀납 답안을 채점할 때 가장 빠른 검사는 "가정에 의해"라고 적힌 줄을 찾는 것이다. 그 줄이 없으면 나머지를 읽을 필요 없이 미완성이다. ### 문제 11 **접근.** 예제 2.3과 다섯 걸음이 같고 재료만 바뀐다. 걸음 ④에서 $\sum_{i=1}^{m-1}$ 에 더할 항은 $i = m$ 일 때의 항, 곧 $2m - 1$ 이다. 걸음 ③을 빠뜨리면 확인 7의 붕괴가 그대로 재연되므로 반드시 적는다. **풀이.** 이 등식이 성립하지 않는 자연수가 존재한다고 가정하고, 그런 자연수 전체의 집합을 $R$ 라 하자. $R$ 는 공집합이 아닌 자연수 집합이므로 최소원리에 의해 최소원소 $m$ 이 존재한다. $n = 1$ 일 때 좌변은 $2 \cdot 1 - 1 = 1$ 이고 우변은 $1^2 = 1$ 로 같으므로 $1 \notin R$ 이고, 따라서 $m \ge 2$ 이다. 곧 $m - 1$ 은 자연수다. $m$ 이 $R$ 의 최소원소이고 $m - 1 < m$ 이므로 $m - 1 \notin R$ 이다. 곧 $$ \sum_{i=1}^{m-1}(2i-1) = (m-1)^2 $$ 이다. 양변에 $i = m$ 일 때의 항 $2m-1$ 을 더하면 $$ \sum_{i=1}^{m}(2i-1) = (m-1)^2 + (2m-1) = m^2 - 2m + 1 + 2m - 1 = m^2 $$ 이므로 $m \notin R$ 이다. 이것은 $m \in R$ 와 충돌하므로 모순이다. 따라서 $R$ 는 공집합이고, 모든 자연수 $n$ 에 대해 $\sum_{i=1}^n (2i-1) = n^2$ 이다. $\blacksquare$ **복기.** 예제 2.1과 이 증명은 같은 명제의 두 서식이다. 계산으로 보면 "$(m-1)^2 + (2m-1) = m^2$" 과 "$n^2 + (2n+1) = (n+1)^2$" 은 $m = n+1$ 을 넣으면 완전히 같은 식이다 — 서식만 다르고 산수는 하나다. **검산.** $m = 3$ 으로 두면 $(3-1)^2 + (2 \cdot 3 - 1) = 4 + 5 = 9 = 3^2$ 이다. ### 문제 12 **접근.** 기저 개수는 §1.3의 삭제 실험(확인 5)이 이미 계산했다. 귀납 단계가 쓰는 항이 $P(n-2)$ 이므로 보폭이 $3$ 이고, 그 보폭만큼의 칸을 손으로 채워야 한다. 답안에서 "$n+1 \ge 11$" 이라는 적용 조건을 밝히는 줄이 채점 대상이다. **풀이.** $P(n)$ 을 "$n$ 은 3원 동전과 5원 동전으로 지불할 수 있다", 곧 "$n = 3a + 5b$ 인 음이 아닌 정수 $a, b$ 가 존재한다"라 하자. **(기저)** $8 = 3 + 5$, $9 = 3 \cdot 3$, $10 = 5 \cdot 2$ 이므로 $P(8), P(9), P(10)$ 이 모두 참이다. **(귀납 단계)** $n \ge 10$ 이라 하고, $8 \le i \le n$ 인 모든 정수 $i$ 에 대해 $P(i)$ 를 가정하자. 이때 $n + 1 \ge 11$ 이므로 $$ (n+1) - 3 = n - 2 \ge 8 $$ 이고, 또한 $n - 2 \le n$ 이므로 $n-2$ 는 가정의 사정권 안에 있다. 가정에 의해 $n - 2 = 3a' + 5b'$ 인 음이 아닌 정수 $a', b'$ 이 존재하고, 따라서 $$ n + 1 = (n-2) + 3 = 3(a'+1) + 5b' $$ 이다. $a' + 1$ 과 $b'$ 이 음이 아닌 정수이므로 $P(n+1)$ 이 참이다. 기저 세 개와 귀납 단계가 성립하므로, 강한 귀납법에 의해 $8$ 이상의 모든 정수는 3원$\cdot$5원 동전으로 지불할 수 있다. $\blacksquare$ **기저를 세 개 잡은 근거.** 귀납 단계는 $P(n+1)$ 을 만들기 위해 $P(n-2)$ 를 쓰므로, $n - 2 \ge 8$ 곧 $n + 1 \ge 11$ 인 곳에서만 작동한다. 따라서 $8, 9, 10$ 의 세 칸은 귀납이 닿지 못하고 손으로 채워야 한다. 보폭이 $3$ 이므로 기저도 셋이다. **검산.** $11 = 3 \cdot 2 + 5$, $12 = 3 \cdot 4$, $13 = 3 + 5 \cdot 2$ 로 실제로 지불된다. $7$ 은 지불되지 않으므로 $n_0 = 8$ 이 최선이라는 것도 확인된다. ### 문제 13 **접근.** 문제 6과 리듬이 같다. 전개해서 $n^3 + 5n$ 덩어리를 드러내고, 남는 항이 $6$ 의 배수임을 보인다. 남는 항 중 $3n(n+1)$ 이 관문인데, $n(n+1)$ 이 짝수라는 사실(§1.7의 목록)을 쓰면 $3 \times (\text{짝수}) = 6 \times (\text{정수})$ 가 된다. **풀이.** $P(n)$ 을 "$6 \mid (n^3 + 5n)$" 이라 하자. **(기저)** $n = 1$ 일 때 $1 + 5 = 6 = 6 \cdot 1$ 이므로 $P(1)$ 이 참이다. **(귀납 단계)** $P(n)$ 을 가정하자. 곧 $n^3 + 5n = 6m$ 인 정수 $m$ 이 존재한다. 전개하면 $$ (n+1)^3 + 5(n+1) = n^3 + 3n^2 + 3n + 1 + 5n + 5 = (n^3 + 5n) + 3n^2 + 3n + 6 $$ 이고, $3n^2 + 3n = 3n(n+1)$ 이므로 $$ (n+1)^3 + 5(n+1) = (n^3 + 5n) + 3n(n+1) + 6 $$ 이다. 여기서 $n(n+1)$ 은 연속한 두 정수의 곱이므로 짝수이고(§1.7의 목록, 1권 1주차 문제 16), $n(n+1) = 2k$ 인 정수 $k$ 가 존재한다. 그러면 $3n(n+1) = 6k$ 이다. 가정을 대입하면 $$ (n+1)^3 + 5(n+1) = 6m + 6k + 6 = 6(m + k + 1) $$ 이고 $m + k + 1$ 은 정수이므로 [근거 ②] $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 모든 자연수 $n$ 에 대해 $6 \mid (n^3 + 5n)$ 이다. $\blacksquare$ **복기.** $3n^2 + 3n$ 을 $3(n^2 + n)$ 으로만 묶고 멈추면 $3$ 의 배수까지밖에 가지 못한다. 도착점이 $6$ 의 배수이므로 $2$ 를 하나 더 확보해야 하고, 그 $2$ 를 공급하는 것이 연속한 두 정수의 곱이다. **도착점의 꼴이 어디까지 묶으라고 지시한다.** **검산.** $n = 2$ 에서 $8 + 10 = 18 = 6 \cdot 3$, $n = 3$ 에서 $27 + 15 = 42 = 6 \cdot 7$ 이다. ### 문제 14 **접근.** 사다리를 걸 변수가 없는 부재 명제이므로 §1.6의 셋째 물음에 걸린다. 최소로 잡을 양은 $x$ 다. $3 \mid x^2$ 에서 $3 \mid x$ 로 가는 줄에 유클리드 보조정리가 필요하며, 그 정리의 가정("$p$ 는 소수")이 $p = 3$ 에서 충족됨을 밝혀야 한다. **풀이.** $x^2 = 3y^2$ 인 양의 정수 $x, y$ 가 존재한다고 가정하자. 그런 해들의 첫 성분 $x$ 가 이루는 집합은 공집합이 아닌 양의 정수 집합이므로, 최소원리에 의해 최소원소가 존재한다. $x$ 가 최소인 해를 $(x, y)$ 라 하자. $x^2 = 3y^2$ 이므로 $3 \mid x^2$, 곧 $3 \mid x \cdot x$ 이다. $3$ 은 소수이므로 유클리드 보조정리에 의해 $3 \mid x$ 이고, $x = 3x'$ 인 양의 정수 $x'$ 이 존재한다. 대입하면 $$ 9x'^2 = 3y^2, \qquad \text{곧} \qquad y^2 = 3x'^2 $$ 이다. 같은 논증을 $y$ 에 적용하면 $3 \mid y^2$ 이므로 $3 \mid y$ 이고, $y = 3y'$ 인 양의 정수 $y'$ 이 존재한다. 이것을 $y^2 = 3x'^2$ 에 대입하면 $$ 9y'^2 = 3x'^2, \qquad \text{곧} \qquad x'^2 = 3y'^2 $$ 이다. 따라서 $(x', y')$ 도 같은 방정식의 양의 정수 해이고, $x' = \frac x3 < x$ 이다. 이것은 $x$ 가 최소라는 사실과 충돌하므로 모순이다. 그러므로 $x^2 = 3y^2$ 인 양의 정수 $x, y$ 는 존재하지 않는다. $\blacksquare$ **복기.** 무한강하의 형태를 그대로 따랐다 — 최소인 것을 잡고, 그것에서 같은 조건을 만족하는 더 작은 것을 **실제로 구성**했다. 여기서 $m - 1$ 은 한 번도 등장하지 않는다. C7주차 문제 17의 $\sqrt2$ 판과 유일하게 다른 곳은 인용하는 소수가 $2$ 대신 $3$ 이라는 것뿐이고, 그 때문에 "짝수" 대신 유클리드 보조정리를 명시적으로 인용해야 한다. **따름.** 이 명제는 $\sqrt3$ 이 무리수라는 것과 같은 말이다. $\sqrt3 = \frac xy$ 이면 양변을 제곱해 $x^2 = 3y^2$ 이 되기 때문이다(1권 21주차 문제 7). ### 문제 15 **접근.** 예제 2.2와 무대는 같지만 결론이 더 약하다 — 분해 전체가 아니라 소인수 **하나**만 있으면 된다. 그래서 합성수 $n+1 = ab$ 에서 $a$ 한쪽에만 가정을 쓰면 되고, 마지막에 "$a$ 의 소인수는 $n+1$ 의 소인수이기도 하다"를 나누어떨어짐의 추이성으로 잇는다. **풀이.** $P(n)$ 을 "$n$ 은 소수인 약수를 가진다"라 하자. **(기저)** $n = 2$ 는 소수이고 $2 \mid 2$ 이므로 $2$ 자신이 $2$ 의 소수인 약수다. 따라서 $P(2)$ 가 참이다. **(귀납 단계)** $n \ge 2$ 라 하고, $2 \le i \le n$ 인 모든 정수 $i$ 에 대해 $P(i)$ 를 가정하자. $n+1$ 을 두 경우로 나눈다. **경우 1: $n+1$ 이 소수.** 그러면 $n+1$ 자신이 $n+1$ 의 소수인 약수이므로 $P(n+1)$ 이 참이다. **경우 2: $n+1$ 이 합성수.** 합성수의 정의에 의해 $n+1 = ab$ 이면서 $1 < a < n+1$, $1 < b < n+1$ 인 정수 $a, b$ 가 존재한다. $a$ 는 정수이므로 $2 \le a \le n$ 이고, 따라서 $a$ 는 가정의 사정권 안에 있다. 가정에 의해 $a$ 는 소수인 약수 $p$ 를 가진다. 그러면 $p \mid a$ 이고 $a \mid (n+1)$ 이므로, 나누어떨어짐의 추이성(1권 2주차)에 의해 $p \mid (n+1)$ 이다. 곧 $p$ 는 $n+1$ 의 소수인 약수이고 $P(n+1)$ 이 참이다. 두 경우가 $n+1$ 의 모든 가능성을 덮으므로 귀납 단계가 성립한다. 기저 단계와 귀납 단계가 모두 성립하므로, 강한 귀납법에 의해 $2$ 이상의 모든 정수는 소수인 약수를 가진다. $\blacksquare$ **복기.** 이 명제는 S11주차 문제 15(소수가 무한히 많다)가 부품으로 쓰는 사실이다 — "$N = p_1 \cdots p_k + 1$ 도 소인수를 가진다"는 줄이 정확히 이 명제의 인용이다. 1권 33주차 문제 6은 같은 것을 소인수분해 존재의 따름정리로 유도한다. 예제 2.2에서 곧바로 따라 나오지만, 여기서 독립적으로 증명해 두면 예제 2.2보다 약한 도구만으로도 소수의 무한성이 서는 것이 보인다. **검산.** $n + 1 = 91 = 7 \cdot 13$ 에서 $a = 7$ 을 잡으면 $7$ 이 소수이므로 $p = 7$ 이고, 실제로 $7 \mid 91$ 이다. ### 문제 16 **접근.** 기하 명제이지만 귀납이 붙을 자리는 개수뿐이다. $P(n+1)$ 을 쪼개는 방법은 "$n+1$ 번째 점을 하나 추가한다"이고, 그때 늘어나는 선분이 몇 개인지 세면 된다. 필요한 이전 항은 $P(n)$ 하나이므로 약한 귀납이다. **풀이.** $P(n)$ 을 "어느 세 점도 한 직선 위에 있지 않은 $n$ 개의 점을 서로 잇는 선분의 개수는 $\binom n2$ 이다"라 하자 ($n \ge 2$). **(기저)** $n = 2$ 일 때 두 점을 잇는 선분은 하나뿐이고 $\binom 22 = 1$ 이므로 $P(2)$ 가 참이다. **(귀납 단계)** $n \ge 2$ 라 하고 $P(n)$ 을 가정하자. 조건을 만족하는 $n+1$ 개의 점이 주어졌다고 하자. 그중 하나를 $Q$ 라 하고 나머지 $n$ 개를 보면, 그 $n$ 개도 어느 세 점이 한 직선 위에 있지 않으므로 가정에 의해 그들 사이의 선분은 $\binom n2$ 개다. 새로 세어야 할 것은 $Q$ 를 끝점으로 하는 선분이다. $Q$ 는 나머지 $n$ 개의 점 각각과 선분을 하나씩 이루고, 서로 다른 점끼리는 서로 다른 선분을 주므로 그 개수는 $n$ 이다. 모든 선분은 $Q$ 를 끝점으로 갖거나 갖지 않으므로 두 묶음은 겹치지 않고 전체를 덮는다. 따라서 선분의 총 개수는 $$ \binom n2 + n = \frac{n(n-1)}{2} + n = \frac{n(n-1) + 2n}{2} = \frac{n(n+1)}{2} = \binom{n+1}{2} $$ 이다. 여기서 이항계수의 값 $\binom n2 = \frac{n(n-1)}2$ 을 썼다(§1.7의 목록). 곧 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 조건을 만족하는 $n$ 개의 점에 대해 선분의 개수는 $\binom n2$ 이다. $\blacksquare$ **복기.** "어느 세 점도 한 직선 위에 없다"는 조건은 **선분**의 개수에는 실제로 필요하지 않다. 선분은 두 끝점으로 결정되므로 서로 다른 점쌍은 언제나 서로 다른 선분을 준다 — 세 점 $A, B, C$ 가 한 직선 위에 있어도 $AB$, $BC$, $AC$ 는 끝점이 다른 세 개의 선분이다. 위 증명에서 조건이 나온 자리는 나머지 $n$ 개의 점에도 가정을 적용하려고 조건이 부분집합에 유전됨을 확인한 한 곳뿐이고, 그 자리도 명제에 조건을 붙여 두었기 때문에 생긴 것이다. 조건이 힘을 갖는 것은 같은 세팅에서 결정되는 **직선**의 개수를 셀 때다 — 세 점이 한 직선 위에 있으면 세 점쌍이 같은 직선 하나를 주어 개수가 $\binom n2$ 보다 작아진다. 조건이 어디서 소비되는지, 또는 소비되지 않는지를 짚는 것이 이 문항의 학습 목표다. C16주차에서 이 개수를 귀납 없이 세는 방법을 다룬다. **검산.** $n = 4$ 에서 $\binom 42 = 6$ 이고, 사각형의 변 넷과 대각선 둘을 합해 실제로 여섯이다. ### 문제 17 **접근.** 쪼개기는 "가정의 양변에 $1+x$ 를 곱한다"이다. 부등식의 양변에 곱할 때는 곱하는 수의 부호를 먼저 밝혀야 부등호 방향이 보존되므로, 조건 $x > -1$ 이 소비되는 자리가 정확히 거기다. 곱한 뒤 남는 $nx^2$ 을 버리는 것이 마지막 걸음이다. **풀이.** $x > -1$ 인 실수 $x$ 를 하나 고정하고, $P(n)$ 을 "$(1+x)^n \ge 1 + nx$" 라 하자. **(기저)** $n = 1$ 일 때 좌변은 $(1+x)^1 = 1 + x$ 이고 우변은 $1 + 1 \cdot x = 1 + x$ 이므로 두 값이 같고 $P(1)$ 이 참이다. **(귀납 단계)** $P(n)$ 을 가정하자. 가정에 의해 $(1+x)^n \ge 1 + nx$ 이다. 여기서 $x > -1$ 이므로 $1 + x > 0$ 이다 — 이 줄이 조건 $x > -1$ 의 소비처다. 양수를 곱하면 부등호 방향이 보존되므로, 가정의 양변에 $1+x$ 를 곱해 $$ (1+x)^{n+1} = (1+x)^n (1+x) \ge (1 + nx)(1 + x) $$ 를 얻는다. 우변을 전개하면 $$ (1+nx)(1+x) = 1 + x + nx + nx^2 = 1 + (n+1)x + nx^2 $$ 이고, $n > 0$ 이고 $x^2 \ge 0$ 이므로 $nx^2 \ge 0$ 이다. 따라서 $$ (1+x)^{n+1} \ge 1 + (n+1)x + nx^2 \ge 1 + (n+1)x $$ 이고 $P(n+1)$ 이 참이다. 기저 단계와 귀납 단계가 모두 성립하므로, 귀납의 원리에 의해 $x > -1$ 인 모든 실수 $x$ 와 모든 자연수 $n$ 에 대해 $(1+x)^n \ge 1 + nx$ 이다. $\blacksquare$ **조건의 소비처.** 귀납 단계에서 "$1 + x > 0$ 이므로 부등호 방향이 보존된다"라고 적은 줄이다. 이 조건이 없으면, 예컨대 $x = -3$ 에서 $1 + x = -2 < 0$ 이라 곱하는 순간 부등호가 뒤집혀 논증이 무너진다. **검산.** $x = 0.5$, $n = 3$ 에서 좌변은 $1.5^3 = 3.375$ 이고 우변은 $1 + 1.5 = 2.5$ 이다. $x = -0.5$, $n = 3$ 에서는 좌변이 $0.125$, 우변이 $-0.5$ 로 역시 성립한다. ### 문제 18 **접근.** 결론이 명백히 거짓이므로($n = 100$ 이 반례다) 답안 어딘가가 반드시 틀렸다. 기저는 옳으니 남은 곳은 귀납 단계뿐이다. 귀납 단계는 "**모든** $n$ 에 대한" 조건문임을 떠올리고, 그 조건문이 거짓이 되는 $n$ 을 하나 찾으면 진단이 끝난다. **풀이.** **판정 — 틀림.** 명제 자체가 거짓이므로 C5주차 평가 다섯 걸음의 ① 명제 진위에서 이미 걸린다 ($n = 100$ 에서 $100 < 100$ 이 거짓). 거짓 명제에 붙은 증명은 반드시 틀렸으므로 판정 낱말은 틀림이다. **결함 줄.** "$n < 100$ 이므로 $n + 1 \le 100$ 이고, 따라서 성립한다"는 줄. **결함의 내용.** 두 가지가 겹쳐 있다. 첫째, **도착점이 틀렸다.** 보여야 할 것은 $P(n+1)$, 곧 $n + 1 < 100$ 인데 답안이 도착한 곳은 $n + 1 \le 100$ 이다. 등호가 붙은 부등식은 도착점이 아니다. 둘째, **귀납 단계가 특정 $n$ 에서 실제로 거짓이다.** $n = 99$ 를 넣어 보면 전건 "$1, \ldots, 99$ 가 모두 $100$ 보다 작다"는 참이고 후건 "$100 < 100$"은 거짓이므로, 이 $n$ 에서 조건문이 거짓이다. 정의 8.1의 걸음 ②는 $n_0$ 이상의 **모든** $n$ 에 대해 성립할 것을 요구하므로, 한 곳에서 끊기면 사다리가 거기서 멈춘다. **무엇이 무너졌는가.** 강한 귀납이라는 이름을 붙였다고 해서 귀납 단계의 요구가 약해지지는 않는다. 가정의 폭을 넓히는 것과 귀납 단계가 모든 $n$ 에서 성립해야 한다는 것은 별개의 조건이다. 이 답안은 앞쪽을 지키고 뒤쪽을 어겼다. **복기.** 귀납 답안의 결함은 두 자리에만 있다 — 기저가 없거나(확인 2), 귀납 단계가 어떤 $n$ 에서 끊기거나. 결론이 거짓인 답안을 만나면 이 두 곳을 순서대로 검사한다. S14주차 문제 17$\cdot$18이 같은 검사를 다른 소재에서 다룬다. ### 문제 19 **접근.** 두 풀이의 계산은 하나다. $(n+1)! = (n+1) \cdot n!$ 이라는 쪼개기가 (a)의 관절이고, $m! = m \cdot (m-1)!$ 이 (b)의 관절이다. 가정을 대입한 뒤 계수 $(n+1)$ 또는 $m$ 을 $2$ 로 눌러 놓는 줄이 양쪽 모두에 필요하다. 논의에서는 §1.6의 첫째 물음이 어느 쪽을 가리키는지를 근거로 삼는다. **풀이 (a) — 약한 귀납.** $P(n)$ 을 "$n! \ge 2^{n-1}$" 이라 하자. **(기저)** $n = 1$ 일 때 $1! = 1$ 이고 $2^{0} = 1$ 이므로 $P(1)$ 이 참이다. **(귀납 단계)** $P(n)$ 을 가정하자. $n$ 이 자연수이므로 $n + 1 \ge 2$ 이고, $n! > 0$ 이므로 $$ (n+1)! = (n+1) \cdot n! \ge (n+1) \cdot 2^{n-1} \ge 2 \cdot 2^{n-1} = 2^{n} $$ 이다. 첫 부등호가 가정 소비처이고, 둘째 부등호에서 $n+1 \ge 2$ 를 썼다. $2^n = 2^{(n+1)-1}$ 이므로 $P(n+1)$ 이 참이다. 따라서 귀납의 원리에 의해 모든 자연수 $n$ 에서 $n! \ge 2^{n-1}$ 이다. $\blacksquare$ **풀이 (b) — 최소 반례법.** 이 부등식이 성립하지 않는 자연수가 존재한다고 가정하고, 그런 자연수 전체의 집합을 $R$ 라 하자. 최소원리에 의해 $R$ 에 최소원소 $m$ 이 존재한다. $n = 1$ 에서 $1! = 1 \ge 2^0 = 1$ 이므로 $1 \notin R$ 이고, 따라서 $m \ge 2$ 이며 $m - 1$ 은 자연수다. 최소성에 의해 $m - 1 \notin R$ 이므로 $(m-1)! \ge 2^{m-2}$ 이다. 그러면 $m \ge 2$ 이고 $(m-1)! > 0$ 이므로 $$ m! = m \cdot (m-1)! \ge m \cdot 2^{m-2} \ge 2 \cdot 2^{m-2} = 2^{m-1} $$ 이다. 곧 $m \notin R$ 이고, 이것은 $m \in R$ 와 충돌하므로 모순이다. 따라서 $R = \varnothing$ 이고 모든 자연수 $n$ 에서 $n! \ge 2^{n-1}$ 이다. $\blacksquare$ **논의 — 어느 쪽이 자연스러운가.** 약한 귀납이 자연스럽다. §1.6의 첫째 물음에서 $P(n+1)$ 을 쪼갠 결과 $(n+1)! = (n+1) \cdot n!$ 이 요구하는 이전 항은 $P(n)$ 하나이고 그것이 직전이므로, 셋째 물음까지 갈 이유가 없다. 최소 반례법 쪽은 같은 계산을 하기 위해 귀류 개시와 최소원리 인용이라는 두 줄을 더 쓴다 — 얻는 것 없이 답안만 길어진다. 최소 반례법이 값을 하는 자리는 문제 14처럼 사다리를 걸 변수가 없는 무대다. **검산.** $n = 5$ 에서 $5! = 120$ 이고 $2^4 = 16$ 이다. 등호는 $n = 1$ 과 $n = 2$ 두 곳에서 성립하고($1! = 1 = 2^0$, $2! = 2 = 2^1$), $n \ge 3$ 부터는 진부등식이다 ($3! = 6 > 4 = 2^2$). 귀납 단계의 둘째 부등호 $(n+1) \cdot 2^{n-1} \ge 2 \cdot 2^{n-1}$ 이 등호가 되는 것은 $n + 1 = 2$, 곧 $n = 1$ 일 때뿐이므로 등호가 두 곳에서만 나오는 것이 계산으로도 확인된다. ### 문제 20 **접근.** 서술 문항의 답안은 개념 절의 문장을 옮겨 적는 것이 아니라, 지정된 예제의 어느 줄이 그 개념의 근거인지 짚는 글이다. (a)는 예제 2.1과 2.3에서 각각 두 줄씩, (b)는 예제 2.2에서 한 줄을 지목해야 점수가 된다. **풀이. (예시 답안)** **(a)** 예제 2.1의 "$n$ 을 자연수라 하고 $P(n)$ 을 가정하자"는 줄이 조건문의 출발점을 무대에 올리는 줄이고, "$= n^2 + (2n+1)$" 이라 적은 줄이 그 출발점을 소비해 도착점 $P(n+1)$ 로 가는 줄이다 — 귀납 단계 전체가 조건문 $P(n) \Rightarrow P(n+1)$ 하나를 증명하는 일임이 이 두 줄로 확인된다(S14주차). 예제 2.3에서는 "$1 \notin R$ 이므로 $m \ge 2$" 라는 줄이 예제 2.1의 기저와 같은 계산을 하고, "$\sum_{i=1}^{m-1} i$ 에 $m$ 을 더해 $\frac{m(m+1)}2$ 을 얻은" 줄이 예제 2.1의 귀납 단계와 같은 계산을 한다. 두 서식은 같은 명제군을 증명하며, 같은 한 칸을 위로 타는가 아래에서 최소성을 깨뜨리는 데 쓰는가만 다르다. **(b)** 예제 2.2에서 합성수 $n+1 = ab$ 의 두 인수는 $2$ 이상 $n$ 이하의 어디든 될 수 있으므로, 증명이 실제로 쓰는 것은 $P(a)$ 와 $P(b)$ 이고 그중 어느 것도 $P(n)$ 이라는 보장이 없다. 약한 귀납의 가정에는 $P(n)$ 하나만 들어 있어 이 둘을 덮지 못하므로, "$a$ 는 정수이므로 $2 \le a \le n$ 이다"라는 줄이 뜻을 가지려면 가정이 $P(2)$ 부터 $P(n)$ 까지의 구간이어야 한다. **복기.** 두 물음 모두 "어느 줄인가"를 묻는 문항이다. 개념 절의 요약만 적은 답안은 내용이 옳아도 점수가 되지 않는다 — 지목이 없으면 그 개념을 자신의 증명에서 찾아낼 수 있는지가 확인되지 않기 때문이다. --- **다음 주 예고 (C9주차):** Chartrand 7장 — 증명 기법 리뷰와 **채점자 되기**, 그리고 전반부 종합 시험이다. C1~C8주차에서 세운 기법들이 "명제의 겉모양이 기법을 정한다"는 하나의 지도로 접히고, 무작위로 배치된 명제 앞에서 어느 기법을 꺼낼지를 시험한다. 이번 주의 확인 3$\cdot$문제 10$\cdot$문제 18에서 한 진단 — 걸음이 비었는가, 가정이 소비되었는가, 귀납 단계가 모든 $n$ 에서 성립하는가 — 이 다음 주의 채점 훈련에서 그대로 항목이 된다. C1~C8주차의 백지 체크리스트를 총복습하고 원서 7장을 먼저 통독한 뒤에 온다.