# S14주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 귀납 답안을 함께 만들기 완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 설계부터 스스로 한 뒤 표 없이 산문으로 적는다. 지지대가 예제마다 하나씩 빠진다. ### 예제 2.1 — 합 공식: 소비처를 만들어 쓰기 **명제.** 모든 자연수 $n$에 대해 $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$이다. **판정.** 도착점의 합 $\sum_{k=1}^{n+1}$은 출발점의 합 $\sum_{k=1}^{n}$에 항 하나를 더한 것이므로 의존이 직전 한 칸이다 — §1.6 표의 첫째 줄, 곧 약한 귀납이다. (이 명제는 1권 31주차 예제 2.1에서 이미 증명했다. 여기서 다시 꺼내는 이유는 결론이 아니라 절차를 보기 위해서다 — 네 걸음과 소비 점검이 어디에 붙는지가 이번의 관찰 대상이다.) **설계 — 쓰기 전에 정하는 세 가지.** 귀납 답안에서 먼저 정할 것은 세 가지다. 무엇을 $P(n)$이라 부를지, 기저에서 무엇을 계산할지, 귀납 단계의 출발점과 도착점이 각각 어떤 식인지. | | **말** | **수식 번역** | |---|---|---| | 명제에 이름 붙이기 | $n$번째 주장 | $P(n)$: $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ | | 기저 | $P(1)$을 확인한다 | 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2}$ | | 귀납 단계의 가정 — 출발점 | $P(n)$ | $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ | | 귀납 단계의 목표 — 도착점 | $P(n+1)$ | $\underline{\quad(?)\quad}$ | :::{container} quotebox **확인 10.** 도착점 칸을 채워 보자. $P(n+1)$은 어떻게 만드는가. ::: :::{admonition} 답 :class: quotebox dropdown $P(n)$의 식에서 $n$이 있는 자리마다 $n+1$을 넣는다: $\sum_{k=1}^{n+1} k = \frac{(n+1)\big((n+1)+1\big)}{2} = \frac{(n+1)(n+2)}{2}$. 오른쪽 끝의 정리는 표기를 줄인 것이지 새 식을 만든 것이 아니다. $P(n+1)$을 손으로 적어 두는 일은 형식이 아니라 후진의 출발점을 확보하는 일이다 — 도착점의 모양을 모르면 어디로 변형할지 정할 수 없다(S2주차의 핵심 질문). ::: **1단계 — 이름을 붙이고 기저를 확인한다.** 답안의 첫 두 문장은 창작이 아니라 서식이다. :::{container} quotebox **확인 11.** 첫 두 문장을 완성해 보자. "$n$에 대한 귀납법으로 증명한다. $P(n)$을 '$\underline{\qquad}$'이라 하자. (기저) $n = 1$: 좌변 $= \underline{\quad}$, 우변 $= \underline{\quad}$이므로 $P(1)$이 참이다." ::: :::{admonition} 답 :class: quotebox dropdown $P(n)$은 "$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$"이고, 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$이다. 기저에서 좌변과 우변을 **각각 계산해 적는** 것이 규격이다. "$n=1$에서 자명하다"로 줄이면 걸음 ②가 실제로 수행되었는지 확인할 수 없다. ::: **2단계 — 귀납 단계를 개시한다.** §1.3에서 본 대로 이 단계는 조건문 하나의 증명이고, 개시 문장은 S1주차의 조건문 개시 문장과 같은 모양이다. :::{container} quotebox **확인 12.** 개시 문장과 목표 명시 문장을 완성해 보자. "(귀납 단계) 자연수 $n$을 $\underline{\qquad}$, $P(n)$이 참이라 하자. 곧 $\sum_{k=1}^{n} k = \underline{\qquad}$이다. 보일 것은 $\underline{\qquad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown "자연수 $n$을 **하나 임의로 고정하고**, $P(n)$이 참이라 하자. 곧 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$이다. 보일 것은 $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$이다." "임의로 고정"은 고정한 그 하나가 특정 값이 아니라는 뜻이고, 그것이 이 한 $n$에서 세운 조건문의 결론을 모든 $n$으로 덮게 해 준다(걸음 ③-가). "$n = 3$에서 $P(n)$을 가정하자"처럼 값을 지정하면 전달이 그 자리에서만 보장되고 사슬이 끊긴다. 가정을 식으로 한 번 풀어 적어 두면 소비할 등식이 눈앞에 놓인다. ::: **3단계 — 도착점을 쪼갠다.** 후진 한 걸음이다. 핵심 질문은 "$\sum_{k=1}^{n+1} k$가 $\frac{(n+1)(n+2)}{2}$와 같음을 보이려면 무엇을 하면 되는가"이고, 답은 언제나 같은 모양이다 — 손에 쥔 것($P(n)$의 식)이 보이도록 왼쪽을 쪼갠다. :::{container} quotebox **확인 13.** 쪼개기 줄을 완성해 보자. "$\displaystyle\sum_{k=1}^{n+1} k = \left(\underline{\qquad}\right) + \underline{\qquad}$" ::: :::{admonition} 답 :class: quotebox dropdown $\displaystyle\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1)$. 합의 마지막 항 하나를 떼어 낸 것뿐이다(§1.5의 첫째 줄, 근거 ③). 이 줄이 끝난 순간 소비 점검 ㄱ이 통과된다 — $P(n)$의 좌변이 그대로 등장했다. ::: **4단계 — 가정을 소비한다.** 방금 만든 자리에 가정의 등식을 대입한다. 이 줄이 답안 전체에서 유일하게 귀납다운 줄이므로, 표시를 남겨 두는 것이 규격이다. :::{container} quotebox **확인 14.** 소비 줄을 완성해 보자. "$= \underline{\qquad} + (n+1)$ [귀납 가정 소비]" ::: :::{admonition} 답 :class: quotebox dropdown $= \frac{n(n+1)}{2} + (n+1)$. 대입한 것은 가정의 등식 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$이다(근거 ③). 소비 점검 ㄴ이 여기서 통과된다. 답안에 "[귀납 가정]"이라고 적어 두면 읽는 쪽이 이 줄을 찾느라 답안 전체를 훑지 않아도 된다. ::: **5단계 — 도착점까지 전진한다.** 남은 것은 계산이고, 목표는 도착점의 식과 **글자 그대로** 일치시키는 것이다. :::{container} quotebox **확인 15.** 계산을 완주해 보자. $\frac{n(n+1)}{2} + (n+1)$을 정리하면 무엇이 되는가. ::: :::{admonition} 답 :class: quotebox dropdown $\frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$. 통분한 뒤 공통인수 $(n+1)$로 묶었다(근거 ③). 결과가 확인 10에서 적어 둔 도착점과 일치하므로 $P(n+1)$이 참이다. 계산만 끝내고 멈추면 걸음 ③-다가 빠진다 — 도착 선언을 한 줄로 적는다. ::: **6단계 — 결론을 선언한다.** 지금까지 확보한 것은 $P(1)$과 조건문 하나뿐이다. 마지막 한 줄이 그 둘을 원명제로 바꾼다. :::{container} quotebox **확인 16.** 마지막 문장을 완성해 보자. 이 문장이 인용하는 근거는 몇 번인가. ::: :::{admonition} 답 :class: quotebox dropdown "기저와 귀납 단계에 의해, 모든 자연수 $n$에 대해 $P(n)$이 참이다. $\blacksquare$" 인용하는 근거는 ④ — 정의 14.1이 주는 귀납 공리다. §1.1에서 본 대로 이 한 줄이 없으면 답안이 확보한 것은 유한 개의 명제와 조건문 하나에 머문다. ::: **완성본.** 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $n$에 대한 귀납법으로 증명한다. $P(n)$을 "$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$"이라 하자. | 귀납 변수와 명제를 지정한다(걸음 ①). 이 선언이 있어야 $P(n+1)$이 어떤 문장인지 확정된다. | | **(기저)** $n = 1$: 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$이므로 $P(1)$이 참이다. | 목록의 시작점을 확보한다(걸음 ②). 좌변$\cdot$우변을 각각 계산해 적는다. | | **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 곧 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$이다. | 조건문 개시(걸음 ③-가). 고정한 $n$이 특정 값이 아니므로 이 조건문이 사슬 전체를 덮고, 가정을 식으로 풀어 두면 소비할 등식이 눈앞에 놓인다. | | 보일 것은 $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$이다. | 도착점 명시. 후진의 출발점이다(S2주차). | | $\displaystyle\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1)$ | 쪼개기 — 마지막 항을 떼어 $P(n)$의 좌변을 드러낸다(근거 ③). 소비 점검 ㄱ 통과. | | $= \frac{n(n+1)}{2} + (n+1)$ | **가정 소비처** — 가정의 등식을 대입한다(걸음 ③-나). 소비 점검 ㄴ 통과. | | $= \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$ | 통분하고 $(n+1)$로 묶는다(근거 ③). 결과가 도착점과 일치한다. | | 따라서 $P(n+1)$이 참이다. | 도착 선언(걸음 ③-다). 도착점과 글자 그대로 일치했음을 명시한다. | | 기저와 귀납 단계에 의해, 모든 자연수 $n$에 대해 $P(n)$이 참이다. $\blacksquare$ | 결론 선언(걸음 ④) — 귀납 공리 인용, 근거 ④. | **이 답안에서 귀납다운 줄은 몇 줄인가.** 아홉 줄 가운데 여섯째 줄 하나다. 나머지는 서식 선언 셋, 계산 셋, 도착$\cdot$결론 선언 둘이다. 귀납 단계에서 막혔을 때 가장 먼저 검사할 것이 그 한 줄인 이유가 여기 있다 — 그 줄이 없으면 답안에서 귀납은 사라지고 서식만 남는다. ### 예제 2.2 — 나누어떨어짐: 차를 만들어 연결하기 **명제.** 모든 자연수 $n$에 대해 $3 \mid (n^3 - n)$이다. **판정.** $(n+1)^3 - (n+1)$을 전개하면 $n^3 - n$ 덩어리가 그대로 나온다(확인 2의 셋째 줄에서 이미 계산했다). 의존이 직전 한 칸이므로 약한 귀납이다. 이번에는 설계만 함께 하고 본문은 완성본으로 본다. :::{container} quotebox **확인 17.** 번역표를 채워 보자. $P(n)$: $3 \mid (n^3 - n)$, 곧 $n^3 - n = \underline{\quad}$인 정수 $m$이 존재한다. 기저: $n = 1$일 때 $n^3 - n = \underline{\quad}$. 도착점: $3 \mid \underline{\qquad}$. ::: :::{admonition} 답 :class: quotebox dropdown $n^3 - n = 3m$인 정수 $m$이 존재한다 / $1 - 1 = 0$ / $3 \mid \big((n+1)^3 - (n+1)\big)$. 가정 쪽의 "나누어떨어진다"는 존재 주장이므로 그런 $m$을 **받아서** 쓰고, 도착점 쪽의 "나누어떨어진다"는 $3 \times (\text{정수})$ 꼴을 실제로 **만들어 제시해야** 한다(1권 2주차의 정의). 기저의 $0$은 $0 = 3 \cdot 0$이므로 3의 배수다. ::: :::{container} quotebox **확인 18.** 쪼개기 줄을 만들어 보자. $(n+1)^3 - (n+1)$을 전개해 $n^3 - n$이 보이도록 재그룹하면 무엇이 남는가. ::: :::{admonition} 답 :class: quotebox dropdown $(n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3n^2 + 3n$. 남는 것은 $3n^2 + 3n$이고, 이것이 3의 배수라는 점이 곧 이 명제가 통하는 이유다. 합의 쪼개기와 달리 여기서는 전개를 한 번 거쳐야 덩어리가 보인다 — 나누어떨어짐 귀납의 표준 동작이다(§1.5의 넷째 줄). ::: | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $n$에 대한 귀납법으로 증명한다. $P(n)$을 "$3 \mid (n^3 - n)$"이라 하자. | 걸음 ① — 명제 지정. | | **(기저)** $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$이므로 $3 \mid 0$이고 $P(1)$이 참이다. | 걸음 ②. 0이 3의 배수임을 정의의 꼴로 적는다. | | **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 정의에 의해 $n^3 - n = 3m$인 정수 $m$이 존재한다. | 걸음 ③-가. 가정의 존재 주장에서 정수 $m$을 받아 온다(근거 ①). | | 보일 것은 $3 \mid \big((n+1)^3 - (n+1)\big)$이다. | 도착점 명시. 만들 꼴은 $3 \times (\text{정수})$다. | | $(n+1)^3 - (n+1) = n^3 + 3n^2 + 3n + 1 - n - 1 = (n^3 - n) + 3n^2 + 3n$ | 쪼개기 — 전개 후 재그룹해 $P(n)$의 식을 드러낸다(근거 ③). 소비 점검 ㄱ 통과. | | $= 3m + 3(n^2 + n) = 3(m + n^2 + n)$ | **가정 소비처** — $n^3 - n = 3m$을 대입하고 3으로 묶는다. 소비 점검 ㄴ 통과. | | $m + n^2 + n$은 정수이므로 $3 \mid \big((n+1)^3 - (n+1)\big)$이고, 따라서 $P(n+1)$이 참이다. | 괄호 안이 정수인지 확인한 뒤(근거 ②) 정의의 꼴이 완성되었음을 선언한다(걸음 ③-다). | | 기저와 귀납 단계에 의해, 모든 자연수 $n$에 대해 $P(n)$이 참이다. $\blacksquare$ | 걸음 ④ — 귀납 공리 인용. | 이 명제는 $n^3 - n = (n-1)n(n+1)$이 연속한 세 정수의 곱이라는 점에서 귀납 없이도 증명된다. 한 칸 강한 명제 $6 \mid (n^3 - n)$에 대해서는 1권 32주차 문제 19가 귀납 경로(1권 32주차 예제 2.2)와 비귀납 경로(1권 30주차 문제 17)를 나란히 놓고 두 경로가 쓰는 부품 목록을 비교한다. 여기서 굳이 귀납으로 적은 것은 결론을 얻기 위해서가 아니라, 나누어떨어짐에서 쪼개기가 어떤 모양이 되는지를 보기 위해서다. ### 예제 2.3 — 진단 2건: 가정 미소비와 기저 붕괴 이번에는 설계부터 스스로 한다. 아래 두 답안은 계산에 오류가 없다. 그런데도 둘 다 이번 주의 규격을 통과하지 못한다. **답안 1.** "명제: 모든 자연수 $n$에 대해 $n < 2^n$이다. 증명: (기저) $1 < 2$이므로 참이다. (귀납 단계) $P(n)$을 가정하자. $n + 1 < 2^{n+1}$을 보이자. $2^{n+1} = 2 \cdot 2^n \ge 2 \cdot 1 = 2 > n + 1$이므로 … 아니, $n$이 크면 $n+1 > 2$라 어긋난다." **답안 2.** "명제: 모든 자연수 $n$에 대해 $n^2 + n$은 홀수이다. 증명: (귀납 단계) $P(n)$을 가정하자. $(n+1)^2 + (n+1) = n^2 + n + 2n + 2 = (n^2 + n) + 2(n+1)$이고, 가정에 의해 $n^2 + n$은 홀수이므로 홀수에 짝수를 더한 것이 되어 홀수이다. 따라서 $P(n+1)$이 참이고, 모든 $n$에서 성립한다." :::{container} quotebox **확인 19.** 두 답안에 소비 점검 ㄱ$\cdot$ㄴ과 걸음 ②의 검사를 각각 걸어 보자. 어느 검사에 걸리는가. ::: :::{admonition} 답 :class: quotebox dropdown 답안 1: 소비 점검 ㄱ에 걸린다. $P(n)$의 식은 "$n < 2^n$"인데 답안이 실제로 쓴 것은 "$2^n \ge 1$"이라는 다른 부등식이다. 걸음 ②는 통과한다. 답안 2: 소비 점검은 ㄱ$\cdot$ㄴ 모두 통과한다 — "$n^2+n$은 홀수"가 등장하고 실제로 쓰였다. 걸리는 것은 걸음 ②다. 기저가 아예 없고, 확인해 보면 $P(1)$, 곧 "$1^2 + 1 = 2$가 홀수"는 거짓이다. ::: **답안 1의 진단 — 가정 미소비.** 병명은 §1.4 삭제 실험 2와 같다. 답안은 $P(n)$을 선언해 놓고 소비처를 만들지 않았고, 대신 $2^n \ge 1$이라는 훨씬 약한 사실로 밀어 보다 막혔다. $2 \cdot 1 = 2$는 $n$이 커지면 $n+1$보다 작아지므로 이 길은 실제로 막힌 길이다. 수리는 소비처를 만드는 것 하나다. 쪼개기 $2^{n+1} = 2 \cdot 2^n$까지는 답안이 이미 했으므로, 그다음 줄에서 가정의 부등식을 대입하면 된다: $2^{n+1} = 2 \cdot 2^n > 2n$ [가정 $n < 2^n$ 소비] $= n + n \ge n + 1$ [$n \ge 1$]. 추이성으로 $n + 1 < 2^{n+1}$이 나오고 답안이 완성된다. **귀납 단계에서 막히면 가장 먼저 의심할 것은 계산이 아니라 소비 점검 ㄱ이다** — 아직 쓰지 않은 가정이 손에 남아 있는지부터 본다. 이 명제는 1권 31주차 문제 16이고, 완성된 답안은 이번 주 문제 10에서 다시 적는다. **답안 2의 진단 — 기저 붕괴.** 이쪽은 소비 점검을 통과하기 때문에 더 그럴듯해 보인다. 실제로 귀납 단계는 참인 조건문이다 — "$n^2+n$이 홀수이면 $(n+1)^2 + (n+1)$도 홀수"는 홀수에 짝수를 더하면 홀수라는 사실(1권 1주차)로 정당하게 유도된다. 무너지는 곳은 걸음 ②다. 기저 $P(1)$이 확인되지 않았고, 확인하면 거짓이다. 사정은 더 나쁘다 — $n^2 + n = n(n+1)$은 연속한 두 정수의 곱이므로 언제나 짝수이고(1권 1주차 문제 16), 명제 자체가 **모든** $n$에서 거짓이다. 참인 귀납 단계 하나만으로는 아무것도 확보되지 않는다는 것이 삭제 실험 1의 결론이었고, 이 답안이 그 결론의 두 번째 사례다. 수리는 명제를 고치는 것이다 — 참인 명제는 "$n^2 + n$은 짝수이다"이고, 그 귀납 증명이 문제 9다. **두 진단이 함께 말하는 것.** 답안 1은 걸음 ③-나가 없고 답안 2는 걸음 ②가 없다. 검사가 둘 다 필요한 이유가 여기 있다 — 한쪽 검사만으로는 다른 쪽 결함이 그대로 통과한다. 답안을 읽을 때는 언제나 걸음 ② 확인, 소비 점검 ㄱ, 소비 점검 ㄴ의 순서로 세 번 건다. ### 관찰 — 같은 뼈대 예제 2.1과 2.2는 소재만 다를 뿐 걸음이 같다. 대응표의 빈칸을 채워 보자. | **걸음** | **예제 2.1 (합)** | **예제 2.2 (나누어떨어짐)** | |---|---|---| | ① 이름 붙이기 | $P(n)$: $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$ | $\underline{\quad(1)\quad}$ | | ② 기저 | $n=1$: 좌변 $1$ $=$ 우변 $1$ | $\underline{\quad(2)\quad}$ | | ③-가 개시 | $P(n)$을 가정하고 식으로 푼다 | $P(n)$을 가정하고 정수 $m$을 받아 온다 | | ③ 쪼개기 | $\sum^{n+1} = \left(\sum^{n}\right) + (n+1)$ | $\underline{\quad(3)\quad}$ | | ③-나 소비 | $\frac{n(n+1)}{2} + (n+1)$ | $\underline{\quad(4)\quad}$ | | ③-다 도착 | $\frac{(n+1)(n+2)}{2}$ | $3(m + n^2 + n)$ | | ④ 결론 선언 | 귀납 공리 | 귀납 공리 | :::{container} quotebox **확인 20.** 빈칸 (1)~(4)를 채우고, 두 열이 다른 곳은 정확히 어느 줄인지 지목해 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $P(n)$: $3 \mid (n^3 - n)$ (2) $n=1$: $1^3 - 1 = 0 = 3 \cdot 0$ (3) $(n+1)^3 - (n+1) = (n^3 - n) + 3n^2 + 3n$ (4) $3m + 3(n^2+n)$. 두 열이 다른 곳은 쪼개기 줄 하나다. 합이면 마지막 항을 떼고, 나누어떨어짐이면 전개해 재그룹한다 — 그 차이가 §1.5 표의 네 줄이다. 나머지 여섯 줄은 명제가 무엇이든 같은 문장이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **귀납 답안의 4단 서식과 세 검사** 서식: ① 이름 붙이기 $\to$ ② 기저 검증 $\to$ ③ 귀납 단계(개시 $\cdot$ 쪼개기 $\cdot$ 소비 $\cdot$ 도착) $\to$ ④ 결론 선언. 검사: 걸음 ② 확인 $\to$ 소비 점검 ㄱ($P(n)$의 식이 등장하는가) $\to$ 소비 점검 ㄴ(실제로 대입했는가). 서식은 답안을 쓰는 순서이고, 검사는 답안을 읽는 순서다. ::: 이 서식은 이번 주 이후로도 형태만 바꿔 계속 쓰인다 — 강한 귀납은 걸음 ③-가의 가정을 넓히고, 최소 반례법은 걸음 ②와 ③을 귀류 쪽에서 다시 적는다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다. 훈련이 진행될수록 빈칸이 커진다. ### 훈련 1 ●○○ — 수식과 절차의 빈칸 **명제.** 모든 자연수 $n$에 대해 $\displaystyle\sum_{k=1}^{n} (2k - 1) = n^2$이다 (처음 $n$개의 홀수의 합). **증명.** $n$에 대한 귀납법으로 증명한다. $P(n)$을 "$\sum_{k=1}^{n}(2k-1) = n^2$"이라 하자. **(기저)** $n = 1$: 좌변 $= 2 \cdot 1 - 1 = 1$, 우변 $= \underline{\quad(1)\quad}$이므로 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 곧 $\sum_{k=1}^{n}(2k-1) = n^2$이다. 보일 것은 $\sum_{k=1}^{n+1}(2k-1) = \underline{\quad(2)\quad}$이다. 쪼개기부터 한다. $$ \sum_{k=1}^{n+1}(2k-1) = \left(\sum_{k=1}^{n}(2k-1)\right) + \underline{\quad(3)\quad} $$ 여기서 떼어 낸 항은 $k = n+1$을 대입해 얻은 것이다. 이제 가정을 대입하면 $$ = n^2 + (2n+1) = \underline{\quad(4)\quad} $$ 이고 이것이 도착점과 일치하므로 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 모든 자연수 $n$에서 $P(n)$이 참이다. $\blacksquare$ **소비 점검.** 가정이 소비된 곳은 위에서 "$\sum_{k=1}^{n}(2k-1)$"을 "$\underline{\quad(5)\quad}$"으로 바꾼 순간이고, 그 자리를 만들어 준 것은 $\underline{\quad(6)\quad}$ 줄이다. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 근거 번호와 근거 문장도 빈칸이다. **명제.** 모든 자연수 $n$에 대해 $4 \mid (5^n - 1)$이다. **증명.** $n$에 대한 귀납법으로 증명한다. $P(n)$을 "$4 \mid (5^n - 1)$"이라 하자. **(기저)** $n = 1$: $5^1 - 1 = 4 = 4 \cdot 1$이므로 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. $\underline{\quad(1)\quad}$의 정의에 의해 $5^n - 1 = \underline{\quad(2)\quad}$인 정수 $m$이 존재한다. 보일 것은 $4 \mid (5^{n+1} - 1)$이다. 쪼개기부터 한다. $$ 5^{n+1} - 1 = 5 \cdot 5^n - 1 = 5(\underline{\quad(3)\quad}) + 4 $$ 이 변형은 근거 $\underline{\quad(4)\quad}$이다. 이제 가정을 대입하면 $$ = 5 \cdot 4m + 4 = 4(\underline{\quad(5)\quad}) $$ 이고, $\underline{\quad(6)\quad}$이므로 괄호 안은 정수이다. 따라서 $4 \mid (5^{n+1} - 1)$이고 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 모든 자연수 $n$에서 $P(n)$이 참이다. $\blacksquare$ **소비 점검.** ㄱ: $P(n)$의 식이 등장하는 줄은 $\underline{\quad(7)\quad}$이다. ㄴ: 대입이 일어난 줄은 그다음 줄이다. ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 형태 판정부터 스스로 한다. 각 칸을 문장으로 통째로 채운다. **명제.** 8 이상의 모든 정수 $n$은 $3a + 5b$ ($a, b$는 음이 아닌 정수) 꼴로 쓸 수 있다. - ① 형태 판정과 그 근거 (§1.6 표의 어느 줄이며 보폭은 얼마인가): $\underline{\quad(1)\quad}$ - ② 기저 — 몇 개를 확인해야 하며 각각 어떤 표현인가: $\underline{\quad(2)\quad}$ - ③ 귀납 단계의 개시 문장 (가정의 범위를 정확히 적을 것): $\underline{\quad(3)\quad}$ - ④ 몸통 — $n+1$의 표현을 어느 항에서 만들며, 그 항이 가정의 범위 안에 있는 이유: $\underline{\quad(4)\quad}$ - ⑤ 결론 선언과 그 근거: $\underline{\quad(5)\quad}$ (이 훈련이 문제 19의 예행연습이다. 두 명제는 우표의 액면과 보폭만 다르다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 근거가 점수다. 귀납 답안의 제출 규격은 다섯 가지다: ① 이름 붙이기("$P(n)$을 …이라 하자") ② 기저의 좌변$\cdot$우변을 각각 계산한 줄 ③ 귀납 단계의 개시 문장이 $n$을 "하나 임의로 고정"했을 것 ④ 가정 소비처의 표시 ⑤ 결론 선언. 계산이 전부 옳아도 ④가 없으면 그 답안은 귀납이 아니므로 귀납법 문제의 답으로 읽히지 않는다. 형태를 묻는 문제는 이름만 적지 말고 §1.6 표의 어느 줄이 근거인지 지목한다. 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 귀납의 2단 구조, "귀납 단계 = 조건문 증명", 가정 소비처의 표준 동작(쪼개기), 세 형태(약한 귀납$\cdot$강한 귀납$\cdot$최소 반례법)를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 정의 14.1, §1.3의 두 게임 비교 표, §1.4의 4단 서식과 소비 점검, §1.5의 쪼개기 표, §1.6의 세 형태 표가 그대로 답이다. 통째로 외우기보다 "새로 들어오는 것은 근거 하나뿐이고 나머지는 조건문 증명"이라는 한 문장에서 나머지를 재구성하는 쪽이 재현률이 높다. ::: **2.** 다음 각 명제에서 $P(n+1)$의 식을 "$P(n)$의 식 $+$ 나머지" 또는 "$P(n)$의 식 $\times$ 나머지" 꼴로 쪼개는 첫 줄만 쓰시오 (증명은 하지 말 것). (a) $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$ (b) $2^n$ (거듭제곱 — $2^{n+1}$을 쪼개시오) (c) $\prod_{k=1}^{n} \frac{k}{k+1}$ (곱) (d) $n!$ ($(n+1)!$을 쪼개시오) :::{admonition} 힌트 :class: quotebox dropdown 네 문항 모두 §1.5 표의 한 줄에 대응한다. 합이면 마지막 항, 거듭제곱이면 한 인수, 곱이면 마지막 인수, 계승이면 마지막 인수를 떼어 낸다. 떼어 낸 뒤 남은 덩어리가 $P(n)$의 식과 글자 그대로 같은지 확인한다. ::: **3.** 예제 2.1을 백지에 재현하시오. 쪼개기 줄과 가정 소비처를 각각 표시하시오. :::{admonition} 힌트 :class: quotebox dropdown 아홉 줄이고, 그중 귀납다운 줄은 하나다. 서식 네 걸음의 이름(이름 붙이기$\cdot$기저$\cdot$ 귀납 단계$\cdot$결론 선언)을 먼저 세로로 적어 놓고 칸을 채우면 빠뜨리는 줄이 줄어든다. ::: **4.** 빈칸 사다리의 훈련 1~3을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 3에서 막히면 기저의 개수부터 정한다. 보폭이 정해지면 기저 개수가 정해지고, 기저 개수가 정해지면 귀납 단계의 개시 문장에 적을 범위가 정해진다. ::: **5.** 예제 2.3의 두 답안을 재현하고, 각각의 병명(가정 미소비 / 기저 붕괴)과 수리를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 병명을 적기 전에 세 검사를 순서대로 건다 — 걸음 ② 확인, 소비 점검 ㄱ, 소비 점검 ㄴ. 어느 검사에 걸리는지가 곧 병명이다. 수리는 답안 1은 한 줄 추가, 답안 2는 명제 자체의 교체다. ::: **6.** "귀납 단계는 조건문 $P(n) \Rightarrow P(n+1)$이다"를 S1주차의 언어로 설명하고, 이 조건문의 출발점과 도착점을 명시하시오. :::{admonition} 힌트 :class: quotebox dropdown S1주차의 물음 세 개를 그대로 옮긴다 — 무엇이 주어지고, 무엇을 확신시켜야 하며, 어떤 근거가 허용되는가. 셋째 물음의 답이 이 주의 요점이다. 귀납 단계 안에서 쓸 수 있는 근거가 이전 주와 같다는 것을 한 줄로 적는다. ::: ### 표준 ●●○ **7.** 모든 자연수 $n$에 대해 $\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$임을 귀납으로 증명하시오 (문제 2(a)의 쪼개기를 활용하시오). :::{admonition} 힌트 :class: quotebox dropdown 소비 후의 식 $\frac{n(n+1)(2n+1)}{6} + (n+1)^2$에서 $(n+1)$을 먼저 묶는다. 남은 괄호를 정리하면 이차식이 나오고, 그것이 인수분해되는지가 관문이다. 도착점은 $\frac{(n+1)(n+2)(2n+3)}{6}$이므로 이차식은 $(n+2)(2n+3)$이 되어야 한다. ::: **8.** 모든 자연수 $n$에 대해 $\displaystyle\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 소비 후의 식 $\left(\frac{n(n+1)}{2}\right)^2 + (n+1)^3$에서 공통인수 $(n+1)^2$을 묶는다. 남는 것은 $\frac{n^2}{4} + (n+1)$이고, 통분하면 완전제곱이 나온다. ::: **9.** 모든 자연수 $n$에 대해 $2 \mid (n^2 + n)$임을 귀납으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2와 같은 요령이다. $(n+1)^2 + (n+1)$을 전개해 $(n^2+n)$ 덩어리가 보이도록 재그룹하면 나머지가 무엇인지 보인다. 이 명제는 1권 1주차 문제 16과 S5주차 문제 3(a)에서 다른 방법으로 이미 증명했으므로, 같은 결론에 이르는 세 번째 경로다. ::: **10.** 모든 자연수 $n$에 대해 $n < 2^n$임을 증명하시오. 가정 소비처를 명확히 표시하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.3 답안 1이 멈춘 자리에서 이어 간다. 쪼개기 $2^{n+1} = 2 \cdot 2^n$까지는 그 답안이 이미 했고, 그다음 줄에서 가정의 부등식을 대입하면 $2n$이 나온다. $2n$에서 $n+1$까지 가는 데 필요한 것은 $n \ge 1$ 하나다. ::: **11.** 5 이상의 모든 자연수 $n$에 대해 $2^n > n^2$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 소비 후에 손에 있는 것은 $2^{n+1} > 2n^2$이고 도착점은 $(n+1)^2$이다. 그 사이를 잇는 다리, 곧 $2n^2 > (n+1)^2$을 따로 증명해야 한다(1권 32주차의 연결 부등식). 차를 계산하면 $n^2 - 2n - 1$이고, 완전제곱으로 고쳐 쓰면 부호가 보인다. ::: **12.** 다음 답안을 진단하시오. :::{container} quotebox "명제: 모든 자연수 $n$에 대해 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$이다. 증명: (기저) $n=1$에서 성립한다. (귀납 단계) $\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$임을 보이자. 좌변은 $1 + 2 + \cdots + (n+1)$인데, 등차수열의 합 공식에 의해 이 값은 $\frac{(n+1)(n+2)}{2}$이다. 따라서 성립한다." ::: :::{admonition} 힌트 :class: quotebox dropdown 검사할 질문은 둘이다. 소비 점검 ㄱ에 걸리는가. 인용된 "등차수열의 합 공식"은 근거 목록의 몇 번인가 — 그 공식이 증명된 적이 있는가. 두 질문의 답이 병명을 정한다. §1.4 삭제 실험 2와 확인 9의 (나)가 같은 **병**(증명 대상과 같은 공식을 근거로 인용)을 다룬다 — 다만 명제는 각각 홀수의 합과 자연수의 합으로 다르다. ::: **13.** 2 이상의 모든 정수는 소수이거나 소수들의 곱임을 증명하시오. 약한 귀납으로는 왜 안 되는지도 한 줄로 쓰시오. :::{admonition} 몸통에 들어오는 도구 — 합성수의 분해 :class: quotebox 2 이상의 정수는 소수이거나 합성수이고, 합성수 $N$에는 정의상 $N = ab$이면서 $1 < a < N$, $1 < b < N$인 정수 $a, b$가 존재한다. 이 사실은 합성수의 정의를 풀어 쓴 것이므로 근거 ①로 쓴다. 이 문제의 관문은 그 $a$와 $b$가 $N$의 직전 칸이 아니라는 데 있다 — $N = 100$이면 $a = 4$일 수도 있다. 약한 귀납의 가정 $P(n)$ 하나로는 그런 $a$를 덮지 못하고, 정의 14.2의 누적 가정이 필요하다. 이 명제는 1권 33주차 예제 2.1과 같은 정리다(소인수분해의 존재 파트). ::: :::{admonition} 힌트 :class: quotebox dropdown $n+1$을 두 경우로 나눈다 — 소수인 경우와 합성수인 경우. 첫 경우는 한 줄로 끝난다. 둘째 경우에서 분해 $n+1 = ab$를 얻은 뒤, $a$와 $b$가 각각 가정의 범위 $2 \le k \le n$ 안에 있음을 **부등식으로** 확인하는 줄을 빠뜨리지 않는다. ::: **14.** 모든 자연수 $n$에 대해 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$임을 최소 반례법으로 증명하고, 예제 2.1과 나란히 놓아 "최소 반례법은 귀납을 귀류 쪽에서 적은 것"임을 확인하시오. :::{admonition} 몸통에 들어오는 도구 — 최소원리와 최소 반례법의 서식 :class: quotebox 최소원리: 자연수의 부분집합이 비어 있지 않으면 최소원소를 갖는다(1권 33주차 §1.5에서 채택했고 이 과정에서도 근거 ④로 쓴다). 최소 반례법의 서식은 네 걸음이다 — ① 반례 집합 $R$을 정의하고 $R \neq \varnothing$이라 가정한다 ② 최소원리로 최소 반례 $n^*$을 잡는다 ③ 기저에 해당하는 값이 반례가 아님을 보여 $n^*$의 위치를 밀어낸다 ④ $n^* - 1$이 반례가 아님(최소성)을 써서 $n^*$도 반례가 아님을 유도하고 모순을 선언한다. ::: :::{admonition} 힌트 :class: quotebox dropdown 걸음 ④에서 쓰는 것이 정확히 예제 2.1의 쪼개기와 소비다. $n^*$에서 $n^* - 1$로 내려가는 방향만 반대일 뿐 계산은 같은 계산이다. 두 답안을 나란히 적어 놓고 어느 줄과 어느 줄이 대응하는지 화살표로 이어 본다. ::: ### 도전 ●●● **15.** $F_1 = F_2 = 1$, $F_{n+2} = F_{n+1} + F_n$으로 정의된 피보나치 수열에 대해, 모든 자연수 $n$에서 $F_n < 2^n$임을 증명하시오. 기저가 두 개 필요한 이유도 쓰시오. :::{admonition} 몸통에 들어오는 도구 — 두 칸 점화식 :class: quotebox 점화식 $F_{n+2} = F_{n+1} + F_n$은 수열의 귀납적 정의이고(1권 34주차), 이 등식은 $n+2 \ge 3$에서만 뜻을 갖는다. 곧 이 등식이 만들어 낼 수 있는 항은 $F_3$부터이고, $F_1$과 $F_2$는 정의가 직접 준 값이다. 귀납 단계는 도착 첨자 $n+2$에서 $F_{n+1}$과 $F_n$을 참조하므로 가장 작은 참조 첨자가 $n$이고, 보폭 규칙(§1.6)에 의해 $d = (n+2) - n = 2$이며 기저도 두 개다. ::: :::{admonition} 힌트 :class: quotebox dropdown 소비 후에 손에 있는 것은 $2^{n+1} + 2^n$이고 도착점은 $2^{n+2}$이다. $2^n$으로 묶으면 $3 \cdot 2^n$이 되고, $2^{n+2} = 4 \cdot 2^n$과 비교하면 여유가 얼마인지 그 자리에서 보인다. ::: **16.** $x > -1$인 모든 실수 $x$와 모든 자연수 $n$에 대해 $(1 + x)^n \ge 1 + nx$임을 증명하시오. 조건 $x > -1$이 귀납 단계의 어느 줄에서 소비되는지 명시하시오. :::{admonition} 몸통에 들어오는 도구 — 부등식 양변에 곱하기 :class: quotebox 부등식 $A \ge B$의 양변에 $c$를 곱할 때 부등호의 방향이 보존되는 것은 $c > 0$인 경우뿐이다(1권 16주차 (W3)). 그러므로 귀납 가정에 $(1+x)$를 곱하려면 그 앞에 "$x > -1$이므로 $1 + x > 0$이다"라는 줄이 반드시 있어야 한다. 곱하는 것의 부호를 확인하는 이 한 줄이 부등식 귀납에서 가장 자주 빠지는 줄이다. 이 명제는 1권 32주차 문제 11에서 $x \ge -1$이라는 더 넓은 자격으로 다룬 것과 같은 부등식이다. ::: :::{admonition} 힌트 :class: quotebox dropdown 곱한 뒤 전개하면 $1 + (n+1)x + nx^2$이 나온다. 도착점은 $1 + (n+1)x$이므로 남는 항 하나를 버려야 하고, 버릴 수 있는 근거는 (W1)이다. ::: **17.** 다음 답안에 대해 (a)와 (b)에 답하시오. :::{container} quotebox "명제: 모든 자연수 $n$에 대해 $n = n + 1$이다. 증명: (귀납 단계) $P(n)$: $n = n+1$을 가정하면 양변에 1을 더해 $n + 1 = n + 2$, 곧 $P(n+1)$이다. 따라서 귀납 단계가 성립한다." ::: (a) 이 귀납 단계가 조건문으로서 **타당함**을 확인하시오. (b) 그런데도 명제는 거짓이다. 무엇이 빠졌는지 지목하고, 예제 2.3 답안 2와 묶어 "귀납의 두 조건이 둘 다 필요한 이유"를 서술하시오. :::{admonition} 힌트 :class: quotebox dropdown (a)에서 검사할 것은 전건의 진위가 아니라 유도의 정당성이다 — 1권 8주차 진리표의 어느 행이 이 상황인지 지목한다. (b)에서는 정의 14.1의 조건 ①과 ②를 각각 확인하고, 하나만 성립할 때 확보되는 명제가 몇 개인지 세어 본다. ::: **18.** "모든 자연수 $n$에 대해, 임의의 $n$개의 실수는 모두 같다"는 거짓 명제의 다음 '증명'을 분석하시오. :::{container} quotebox "(기저) $n = 1$: 한 개의 실수는 자기 자신과 같다. (귀납 단계) $P(n)$을 가정하자. $n+1$개의 실수 $a_1, \dots, a_{n+1}$에서 앞의 $n$개 $a_1, \dots, a_n$은 가정에 의해 모두 같고, 뒤의 $n$개 $a_2, \dots, a_{n+1}$도 가정에 의해 모두 같다. 두 묶음이 겹치므로 $a_1, \dots, a_{n+1}$이 모두 같다. 따라서 $P(n+1)$이다." ::: 귀납 단계가 무너지는 $n$을 정확히 지목하고, 그 지목이 §1.4의 어느 걸음에 해당하는지 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown "두 묶음이 겹치므로"라는 줄이 성립하려면 공통 원소가 실제로 있어야 한다. 공통 부분은 $a_2, \dots, a_n$이고, 이 목록이 비지 않으려면 $n$에 조건이 붙는다. 가장 작은 $n$에서 그 조건을 확인해 본다. 이 답안은 1권 35주차 §1.2가 해부한 "모든 말은 같은 색"과 **같은 구조**의 사례이고, 오류 박물관 3관에 해당한다. ::: **19.** 12 이상의 모든 정수 $n$은 $4a + 5b$ ($a, b$는 음이 아닌 정수) 꼴로 쓸 수 있음을 증명하시오. 어느 형태를 쓸지 판단하고, 기저를 몇 개 잡아야 하는지 결정한 근거도 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown $n+1$을 만드는 길은 두 가지다 — 이미 만든 $n - 3$에 4를 더하거나, $n - 4$에 5를 더한다. 어느 쪽을 택하든 참조하는 항이 직전이 아니므로 형태는 정해진다. 기저 개수는 보폭과 같고, 보폭은 방금 택한 길이 몇 칸을 건너뛰는지로 정해진다. 훈련 3에서 같은 설계를 3원$\cdot$5원 우표로 이미 한 번 했다. ::: **20.** (서술) (a) "귀납 단계 = 조건문 증명"을 예제 2.1로 뒷받침하고, 그 증명에서 유일하게 새로운 것(가정 $P(n)$이라는 출발점과 쪼개기라는 소비 동작)이 무엇인지 세 문장 이내로 쓰시오. (b) 약한 귀납$\cdot$강한 귀납$\cdot$최소 반례법 세 형태가 하나의 원리의 세 표현임을, 문제 14의 결과를 근거로 두 문장 이내로 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown (a)는 예제 2.1 완성본의 아홉 줄 가운데 몇 줄이 이전 주의 기법으로 설명되는지 세는 것에서 시작한다. (b)는 문제 14에서 두 답안을 나란히 놓았을 때 대응하지 않고 남은 줄이 있었는지를 근거로 삼는다. ::: ## 백지 재현 — 복습 프로토콜 **이번 주의 5일 루틴.** 원서와 교안을 번갈아 쓰는 순서다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Solow 12장 통독 (모르는 문장은 표시만 하고 통과) | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다 | | 3일차 | 원서 재독 — 1일차에 표시한 문장을 해결하고, 원서 12장의 연습문제 몇 개를 직접 시도 | | 4일차 | 교안 §3 빈칸 사다리 + §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | 3일차의 재독이 이번 주에는 특히 중요하다. 원서 12장은 귀납 단계를 조건문 증명으로 다루는 관점을 짧은 문단으로 지나가므로, 교안 §1.3의 두 게임 비교 표와 §1.4의 4단 서식을 손에 쥐고 다시 읽으면 원서 예제의 각 줄이 서식의 어느 걸음인지 짚을 수 있다. 원서 예제에서 가정이 소비되는 줄에 직접 표시를 해 보는 것이 3일차의 실질적인 과제다. **1차 시도 — 틀 카드 허용.** 다음 세 상자만 옮겨 적은 카드를 펴 놓는다: 4단 서식(§1.4), 가정 소비 점검(§1.4), 쪼개기 표(§1.5). 그 상태에서 예제 2.1을 이름 붙이기부터 결론 선언까지 적는다. 예제 본문과 확인 상자는 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 정의 14.1(약한 귀납법)과 정의 14.2(강한 귀납법)를 조각 그대로 썼다. - [ ] 4단 서식을 쓰고, 각 걸음을 빼면 무엇이 무너지는지 절차 해부 표의 여섯 줄로 설명했다. - [ ] 가정 소비 점검 ㄱ$\cdot$ㄴ을 쓰고, 삭제 실험 2의 답안에서 ㄱ이 걸리는 것을 보였다. - [ ] §1.1의 실패 사례를 재현하고, 유한한 답안이 무한을 덮는 통로가 결론 선언 한 줄임을 지목했다. - [ ] 쪼개기 표 네 줄(합$\cdot$거듭제곱$\cdot$곱$\cdot$나누어떨어짐)을 재현하고 각각의 예를 하나씩 들었다. - [ ] 예제 2.1과 2.2를 처음부터 끝까지 재현하고, 각 답안에서 귀납다운 줄을 손가락으로 짚었다. - [ ] 예제 2.3의 두 답안을 병명과 함께 재현하고, 두 검사가 서로를 대신하지 못하는 이유를 한 줄로 적었다. - [ ] 세 형태 표를 재현하고, 확인 8의 세 명제를 표만 보고 다시 판정했다. - [ ] 보폭 규칙(보폭 $d$ = 도착 첨자 $-$ 가장 작은 참조 첨자, 기저 $d$개)을 쓰고, 문제 15와 문제 19에서 각각 기저가 몇 개인지 근거와 함께 말했다. - [ ] 원서 12장을 두 번 읽었고, 1일차에 표시한 문장이 전부 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 첫 문장부터 나오지 않는다 | §1.4의 4단 서식 — 걸음 ①과 ②는 창작이 아니라 정해진 문장이다 | | $P(n+1)$이 어떤 식인지 헷갈린다 | 확인 10 — $P(n)$의 $n$ 자리마다 $n+1$을 넣어 적은 뒤에 정리한다 | | 귀납 단계에서 다음 줄이 나오지 않는다 | 소비 점검 ㄱ부터 건다. $P(n)$의 식이 아직 등장하지 않았다면 필요한 것은 계산이 아니라 쪼개기다(§1.5) | | 쪼갤 곳을 모르겠다 | §1.5 표 — 합$\cdot$거듭제곱$\cdot$곱$\cdot$나누어떨어짐 중 어느 줄인지부터 정한다 | | 소비까지 했는데 도착점과 모양이 다르다 | 예제 2.1의 5단계 — 공통인수로 묶거나 통분해 도착점의 꼴에 맞춘다. 부등식이면 연결 부등식이 따로 필요하다(문제 11) | | 약한 귀납으로 하다 가정이 모자란다 | §1.6 둘째 줄 — 참조하는 항이 직전인지 확인한다. 직전이 아니면 정의 14.2로 갈아탄다 | | 기저를 몇 개 잡을지 모르겠다 | §1.6의 보폭 규칙 — 귀납 단계가 참조하는 가장 먼 첨자까지의 거리를 세고 그만큼 기저를 잡는다 | | 답안이 다 맞아 보이는데 통과되지 않는다 | 세 검사를 순서대로 건다 — 걸음 ② 확인, 소비 점검 ㄱ, 소비 점검 ㄴ (예제 2.3) | 하나라도 실패하면 그 항목만 다시 적고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $1^2 = 1$ (2) $(n+1)^2$ (3) $2(n+1) - 1 = 2n + 1$ (4) $n^2 + 2n + 1 = (n+1)^2$ (5) $n^2$ (6) 쪼개기(마지막 항 $2n+1$을 떼어 낸 줄) ※ (3)은 일반항 $2k-1$에 $k = n+1$을 대입해 얻는다. 이 대입을 건너뛰고 "다음 홀수"로 적으면 다음 줄의 계산에서 값을 다시 찾아야 한다. (4)의 검산: $n^2 + 2n + 1$을 완전제곱으로 묶으면 $(n+1)^2$이고, 이것이 (2)에 적은 도착점과 글자 그대로 같다. ### 빈칸 사다리 — 훈련 2 (1) 나누어떨어짐 (2) $4m$ (3) $5^n - 1$ (4) ③ (등식의 성질 — 전개와 재그룹) (5) $5m + 1$ (6) 정수의 곱과 합은 정수 (근거 ②) (7) 쪼개기 줄, 곧 $5^{n+1} - 1 = 5(5^n-1) + 4$ ※ (3)의 검산: $5(5^n - 1) + 4 = 5^{n+1} - 5 + 4 = 5^{n+1} - 1$ ✓. (5)의 검산: $4(5m+1) = 20m + 4 = 5 \cdot 4m + 4$ ✓. 이 명제는 1권 32주차 문제 8과 같은 것이고, 여기서는 결론이 아니라 거듭제곱 쪼개기가 나누어떨어짐 명제에서 어떻게 쓰이는지가 훈련 대상이다. ### 빈칸 사다리 — 훈련 3 (1) §1.6 표의 둘째 줄, 곧 **강한 귀납**이다. 신호는 고정 보폭형이고 보폭은 3이다 — $n+1$의 표현을 $n - 2$의 표현에서 만들기 때문이다. (2) 기저는 **세 개**다: $8 = 3 + 5$, $9 = 3 \cdot 3$, $10 = 5 \cdot 2$. 보폭이 3이므로 전달 장치가 덮지 못하는 앞의 세 자리를 직접 확인한다. (3) "$n \ge 10$인 정수 $n$을 하나 임의로 고정하고, $8 \le k \le n$인 모든 정수 $k$가 $3a + 5b$ 꼴로 쓰인다고 하자." (4) $n + 1 \ge 11$이므로 $n + 1 - 3 = n - 2 \ge 8$이고 동시에 $n - 2 \le n$이므로, $n-2$는 가정의 범위 $8 \le k \le n$ 안에 있다. 가정에 의해 $n - 2 = 3a + 5b$인 음이 아닌 정수 $a, b$가 있고, 양변에 3을 더하면 $n + 1 = 3(a+1) + 5b$이다. $a + 1$은 음이 아닌 정수이므로 $n+1$도 원하는 꼴이다. (5) "기저와 귀납 단계에 의해, 정의 14.2에 따라 8 이상의 모든 정수에서 성립한다." 근거는 ④(강한 귀납의 원리)다. ※ 이 명제는 1권 33주차 문제 8과 같다. 기저의 개수를 정하는 셈이 이 훈련의 핵심이고, 같은 셈이 문제 19에서 보폭 4로 반복된다. ### 문제 1 **접근.** 백지 항목은 네 덩어리다 — 정의 14.1의 두 조건, §1.3의 게임 비교, §1.4의 서식과 검사, §1.6의 세 형태. 항목을 나열하기 전에 "이번 주에 새로 들어오는 것은 근거 하나뿐"이라는 문장을 먼저 적어 두면, 나머지가 그 문장에서 재구성된다. **풀이.** ① **2단 구조**: 기저 $P(n_0)$의 검증과, 임의의 $n \ge n_0$에서 $P(n) \Rightarrow P(n+1)$의 증명. 이 둘이 확보되면 귀납 공리가 $n_0$ 이상의 모든 정수에서 $P(n)$을 준다. ② **귀납 단계 = 조건문 증명**: 출발점은 임의로 고정한 한 $n$에서의 $P(n)$, 도착점은 $P(n+1)$이고, 그 사이는 정의 풀기$\cdot$후진$\cdot$전진 등 이전 주들의 기법 그대로다. 새 기법은 들어오지 않는다. ③ **소비처의 표준 동작**: 도착점의 식을 "$P(n)$의 식 $+$ 나머지" 또는 "$P(n)$의 식 $\times$ 나머지"로 쪼갠다 — 합이면 마지막 항, 거듭제곱이면 한 인수, 곱$\cdot$계승이면 마지막 인수를 떼고, 나누어떨어짐이면 전개해 재그룹한다. 쪼갠 다음 줄에서 가정의 등식을 대입하는 자리가 소비처다. ④ **세 형태**: 직전 한 칸에만 의존하면 약한 귀납, 직전이 아닌 이전 항에 의존하면 (분해형이거나 고정 보폭형) 강한 귀납, 결론이 부재 꼴이거나 귀류 개시가 자연스러우면 최소 반례법. 보폭 $d$는 도착 첨자에서 귀납 단계가 참조하는 가장 작은 첨자까지의 거리이고, 기저가 $d$개다. **복기.** 백지 항목을 채점할 때는 낱말의 일치가 아니라 **삭제 실험을 재현할 수 있는가**로 본다. 기저를 지우면 무엇이 무너지는지, 소비를 지우면 무엇이 남는지를 사례로 말할 수 있으면 서식은 저절로 복구된다. ### 문제 2 **접근.** 네 문항 모두 §1.5 표의 한 줄에 대응한다. 쪼갠 뒤 남은 덩어리가 $P(n)$의 식과 **글자 그대로** 같은지 확인하는 것이 채점 지점이다. 비슷한 식이 나오면 소비를 할 수 없다. **풀이.** (a) $\displaystyle\sum_{k=1}^{n+1} k^2 = \left(\sum_{k=1}^{n} k^2\right) + (n+1)^2$. 합의 쪼개기이고, 떼어 낸 항은 일반항 $k^2$에 $k = n+1$을 넣은 것이다. (b) $2^{n+1} = 2^n \cdot 2$. 거듭제곱의 쪼개기이고, 지수법칙 $a^{m+1} = a^m \cdot a$ 한 번이다. (c) $\displaystyle\prod_{k=1}^{n+1} \frac{k}{k+1} = \left(\prod_{k=1}^{n} \frac{k}{k+1}\right) \cdot \frac{n+1}{n+2}$. 곱의 쪼개기이고, 떼어 낸 인수는 일반항 $\frac{k}{k+1}$에 $k = n+1$을 넣은 것이다. (d) $(n+1)! = (n+1) \cdot n!$. 계승의 정의를 한 번 푼 것이다. **복기.** 네 줄이 전부 "마지막 하나를 떼어 낸다"는 같은 동작이다. 합은 더하기로, 곱과 계승은 곱하기로, 거듭제곱은 인수 하나로 떼어질 뿐이다. 이 동작이 손에 붙으면 귀납 단계의 첫 줄에서 망설이는 일이 없어진다. ### 문제 3 **접근.** 재현의 채점 지점은 계산이 아니라 서식이다. 네 걸음의 이름을 세로로 적어 놓고 칸을 채우면 빠뜨리는 줄이 줄어든다. **풀이.** 예제 2.1의 완성본 표 아홉 줄을 그대로 적는다. 자가 채점 항목은 다음 다섯이다. ① 첫 줄에 "$P(n)$을 …이라 하자"가 있는가. ② 기저에서 좌변과 우변을 **각각** 계산해 적었는가($\frac{1 \cdot 2}{2} = 1$까지). ③ 개시 문장이 $n$을 "하나 임의로 고정"했는가. ④ 쪼개기 줄 $\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1)$과 소비 줄 $= \frac{n(n+1)}{2} + (n+1)$이 **서로 다른 두 줄**로 적혔는가. ⑤ 마지막 줄에 결론 선언이 있는가. ④가 한 줄로 뭉쳐 있으면 소비처를 표시할 자리가 없어지므로 두 줄로 나누어 적는 것이 규격이다. **검산.** $n = 3$을 넣어 답안을 다시 읽어 본다: 쪼개기는 $1+2+3+4 = (1+2+3) + 4$, 소비는 $6 + 4$, 정리는 $10 = \frac{4 \cdot 5}{2}$. 모든 줄이 그대로 성립한다. ### 문제 4 **접근.** 훈련마다 막히는 자리가 다르다. 훈련 1은 (3)의 대입, 훈련 2는 (3)의 쪼개기, 훈련 3은 기저 개수다. 막힌 훈련만 다시 적고 나머지는 넘어간다. **풀이.** 답은 위의 "빈칸 사다리 — 훈련 1$\cdot$2$\cdot$3" 항목에 있다. 자주 어긋나는 곳은 셋이다. 훈련 1의 (3)에서 일반항에 $k = n+1$을 대입하지 않고 "다음 홀수"라고만 적으면 다음 줄의 계산에서 값을 다시 찾아야 한다. 훈련 2의 (3)에서 $-1$을 $-5 + 4$로 가르는 조작을 떠올리지 못하면 쪼개기가 완성되지 않는다 — 거듭제곱을 먼저 쪼개고 상수를 맞추는 순서다. 훈련 3의 (2)에서 기저를 한 개만 잡으면 $n + 1 = 9$나 $10$을 만들 때 참조할 항($n-2$)이 8보다 작아져 가정의 범위를 벗어난다. **복기.** 세 훈련의 지지대는 각각 수식, 수식과 근거, 뼈대뿐이다. 훈련 3에서 손이 멈춘다면 부족한 것은 계산력이 아니라 설계 순서다 — 형태 판정 $\to$ 보폭 $\to$ 기저 개수 $\to$ 개시 문장의 범위 순으로 정하면 몸통은 한 줄이면 끝난다. ### 문제 5 **접근.** 병명을 적기 전에 세 검사를 순서대로 건다. 어느 검사에 걸리는지가 곧 병명이므로, 검사 없이 병명부터 적으면 두 답안을 뒤바꿔 진단하기 쉽다. **풀이.** **답안 1 — 가정 미소비.** 소비 점검 ㄱ에 걸린다. $P(n)$의 식은 "$n < 2^n$"인데 답안이 실제로 쓴 것은 "$2^n \ge 1$"이라는 다른 부등식이다. 수리는 소비처를 만드는 것 하나다: $2^{n+1} = 2 \cdot 2^n > 2 \cdot n$ [가정 $n < 2^n$의 양변에 2를 곱했다, (W3)] $= n + n \ge n + 1$ [$n \ge 1$이므로]. 추이성 (W6)으로 $n + 1 < 2^{n+1}$이고 $P(n+1)$이 참이다. **답안 2 — 기저 붕괴.** 소비 점검은 ㄱ$\cdot$ㄴ 모두 통과하고, 귀납 단계도 참인 조건문이다("홀수 $+$ 짝수 $=$ 홀수"). 걸리는 것은 걸음 ②다 — 기저가 아예 없고, 확인하면 $P(1)$: "$1^2 + 1 = 2$가 홀수"가 거짓이다. 더구나 $n^2 + n = n(n+1)$은 연속한 두 정수의 곱이므로 항상 짝수이고(1권 1주차 문제 16), 명제 자체가 모든 $n$에서 거짓이다. 수리는 명제의 교체다 — 참인 명제 "$n^2+n$은 짝수"의 귀납 증명이 문제 9다. **복기.** 두 답안이 서로 다른 검사에 걸린다는 것이 이 문제의 요점이다. 소비 점검만 거는 독자는 답안 2를 통과시키고, 기저만 보는 독자는 답안 1을 통과시킨다. 답안을 읽는 순서를 셋으로 고정해 두는 이유가 이것이다. ### 문제 6 **접근.** S1주차가 증명 과제에 던지는 물음은 셋이다 — 무엇이 주어지는가, 무엇을 확신시켜야 하는가, 어떤 근거가 허용되는가. 귀납 단계를 이 셋에 대입해 답하면 된다. 셋째 물음의 답이 이번 주의 요점이다. **풀이.** 귀납 단계가 증명하는 명제는 "임의의 $n \ge n_0$에 대해, $P(n)$이면 $P(n+1)$이다"라는 조건문이다. **출발점(주어지는 것)**은 임의로 고정한 한 $n$에서의 $P(n)$과 표준 정의$\cdot$정리이고, **도착점(확신시켜야 할 것)**은 같은 $n$에서의 $P(n+1)$이다. **허용되는 근거**는 §1.7의 다섯 칸이고, 그 가운데 귀납 단계 **안에서** 쓸 수 있는 것은 이전 주와 같다 — 이번 주에 늘어난 것(귀납 공리와 최소원리)은 걸음 ④와 최소 반례법의 개시에서만 쓰이고 귀납 단계 안에서는 쓰이지 않는다. 답안은 S1주차의 조건문 개시 문장 "$P(n)$이 참이라 하자"로 시작해 후진(도착점을 쪼개는 핵심 질문)과 전진(가정을 소비한 뒤의 계산)으로 $P(n+1)$에 도달한다. 귀납 단계에만 있는 특징은 출발점의 식이 도착점의 식 안에 숨어 있다는 것 하나이고, 그것이 쪼개기가 언제나 첫 걸음이 되는 이유다. **복기.** "귀납 단계 안에서는 귀납 공리를 쓰지 않는다"는 관찰이 이 문제의 값이다. 그 관찰이 있으면 귀납 단계에서 막혔을 때 꺼낼 도구가 S2~S13주차의 목록으로 한정되고, 검토할 후보가 줄어든다. ### 문제 7 **접근.** 쪼개기와 소비까지는 예제 2.1과 같은 동작이다. 관문은 소비 후의 정리다 — $(n+1)$을 먼저 묶고 남은 이차식이 $(n+2)(2n+3)$으로 인수분해되는지가 이 문제의 전부다. 도착점을 먼저 적어 두면 그 이차식이 무엇이어야 하는지가 정해진다. **풀이.** $n$에 대한 귀납법으로 증명한다. $P(n)$을 "$\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$"이라 하자. **(기저)** $n = 1$: 좌변 $= 1^2 = 1$, 우변 $= \frac{1 \cdot 2 \cdot 3}{6} = 1$이므로 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 보일 것은 $\sum_{k=1}^{n+1} k^2 = \frac{(n+1)(n+2)(2n+3)}{6}$이다 — 이는 $P(n)$의 우변에서 $n$ 자리마다 $n+1$을 넣어 정리한 것이다. 쪼개면 $$ \sum_{k=1}^{n+1} k^2 = \left(\sum_{k=1}^{n} k^2\right) + (n+1)^2 = \frac{n(n+1)(2n+1)}{6} + (n+1)^2 $$ 이고 둘째 등호가 가정 소비처다. 이어서 $$ \frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{(n+1)\big[n(2n+1) + 6(n+1)\big]}{6} = \frac{(n+1)(2n^2 + 7n + 6)}{6} = \frac{(n+1)(n+2)(2n+3)}{6} $$ 이다. 도착점과 일치하므로 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 모든 자연수 $n$에서 $P(n)$이 참이다. $\blacksquare$ **검산.** 인수분해: $(n+2)(2n+3) = 2n^2 + 3n + 4n + 6 = 2n^2 + 7n + 6$ ✓. $n = 3$: 좌변 $= 1 + 4 + 9 = 14$, 우변 $= \frac{3 \cdot 4 \cdot 7}{6} = 14$ ✓. **복기.** 합 공식 귀납의 정리 단계는 언제나 "공통인수 묶기 $\to$ 남은 다항식 인수분해"의 두 동작이다. 도착점을 먼저 적어 두면 인수분해의 목표가 정해지므로 시행착오가 없다. ### 문제 8 **접근.** 소비 후의 식에서 공통인수가 $(n+1)^2$이라는 것을 알아보는 것이 시작이다. $\left(\frac{n(n+1)}{2}\right)^2$에도 $(n+1)^2$이 들어 있고 $(n+1)^3$에도 들어 있다. 묶고 나면 남는 것은 통분 한 번이고, 그 결과가 완전제곱이 된다. **풀이.** $P(n)$을 "$\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$"이라 하자. **(기저)** $n = 1$: 좌변 $= 1$, 우변 $= \left(\frac{1 \cdot 2}{2}\right)^2 = 1$이므로 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 보일 것은 $\sum_{k=1}^{n+1} k^3 = \left(\frac{(n+1)(n+2)}{2}\right)^2$이다. 쪼개고 소비하면 $$ \sum_{k=1}^{n+1} k^3 = \left(\sum_{k=1}^{n} k^3\right) + (n+1)^3 = \frac{n^2(n+1)^2}{4} + (n+1)^3 $$ 이다. 공통인수 $(n+1)^2$으로 묶고 통분하면 $$ \frac{n^2(n+1)^2}{4} + (n+1)^3 = (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 $$ 이고 도착점과 일치하므로 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **검산.** $n = 3$: 좌변 $= 1 + 8 + 27 = 36$, 우변 $= \left(\frac{3 \cdot 4}{2}\right)^2 = 36$ ✓. $n^2 + 4n + 4 = (n+2)^2$ ✓. **복기.** 이 명제는 "세제곱의 합이 합의 제곱"이라는 형태이므로 예제 2.1의 결과를 읽는 데 쓸 수 있다 — 우변이 $\left(\sum_{k=1}^{n} k\right)^2$이다. 다만 증명 자체는 그 관찰을 쓰지 않는다. 관찰은 결과를 기억하는 데 쓰고, 증명은 쪼개기와 소비로 독립적으로 세운다. ### 문제 9 **접근.** 예제 2.2와 같은 요령이다. 나누어떨어짐의 가정에서 정수 하나를 받아 오고, 도착점의 식을 전개해 $(n^2+n)$ 덩어리가 보이도록 재그룹한다. 남은 항이 2의 배수인지 확인하면 끝난다. **풀이.** $P(n)$을 "$2 \mid (n^2 + n)$"이라 하자. **(기저)** $n = 1$: $1^2 + 1 = 2 = 2 \cdot 1$이므로 $2 \mid 2$이고 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 정의에 의해 $n^2 + n = 2m$인 정수 $m$이 존재한다. 보일 것은 $2 \mid \big((n+1)^2 + (n+1)\big)$이다. 전개해 재그룹하면 $$ (n+1)^2 + (n+1) = n^2 + 2n + 1 + n + 1 = (n^2 + n) + 2n + 2 $$ 이고, 가정을 대입하면 $= 2m + 2(n+1) = 2(m + n + 1)$이다. $m + n + 1$은 정수이므로 (근거 ②) $2 \mid \big((n+1)^2 + (n+1)\big)$이고 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **검산.** $n = 4$: $16 + 4 = 20 = 2 \cdot 10$ ✓. $n = 5$: $25 + 5 = 30 = 2 \cdot 15$ ✓. **복기.** 같은 명제를 이 과정에서 세 번째로 증명했다 — 1권 1주차 문제 16은 연속한 두 정수의 곱으로, S5주차 문제 3(a)는 구성법으로, 여기서는 귀납으로 다뤘다. 세 증명이 의존하는 부품이 각각 다르므로, 어느 부품이 손에 있는지에 따라 고를 수 있다는 것이 세 경로를 모두 적어 두는 이유다. 예제 2.3 답안 2가 거짓 명제로 만든 것이 바로 이 식이라는 점도 함께 기억해 둔다. ### 문제 10 **접근.** 예제 2.3 답안 1이 멈춘 자리에서 이어 간다. 쪼개기까지는 그 답안이 이미 했고, 필요한 것은 가정의 부등식을 실제로 대입하는 한 줄이다. 대입 후에는 $2n$에서 $n+1$까지 가는 다리가 필요하고, 그 다리는 $n \ge 1$ 하나로 놓인다. **풀이.** $P(n)$을 "$n < 2^n$"이라 하자. **(기저)** $n = 1$: $1 < 2 = 2^1$이므로 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 곧 $n < 2^n$이다. 보일 것은 $n + 1 < 2^{n+1}$이다. 거듭제곱을 쪼개고 가정을 소비하면 $$ 2^{n+1} = 2 \cdot 2^n > 2 \cdot n $$ 이다. 부등식 $n < 2^n$의 양변에 양수 2를 곱했으므로 방향이 보존된다((W3)) — 이 줄이 **가정 소비처**다. 이어서 $n \ge 1$이므로 $2n = n + n \ge n + 1$이고, 추이성((W6))에 의해 $2^{n+1} > n + 1$이다. 따라서 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 모든 자연수 $n$에서 $n < 2^n$이다. $\blacksquare$ **검산.** $n = 4$: $4 < 16$ ✓. $n = 10$: $10 < 1024$ ✓. **복기.** 부등식 귀납의 답안은 두 개의 부등식을 이어 붙여 만든다 — 가정을 소비해 얻은 것($2^{n+1} > 2n$)과, 그 중간값에서 도착점까지 가는 다리($2n \ge n+1$)다. 다리를 놓는 줄이 1권 32주차가 연결 부등식이라 부른 것이고, 그것을 빼먹는 것이 부등식 귀납에서 가장 흔한 결함이다(1권 35주차 오류 박물관 4관). ### 문제 11 **접근.** 소비까지는 문제 10과 같다. 이 문제의 무게는 연결 부등식 $2n^2 > (n+1)^2$에 있고, 그것은 귀납이 아니라 보통의 부등식 증명으로 따로 처리한다 — 차를 계산해 부호를 확정하는 것이 표준 동작이다. **풀이.** $P(n)$을 "$2^n > n^2$"이라 하고 $n_0 = 5$로 둔다. **(기저)** $n = 5$: $2^5 = 32$이고 $5^2 = 25$이므로 $32 > 25$이고 $P(5)$가 참이다. **(귀납 단계)** $n \ge 5$인 정수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 곧 $2^n > n^2$이다. 보일 것은 $2^{n+1} > (n+1)^2$이다. 쪼개고 소비하면 $$ 2^{n+1} = 2 \cdot 2^n > 2n^2 $$ 이다(양변에 2를 곱했다, (W3)). 이제 연결 부등식 $2n^2 > (n+1)^2$을 따로 보인다. 차를 계산하면 $$ 2n^2 - (n+1)^2 = 2n^2 - n^2 - 2n - 1 = n^2 - 2n - 1 = (n-1)^2 - 2 $$ 이고, $n \ge 5$이므로 $(n-1)^2 \ge 16 > 2$이다. 따라서 $2n^2 - (n+1)^2 > 0$, 곧 $2n^2 > (n+1)^2$이다. 두 부등식을 추이성((W6))으로 이으면 $2^{n+1} > (n+1)^2$이고 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해 5 이상의 모든 자연수에서 성립한다. $\blacksquare$ **검산.** $n = 5$: $2^6 = 64 > 36 = 6^2$ ✓. $n = 6$: $128 > 49$ ✓. 연결 부등식은 $n = 3$에서 $(3-1)^2 - 2 = 2 > 0$이므로 이미 성립한다 — 기저가 5인 이유는 연결 부등식이 아니라 $2^n > n^2$ 자체가 $n = 2, 3, 4$에서 성립하지 않기 때문이다($2^2 = 4 = 2^2$, $2^3 = 8 < 9$, $2^4 = 16 = 16$). **복기.** S10주차 문제 11에서 "$\forall n \in \mathbb{N}: 2^n \ge n^2$"이 거짓임을 반례로 보이고 자격을 "$n = 1$ 또는 $n \ge 4$"로 수리해 진술만 해 두었다. 그 수리된 명제의 참을 확정하는 것이 이번 문제이고, 부등호를 등호 없는 쪽으로 좁히면 시작점이 4가 아니라 5가 된다($n = 4$에서는 등호가 성립한다). $\ge$ 판이 실제로 거짓인 자리는 $n = 3$ 하나뿐이므로 S10주차의 자격 "$n = 1$ 또는 $n \ge 4$"는 참이긴 하지만 최대 자격은 아니다 — $n = 2$에서도 $4 \ge 4$로 성립한다. 반례가 자격을 좁히고 귀납이 그 좁혀진 자격 안에서 참을 확정하는 이 두 걸음이 한 명제를 다루는 표준 순서다. ### 문제 12 **접근.** 검사할 질문은 둘이다. 소비 점검 ㄱ에 걸리는가. 인용된 "등차수열의 합 공식"은 근거 목록의 몇 번인가. 두 질문의 답이 병명을 정한다. **풀이.** 병명은 **가정 미소비이자 순환**이다. 소비 점검 ㄱ부터 걸린다 — $P(n)$의 식 "$\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$"이 답안 어디에도 등장하지 않는다. 개시 문장조차 없이 도착점부터 적었고, 귀납 가정은 선언조차 되지 않았다. 다음으로 인용된 "등차수열의 합 공식"은 근거 목록에 없다. 그 공식의 첫 항이 1, 공차가 1인 경우가 바로 지금 증명하려는 명제이므로, 이 인용은 결론을 다른 이름으로 근거에 올린 것이다 (확인 9의 (나)). 수리는 인용을 지우고 예제 2.1의 세 줄로 바꾸는 것이다: 쪼개기 $\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1)$, 소비 $= \frac{n(n+1)}{2} + (n+1)$, 정리 $= \frac{(n+1)(n+2)}{2}$. 기저도 "성립한다"로 줄이지 말고 좌변 $1$, 우변 $\frac{1 \cdot 2}{2} = 1$을 각각 적는다. **복기.** 같은 병이 S7주차 문제 18(증명 대상을 특수화해 증명이라 주장)과 S11주차 문제 12(충돌 상대로 미확보 사실을 인용)에서도 나왔다. 형태는 달라도 검사 질문은 하나다 — **인용한 문장이 이미 확보된 것인가.** 귀납 답안에서 "공식에 의해"가 결론과 같은 공식을 가리키면 그 줄은 근거가 아니다. ### 문제 13 **접근.** $n+1$이 소수인 경우와 합성수인 경우로 나눈다. 첫 경우는 한 줄로 끝나고, 둘째 경우에서 분해 $n+1 = ab$를 얻는다. 관문은 $a$와 $b$가 가정의 범위 안에 있음을 부등식으로 확인하는 줄이다 — 그 줄이 없으면 강한 가정을 쓸 자격이 확보되지 않는다. **풀이.** 강한 귀납법으로 증명한다. $P(n)$을 "$n$은 소수이거나 소수들의 곱이다"라 하고 $n_0 = 2$로 둔다. **(기저)** $n = 2$: 2는 소수이므로 $P(2)$가 참이다. **(귀납 단계)** $n \ge 2$인 정수 $n$을 하나 임의로 고정하고, $2 \le k \le n$인 모든 정수 $k$에서 $P(k)$가 참이라 하자. $n+1$을 보인다. 두 경우로 나눈다. **경우 1: $n+1$이 소수인 경우.** $P(n+1)$이 곧바로 참이다. **경우 2: $n+1$이 합성수인 경우.** 합성수의 정의에 의해 $n + 1 = ab$이면서 $1 < a < n+1$, $1 < b < n+1$인 정수 $a, b$가 존재한다. $a$와 $b$는 정수이고 $1 < a$이므로 $2 \le a$이며, $a < n+1$이므로 $a \le n$이다. 곧 $2 \le a \le n$이고 같은 이유로 $2 \le b \le n$이다. 따라서 $a$와 $b$는 모두 가정의 범위 안에 있으므로 $P(a)$와 $P(b)$가 참이다 — 곧 $a$와 $b$는 각각 소수이거나 소수들의 곱이다. 그 표현들을 이어 붙이면 $n + 1 = ab$도 소수들의 곱이다. 두 경우가 $n+1$의 모든 가능성을 덮으므로 $P(n+1)$이 참이다. 기저와 귀납 단계에 의해, 정의 14.2에 따라 2 이상의 모든 정수에서 성립한다. $\blacksquare$ **약한 귀납으로 안 되는 이유.** 경우 2에서 실제로 쓴 것은 $P(a)$와 $P(b)$이고, $a$와 $b$는 $n$의 직전 칸이라는 보장이 전혀 없다 — $n+1 = 100$이면 $a = 4$일 수 있다. 약한 귀납의 가정은 $P(n)$ 하나뿐이므로 $P(4)$를 꺼낼 자격이 없다. 누적 가정이 필요한 것은 이 자격 때문이다(§1.6 둘째 줄, 분해형 신호). **복기.** 이 정리는 1권 33주차 예제 2.1과 같고, 산술의 기본정리의 존재 파트다. 유일성 파트는 훨씬 어렵고 유클리드 보조정리를 요구하며, 2학기 C15주차에서 청산된다. 존재와 유일을 두 게임으로 분리해 관리하는 것은 S13주차의 규격 그대로다. ### 문제 14 **접근.** 최소 반례법의 네 걸음을 그대로 따른다. 계산 자체는 예제 2.1의 쪼개기와 소비를 방향만 바꿔 쓰는 것이므로 새로 만들 것이 없다. 걸음 ③에서 $n^* \ge 2$를 확보해야 $n^* - 1$이 자연수가 되고, 그래야 최소성을 쓸 수 있다. **풀이.** 반례 집합을 $R = \left\{n \in \mathbb{N} : \sum_{k=1}^{n} k \neq \frac{n(n+1)}{2}\right\}$이라 하고, $R \neq \varnothing$이라 가정하자. $R$은 자연수의 부분집합이고 비어 있지 않으므로 최소원리에 의해 최소원 $n^*$이 존재한다(근거 ④, 1권 33주차). $n = 1$은 반례가 아니다 — $\sum_{k=1}^{1} k = 1 = \frac{1 \cdot 2}{2}$이기 때문이다. 따라서 $1 \notin R$이고 $n^* \ge 2$이므로 $n^* - 1$은 자연수다. $n^* - 1 < n^*$이고 $n^*$이 $R$의 최소원이므로 $n^* - 1 \notin R$, 곧 $$ \sum_{k=1}^{n^*-1} k = \frac{(n^*-1)n^*}{2} $$ 이다. 그러면 $$ \sum_{k=1}^{n^*} k = \left(\sum_{k=1}^{n^*-1} k\right) + n^* = \frac{(n^*-1)n^*}{2} + n^* = \frac{(n^*-1)n^* + 2n^*}{2} = \frac{n^*(n^*+1)}{2} $$ 이다. 이는 $n^*$이 반례가 아니라는 뜻이고 $n^* \in R$과 모순이다. 따라서 $R = \varnothing$이고, 모든 자연수 $n$에서 $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$이다. $\blacksquare$ **예제 2.1과의 대조.** 줄과 줄이 다음처럼 대응한다. 예제 2.1의 기저($P(1)$ 확인)는 여기서 "$1 \notin R$"이 되어 $n^*$의 위치를 2 이상으로 밀어내는 데 쓰인다. 예제 2.1의 귀납 가정($P(n)$)은 여기서 최소성이 주는 "$n^* - 1 \notin R$"이다. 예제 2.1의 쪼개기와 소비 두 줄은 위 계산의 첫 두 등호로 글자까지 같다. 예제 2.1의 결론 선언은 여기서 모순 선언과 $R = \varnothing$의 결론으로 바뀐다. 곧 **최소 반례법은 귀납을 귀류 쪽에서 적은 서식**이고, 대응하지 않고 남는 줄이 없다. **복기.** S11주차와 S12주차에서 귀류와 대우가 같은 계산을 다른 방향으로 적는 것을 보았고, 여기서 귀납과 최소 반례법이 같은 관계에 있음을 확인했다. 세 형태 중 무엇을 고를지는 계산의 난이도가 아니라 개시 문장이 얼마나 자연스러운가로 정한다 — "반례가 있다면"으로 시작하는 편이 자연스러운 명제가 최소 반례법의 자리다. 이 명제는 1권 33주차 문제 11에서도 같은 방법으로 다뤘다. ### 문제 15 **접근.** 귀납 단계가 도착 첨자 $n+2$에서 참조하는 가장 작은 첨자가 $n$이므로 보폭이 2이고, 보폭 규칙에 의해 기저도 두 개다. 소비 후에 손에 있는 것은 $2^{n+1} + 2^n$이므로 $2^n$으로 묶어 도착점 $2^{n+2} = 4 \cdot 2^n$과 비교하면 된다. **풀이.** 강한 귀납법으로 증명한다. $P(n)$을 "$F_n < 2^n$"이라 하자. **(기저)** $n = 1$: $F_1 = 1 < 2 = 2^1$이므로 $P(1)$이 참이다. $n = 2$: $F_2 = 1 < 4 = 2^2$이므로 $P(2)$가 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $1 \le k \le n+1$인 모든 정수 $k$에서 $P(k)$가 참이라 하자. 이것은 정의 14.2 ②의 $n$ 자리에 $n+1$을 넣은 것이다 — $n_0 = 1$, $d = 2$이므로 ②의 범위 조건은 $n + 1 \ge n_0 + d - 1 = 2$, 곧 모든 자연수 $n$에서 성립한다. 누적 가정 가운데 실제로 소비하는 것은 $P(n)$과 $P(n+1)$ 둘이고, 곧 $F_n < 2^n$이고 $F_{n+1} < 2^{n+1}$이다. 보일 것은 $P(n+2)$, 곧 $F_{n+2} < 2^{n+2}$이다. 점화식으로 쪼개고 두 가정을 소비하면 $$ F_{n+2} = F_{n+1} + F_n < 2^{n+1} + 2^n $$ 이다(두 부등식을 변변 더했다, (W2)와 (W6)). 이어서 $2^{n+1} + 2^n = 2 \cdot 2^n + 2^n = 3 \cdot 2^n < 4 \cdot 2^n = 2^{n+2}$이므로, 추이성에 의해 $F_{n+2} < 2^{n+2}$이고 $P(n+2)$가 참이다. 기저 두 개와 귀납 단계에 의해, 정의 14.2에 따라 모든 자연수 $n$에서 $F_n < 2^n$이다. $\blacksquare$ **기저가 두 개인 이유.** 귀납 단계의 첫 등식 $F_{n+2} = F_{n+1} + F_n$은 점화식이고, 그 점화식은 첨자가 3 이상인 항에서만 값을 준다. 곧 이 귀납 단계가 만들어 낼 수 있는 명제는 $P(3)$부터이고, $P(1)$과 $P(2)$는 어떤 $n$을 넣어도 나오지 않는다. 두 자리는 직접 확인하는 수밖에 없다. 피보나치에서는 보폭 2와 소비하는 가정 2개가 우연히 일치한다 — 도착 첨자 $n+2$에서 가장 작은 참조 첨자 $n$까지의 거리도 2이고, 실제로 소비한 가정도 $P(n)$과 $P(n+1)$ 둘이다. 훈련 3과 문제 19처럼 둘이 갈라지는 경우에 기저의 개수를 정하는 것은 보폭 쪽이다(§1.6의 주의 상자, 1권 34주차 §1.5). **검산.** $F_1, \dots, F_6 = 1, 1, 2, 3, 5, 8$이고 $2^1, \dots, 2^6 = 2, 4, 8, 16, 32, 64$이므로 여섯 자리 모두 부등식이 성립한다 ✓. **복기.** 부등식의 여유가 $3 \cdot 2^n$ 대 $4 \cdot 2^n$으로 넉넉하다는 것이 이 명제가 쉬운 이유다. 상계를 더 조이면(예를 들어 1권 34주차 문제 18의 $\varphi^{n-1}$) 연결이 등호로 딱 떨어지고 여유가 사라진다. 상계의 여유가 클수록 연결 부등식이 쉬워진다는 것이 부등식 귀납의 일반적인 사정이다. ### 문제 16 **접근.** 귀납 가정에 $(1+x)$를 곱해 도착점으로 간다. 관문은 곱하기 전에 곱하는 것의 부호를 확정하는 줄이다 — $1 + x$가 음수이면 부등호가 뒤집혀 답안 전체가 무너진다. 조건 $x > -1$이 정확히 그것을 막는다. **풀이.** $x > -1$인 실수 $x$를 하나 고정하자. $P(n)$을 "$(1+x)^n \ge 1 + nx$"라 하자. $x$는 끝까지 고정된 값이고 귀납은 $n$에 대해서만 한다. **(기저)** $n = 1$: 좌변 $= (1+x)^1 = 1 + x$, 우변 $= 1 + 1 \cdot x = 1 + x$이므로 등호로 성립하고 $P(1)$이 참이다. **(귀납 단계)** 자연수 $n$을 하나 임의로 고정하고, $P(n)$이 참이라 하자. 곧 $(1+x)^n \ge 1 + nx$이다. 보일 것은 $(1+x)^{n+1} \ge 1 + (n+1)x$이다. $x > -1$이므로 $1 + x > 0$이다 — **여기서 조건 $x > -1$이 소비된다.** 곱하는 것이 양수이므로 가정의 양변에 $1+x$를 곱해도 부등호의 방향이 보존된다((W3)). 거듭제곱을 쪼개고 소비하면 $$ (1+x)^{n+1} = (1+x)^n (1+x) \ge (1 + nx)(1 + x) = 1 + (n+1)x + nx^2 $$ 이다. $n$은 자연수이고 (W1)에 의해 $x^2 \ge 0$이므로 $nx^2 \ge 0$이고, 따라서 $1 + (n+1)x + nx^2 \ge 1 + (n+1)x$이다. 추이성((W6))으로 $(1+x)^{n+1} \ge 1 + (n+1)x$이고 $P(n+1)$이 참이다. $x$가 $-1$보다 큰 임의의 실수였으므로, 기저와 귀납 단계에 의해 결론이 성립한다. $\blacksquare$ **소비처 두 곳.** 조건 $x > -1$은 "$1 + x > 0$"을 확보하는 줄에서 소비되고, 귀납 가정은 그다음 줄의 부등호에서 소비된다. 두 소비처를 따로 표시하는 것이 이 문제의 채점 지점이다. $x \le -1$이면 어떻게 무너지는지도 확인해 두면 좋다 — 예를 들어 $x = -2$, $n = 2$에서 좌변은 $(-1)^2 = 1$이고 우변은 $1 + 2(-2) = -3$이라 우연히 성립하지만, 곱하기 단계에서 부등호가 뒤집히므로 이 증명 자체는 성립하지 않는다. **복기.** 부등식 귀납에서 가정에 무엇을 곱하거나 더할 때는 그 대상의 부호를 먼저 확정한다 — 이것이 S7주차의 자격 검증이 부등식에서 나타나는 모양이다. 이 부등식은 1권 32주차 문제 11에서 $x \ge -1$이라는 더 넓은 자격으로 다룬 것과 같은 명제이고, 그쪽에서는 $1 + x \ge 0$만으로 충분하다는 것도 함께 확인해 둔다. ### 문제 17 **접근.** (a)에서 검사할 것은 전건이 참인지가 아니라 유도가 정당한지다. (b)에서는 정의 14.1의 두 조건을 각각 확인하고, 하나만 성립할 때 확보되는 명제가 몇 개인지 세어 본다. **풀이.** **(a)** 귀납 단계가 주장하는 것은 조건문 "$n = n+1$이면 $n+1 = n+2$"이다. $n = n+1$이라는 등식을 손에 쥐었다고 **가정하면**, 양변에 1을 더하는 조작(근거 ③)만으로 $n + 1 = n + 2$가 나온다. 유도에 결함이 없으므로 이 조건문은 참이고, 귀납 단계는 모든 자연수 $n$에서 타당하다. 유도의 정당성 판정은 전건이 실제로 참인지를 묻지 않고, 전건이 거짓인 행에서는 조건문이 자동으로 참이다(1권 8주차 진리표의 전건이 거짓인 두 행 — 근거 ⑤). 그러므로 전건 "$n = n+1$"이 실제로는 언제나 거짓이라는 사실이 이 판정을 바꾸지 않는다. **(b)** 빠진 것은 정의 14.1의 조건 ①, 곧 기저다. $P(1)$은 "$1 = 2$"이고 이것은 거짓이므로 조건 ①이 성립하지 않는다. 정의 14.1은 ①과 ②를 **함께** 요구하므로, ②만 확보된 상태에서는 정의 14.1을 인용할 수 없고 결론 선언에 근거가 없다. 실제로 확보된 명제의 개수를 세어 보면 0개다 — 조건문은 "$P(n)$이 참이면"이라는 조건 아래에서만 결론을 주는데, 그 조건을 채워 줄 출발점이 하나도 없기 때문이다. 예제 2.3 답안 2도 같은 자리에서 무너진다. 그쪽은 기저를 아예 적지 않았고 적었더라면 거짓이었을 것이다. 두 답안을 묶으면 결론은 하나다 — **귀납 단계가 모든 $n$에서 참이어도 기저가 무너지면 확보되는 명제는 없다.** 정의 14.1의 두 조건은 각각 다른 일을 한다. 조건 ①은 목록의 시작점을 만들고, 조건 ②는 이미 확보된 자리에서 다음 자리로 옮기는 일만 한다. 옮길 출발점이 없으면 옮기는 장치는 아무것도 만들지 못한다. **복기.** 이 답안은 1권 31주차 문제 17이자 1권 35주차 오류 박물관 1관의 사례다. 탐지 질문은 한 줄이다 — 기저를 실제로 계산해 확인했는가. 답안에 "(기저) 자명하다"만 적혀 있으면 그 줄은 확인이 아니라 생략이다. ### 문제 18 **접근.** "두 묶음이 겹치므로"라는 줄이 이 답안의 유일한 연결 고리다. 그 줄이 성립하려면 공통 원소가 실제로 있어야 하므로, 공통 부분이 비는 $n$을 찾으면 된다. 가장 작은 $n$부터 확인한다. **풀이.** 귀납 단계의 논증은 앞 묶음 $\{a_1, \dots, a_n\}$과 뒤 묶음 $\{a_2, \dots, a_{n+1}\}$이 각각 내부적으로 모두 같음을 가정에서 얻은 뒤, 두 묶음의 **공통 원소**를 통해 두 묶음을 이어 붙인다. 공통 부분은 $a_2, \dots, a_n$이고, 이 목록이 비지 않으려면 $2 \le n$이어야 한다. 곧 이 논증은 $n \ge 2$에서만 작동한다. 무너지는 자리는 $n = 1$이다. 이때 앞 묶음은 $\{a_1\}$, 뒤 묶음은 $\{a_2\}$이고 공통 원소가 없으므로 $a_1 = a_2$를 잇는 근거가 전혀 없다. 실제로 $a_1 = 0$, $a_2 = 1$이면 가정("한 개의 실수는 자기 자신과 같다")은 두 묶음 모두에서 성립하지만 결론은 거짓이다. 따라서 조건문 $P(1) \Rightarrow P(2)$는 거짓이고, 귀납 단계가 **모든** $n$에서 성립한다는 주장이 무너진다. 이 결함은 §1.4 절차 해부 표의 걸음 **③-가**($n$을 하나 임의로 고정해 귀납 단계의 범위를 선언하는 자리)에 해당한다. 답안은 어느 $n$에서도 좋다는 듯이 적었지만 몸통은 $n \ge 2$에서만 유효하므로, 선언한 범위와 실제 유효 범위가 어긋났다. 기저 $P(1)$은 참이고 $n \ge 2$에서의 귀납 단계도 참이지만, 사슬은 $P(1)$에서 $P(2)$로 넘어가지 못하고 그 자리에서 끊긴다. 확보되는 것은 $P(1)$ 하나뿐이다. **복기.** 교훈은 하나다 — 귀납 단계를 적은 뒤에는 그 논증이 **가장 작은 $n$에서** 성립하는지 반드시 확인한다. 몸통이 "겹친다", "쪼갤 수 있다", "하나를 뺀다" 같은 조작을 쓰면 그 조작이 작은 $n$에서 가능한지가 언제나 검사 대상이다. 이 답안은 1권 35주차 §1.2가 해부한 "모든 말은 같은 색"과 **같은 구조**의 사례이고, 오류 박물관 3관(전달의 첫 고리 붕괴)에 해당한다. ### 문제 19 **접근.** $n+1$의 표현을 어디서 가져올지 먼저 정한다. $n - 3$의 표현에 4를 더하는 길을 택하면 참조하는 항이 직전이 아니므로 형태는 강한 귀납이고, 건너뛰는 칸이 4이므로 보폭이 4, 따라서 기저도 4개다. 설계가 정해지면 몸통은 두 줄이다. **풀이.** 강한 귀납법으로 증명한다. $P(n)$을 "$n = 4a + 5b$인 음이 아닌 정수 $a, b$가 존재한다"라 하고 $n_0 = 12$로 둔다. **(기저)** 보폭이 4이므로 기저를 네 개 확인한다. $12 = 4 \cdot 3 + 5 \cdot 0$, $13 = 4 \cdot 2 + 5 \cdot 1$, $14 = 4 \cdot 1 + 5 \cdot 2$, $15 = 4 \cdot 0 + 5 \cdot 3$이므로 $P(12), P(13), P(14), P(15)$가 모두 참이다. **(귀납 단계)** $n \ge 15$인 정수 $n$을 하나 임의로 고정하고, $12 \le k \le n$인 모든 정수 $k$에서 $P(k)$가 참이라 하자. $n + 1 \ge 16$이므로 $n + 1 - 4 = n - 3 \ge 12$이고, 동시에 $n - 3 \le n$이므로 $n - 3$은 가정의 범위 안에 있다. 따라서 $P(n-3)$이 참이고, $n - 3 = 4a + 5b$인 음이 아닌 정수 $a, b$가 존재한다. 양변에 4를 더하면 $$ n + 1 = 4a + 5b + 4 = 4(a+1) + 5b $$ 이고 $a + 1$은 음이 아닌 정수이므로 $P(n+1)$이 참이다. 기저 네 개와 귀납 단계에 의해, 정의 14.2에 따라 12 이상의 모든 정수에서 성립한다. $\blacksquare$ **기저를 네 개 잡는 이유.** 귀납 단계가 $n+1$을 만들 때 참조하는 항은 $n - 3$이므로 건너뛰는 칸이 4다. 귀납 단계는 $n + 1 \ge 16$에서만 작동하고, 곧 이 장치가 만들어 내는 명제는 $P(16)$부터다. $P(12), P(13), P(14), P(15)$ 네 자리는 어떤 $n$을 넣어도 나오지 않으므로 직접 확인해야 한다. 기저를 세 개만 잡으면 $n + 1 = 16$을 만들 때 참조하는 $12$는 확보되지만 $n+1 = 15$가 확보되지 않은 채 남는다. **검산.** $16 = 4 \cdot 4$, $17 = 4 \cdot 3 + 5$, $18 = 4 \cdot 2 + 5 \cdot 2$, $19 = 4 + 5 \cdot 3$ ✓. 참고로 11은 이 꼴로 쓸 수 없다 — $b = 0$이면 11이 4의 배수가 아니고, $b = 1$이면 남는 6이 4의 배수가 아니며, $b = 2$이면 남는 1이 4의 배수가 아니고, $b \ge 3$이면 $5b \ge 15 > 11$이라 애초에 불가능하다. 네 경우가 $b$의 모든 값을 덮으므로 11은 이 꼴로 쓸 수 없고, 곧 12라는 시작점은 최선이다. **복기.** 설계 순서를 고정해 두면 이런 문제는 기계적으로 풀린다 — ① $n+1$을 어느 항에서 만들지 정한다 $\to$ ② 그 항이 직전인지 확인해 형태를 정한다 $\to$ ③ 건너뛰는 칸수가 보폭이고 그만큼 기저를 잡는다 $\to$ ④ 귀납 단계의 개시 문장에 범위를 적는다. 이 명제는 1권 33주차 문제 12와 같고, 훈련 3의 3원$\cdot$5원 우표 문제는 같은 설계를 보폭 3으로 한 것이다. ### 문제 20 **접근.** (a)는 예제 2.1 완성본의 아홉 줄 가운데 몇 줄이 이전 주의 기법으로 설명되는지 세는 것에서 시작한다. (b)는 문제 14에서 두 답안을 나란히 놓았을 때 대응하지 않고 남은 줄이 있었는지를 근거로 삼는다. **풀이.** (예시 답안) **(a)** 예제 2.1의 귀납 단계는 "$P(n)$이 참이라 하자"로 시작해 $P(n+1)$에 도달하는 조건문 증명이고, 그 안에서 쓰인 것은 후진(도착점을 향한 쪼개기), 대입, 통분과 인수분해뿐으로 전부 S2~S3주차와 1권의 기법이다. 새로운 것은 둘뿐이다 — 출발점 목록에 $P(n)$이라는 가정이 하나 더 놓인다는 것, 그리고 그 가정을 쓰려면 도착점의 식을 "$P(n)$의 식 $+$ 나머지"로 쪼개어 소비처를 손으로 만들어야 한다는 것이다. 쪼개기(다섯째 줄)와 가정 소비(여섯째 줄), 그리고 귀납 공리를 인용하는 결론 선언 (아홉째 줄) 세 줄을 빼면, 나머지 여섯 줄은 전부 이전 주의 기법으로 설명된다 — 새 도구는 없고 새 근거가 하나 있을 뿐이다. **(b)** 문제 14에서 최소 반례법 답안과 예제 2.1의 귀납 답안을 나란히 놓았을 때 대응하지 않고 남은 줄이 하나도 없었다 — 기저는 "1은 반례가 아니다"로, 귀납 가정은 최소성이 주는 "$n^*-1$은 반례가 아니다"로, 쪼개기와 소비는 글자까지 같은 계산으로 옮겨졌다. 강한 귀납은 여기에 가정의 범위만 넓힌 것이므로, 세 형태는 서로 다른 원리가 아니라 자연수의 최소원리라는 하나의 원리를 개시 문장만 바꿔 적은 세 서식이다. **복기.** 세 형태를 하나로 보는 관점이 실전에서 주는 이득은 선택의 자유다. 어느 형태로 적어도 계산이 같으므로, 개시 문장이 가장 자연스러운 것을 고르면 된다 — 직전 한 칸이면 약한, 이전 여러 칸이면 강한, "반례가 있다면"으로 시작하는 편이 자연스러우면 최소 반례법이다. --- **다음 주 예고 (S15주차).** **양자택일법** — 가정이나 결론에 "또는"이 있을 때의 표준 공략법을 세운다. 결론이 "$P$ 또는 $Q$"이면 $\neg P$를 가정하고 $Q$를 보이는 소거법으로, 가정이 "$P$ 또는 $Q$"이면 경우를 나누는 경우법으로 처리한다. S12주차에서 대우가 "또는" 결론을 "그리고" 가정으로 바꿔 준 것과 소거법이 어떤 관계인지가 그 주의 첫 물음이다. 원서 13장을 통독하고 온다.