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}\) |
확인 10. 도착점 칸을 채워 보자. \(P(n+1)\)은 어떻게 만드는가.
답
\(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단계 — 이름을 붙이고 기저를 확인한다. 답안의 첫 두 문장은 창작이 아니라 서식이다.
확인 11. 첫 두 문장을 완성해 보자.
“\(n\)에 대한 귀납법으로 증명한다. \(P(n)\)을 ‘\(\underline{\qquad}\)’이라 하자.
(기저) \(n = 1\): 좌변 \(= \underline{\quad}\), 우변 \(= \underline{\quad}\)이므로 \(P(1)\)이 참이다.”
답
\(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주차의 조건문 개시 문장과 같은 모양이다.
확인 12. 개시 문장과 목표 명시 문장을 완성해 보자.
“(귀납 단계) 자연수 \(n\)을 \(\underline{\qquad}\), \(P(n)\)이 참이라 하자. 곧
\(\sum_{k=1}^{n} k = \underline{\qquad}\)이다. 보일 것은 \(\underline{\qquad}\)이다.”
답
“자연수 \(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)\)의 식)이 보이도록 왼쪽을 쪼갠다.
확인 13. 쪼개기 줄을 완성해 보자.
“\(\displaystyle\sum_{k=1}^{n+1} k = \left(\underline{\qquad}\right) + \underline{\qquad}\)”
답
\(\displaystyle\sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1)\).
합의 마지막 항 하나를 떼어 낸 것뿐이다(§1.5의 첫째 줄, 근거 ③). 이 줄이 끝난
순간 소비 점검 ㄱ이 통과된다 — \(P(n)\)의 좌변이 그대로 등장했다.
4단계 — 가정을 소비한다. 방금 만든 자리에 가정의 등식을 대입한다. 이 줄이 답안 전체에서 유일하게 귀납다운 줄이므로, 표시를 남겨 두는 것이 규격이다.
확인 14. 소비 줄을 완성해 보자.
“\(= \underline{\qquad} + (n+1)\) [귀납 가정 소비]”
답
\(= \frac{n(n+1)}{2} + (n+1)\).
대입한 것은 가정의 등식 \(\sum_{k=1}^{n} k = \frac{n(n+1)}{2}\)이다(근거 ③).
소비 점검 ㄴ이 여기서 통과된다. 답안에 “[귀납 가정]”이라고 적어 두면 읽는 쪽이
이 줄을 찾느라 답안 전체를 훑지 않아도 된다.
5단계 — 도착점까지 전진한다. 남은 것은 계산이고, 목표는 도착점의 식과 글자 그대로 일치시키는 것이다.
확인 15. 계산을 완주해 보자. \(\frac{n(n+1)}{2} + (n+1)\)을 정리하면 무엇이 되는가.
답
\(\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)\)과 조건문 하나뿐이다. 마지막 한 줄이 그 둘을 원명제로 바꾼다.
확인 16. 마지막 문장을 완성해 보자. 이 문장이 인용하는 근거는 몇 번인가.
답
“기저와 귀납 단계에 의해, 모든 자연수 \(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의 셋째 줄에서 이미 계산했다). 의존이 직전 한 칸이므로 약한 귀납이다.
이번에는 설계만 함께 하고 본문은 완성본으로 본다.
확인 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}\).
답
\(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의 배수다.
확인 18. 쪼개기 줄을 만들어 보자. \((n+1)^3 - (n+1)\)을 전개해 \(n^3 - n\)이 보이도록 재그룹하면 무엇이 남는가.
답
\((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\)에서 성립한다.”
확인 19. 두 답안에 소비 점검 ㄱ\(\cdot\)ㄴ과 걸음 ②의 검사를 각각 걸어 보자. 어느 검사에 걸리는가.
답
답안 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)\) |
④ 결론 선언 |
귀납 공리 |
귀납 공리 |
확인 20. 빈칸 (1)~(4)를 채우고, 두 열이 다른 곳은 정확히 어느 줄인지 지목해 보자.
답
(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 표의 네 줄이다. 나머지 여섯 줄은 명제가
무엇이든 같은 문장이다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
귀납 답안의 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}\)이다. 쪼개기부터 한다.
여기서 떼어 낸 항은 \(k = n+1\)을 대입해 얻은 것이다. 이제 가정을 대입하면
이고 이것이 도착점과 일치하므로 \(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)\)이다. 쪼개기부터 한다.
이 변형은 근거 \(\underline{\quad(4)\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분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. 귀납 답안의 제출 규격은 다섯 가지다: ① 이름 붙이기(”\(P(n)\)을 …이라 하자”) ② 기저의 좌변\(\cdot\)우변을 각각 계산한 줄 ③ 귀납 단계의 개시 문장이 \(n\)을 “하나 임의로 고정”했을 것 ④ 가정 소비처의 표시 ⑤ 결론 선언. 계산이 전부 옳아도 ④가 없으면 그 답안은 귀납이 아니므로 귀납법 문제의 답으로 읽히지 않는다. 형태를 묻는 문제는 이름만 적지 말고 §1.6 표의 어느 줄이 근거인지 지목한다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 귀납의 2단 구조, “귀납 단계 = 조건문 증명”, 가정 소비처의 표준 동작(쪼개기), 세 형태(약한 귀납\(\cdot\)강한 귀납\(\cdot\)최소 반례법)를 쓰시오.
힌트
정의 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)!\)을 쪼개시오)
힌트
네 문항 모두 §1.5 표의 한 줄에 대응한다. 합이면 마지막 항, 거듭제곱이면 한
인수, 곱이면 마지막 인수, 계승이면 마지막 인수를 떼어 낸다. 떼어 낸 뒤 남은
덩어리가 \(P(n)\)의 식과 글자 그대로 같은지 확인한다.
3. 예제 2.1을 백지에 재현하시오. 쪼개기 줄과 가정 소비처를 각각 표시하시오.
힌트
아홉 줄이고, 그중 귀납다운 줄은 하나다. 서식 네 걸음의 이름(이름 붙이기\(\cdot\)기저\(\cdot\)
귀납 단계\(\cdot\)결론 선언)을 먼저 세로로 적어 놓고 칸을 채우면 빠뜨리는 줄이 줄어든다.
4. 빈칸 사다리의 훈련 1~3을 백지에서 완성하시오.
힌트
훈련 3에서 막히면 기저의 개수부터 정한다. 보폭이 정해지면 기저 개수가 정해지고,
기저 개수가 정해지면 귀납 단계의 개시 문장에 적을 범위가 정해진다.
5. 예제 2.3의 두 답안을 재현하고, 각각의 병명(가정 미소비 / 기저 붕괴)과 수리를 쓰시오.
힌트
병명을 적기 전에 세 검사를 순서대로 건다 — 걸음 ② 확인, 소비 점검 ㄱ, 소비
점검 ㄴ. 어느 검사에 걸리는지가 곧 병명이다. 수리는 답안 1은 한 줄 추가,
답안 2는 명제 자체의 교체다.
6. “귀납 단계는 조건문 \(P(n) \Rightarrow P(n+1)\)이다”를 S1주차의 언어로 설명하고, 이 조건문의 출발점과 도착점을 명시하시오.
힌트
S1주차의 물음 세 개를 그대로 옮긴다 — 무엇이 주어지고, 무엇을 확신시켜야 하며,
어떤 근거가 허용되는가. 셋째 물음의 답이 이 주의 요점이다. 귀납 단계 안에서 쓸
수 있는 근거가 이전 주와 같다는 것을 한 줄로 적는다.
표준 ●●○#
7. 모든 자연수 \(n\)에 대해 \(\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}\)임을 귀납으로 증명하시오 (문제 2(a)의 쪼개기를 활용하시오).
힌트
소비 후의 식 \(\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\)임을 증명하시오.
힌트
소비 후의 식 \(\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)\)임을 귀납으로 증명하시오.
힌트
예제 2.2와 같은 요령이다. \((n+1)^2 + (n+1)\)을 전개해 \((n^2+n)\) 덩어리가 보이도록
재그룹하면 나머지가 무엇인지 보인다. 이 명제는 1권 1주차 문제 16과 S5주차 문제
3(a)에서 다른 방법으로 이미 증명했으므로, 같은 결론에 이르는 세 번째 경로다.
10. 모든 자연수 \(n\)에 대해 \(n < 2^n\)임을 증명하시오. 가정 소비처를 명확히 표시하시오.
힌트
예제 2.3 답안 1이 멈춘 자리에서 이어 간다. 쪼개기 \(2^{n+1} = 2 \cdot 2^n\)까지는
그 답안이 이미 했고, 그다음 줄에서 가정의 부등식을 대입하면 \(2n\)이 나온다.
\(2n\)에서 \(n+1\)까지 가는 데 필요한 것은 \(n \ge 1\) 하나다.
11. 5 이상의 모든 자연수 \(n\)에 대해 \(2^n > n^2\)임을 증명하시오.
힌트
소비 후에 손에 있는 것은 \(2^{n+1} > 2n^2\)이고 도착점은 \((n+1)^2\)이다. 그 사이를
잇는 다리, 곧 \(2n^2 > (n+1)^2\)을 따로 증명해야 한다(1권 32주차의 연결 부등식).
차를 계산하면 \(n^2 - 2n - 1\)이고, 완전제곱으로 고쳐 쓰면 부호가 보인다.
12. 다음 답안을 진단하시오.
“명제: 모든 자연수 \(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}\)이다. 따라서 성립한다.”
힌트
검사할 질문은 둘이다. 소비 점검 ㄱ에 걸리는가. 인용된 “등차수열의 합 공식”은
근거 목록의 몇 번인가 — 그 공식이 증명된 적이 있는가. 두 질문의 답이 병명을
정한다. §1.4 삭제 실험 2와 확인 9의 (나)가 같은 병(증명 대상과 같은 공식을
근거로 인용)을 다룬다 — 다만 명제는 각각 홀수의 합과 자연수의 합으로 다르다.
13. 2 이상의 모든 정수는 소수이거나 소수들의 곱임을 증명하시오. 약한 귀납으로는 왜 안 되는지도 한 줄로 쓰시오.
몸통에 들어오는 도구 — 합성수의 분해
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과 같은 정리다(소인수분해의 존재 파트).
힌트
\(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과 나란히 놓아 “최소 반례법은 귀납을 귀류 쪽에서 적은 것”임을 확인하시오.
몸통에 들어오는 도구 — 최소원리와 최소 반례법의 서식
최소원리: 자연수의 부분집합이 비어 있지 않으면 최소원소를 갖는다(1권 33주차
§1.5에서 채택했고 이 과정에서도 근거 ④로 쓴다). 최소 반례법의 서식은 네
걸음이다 — ① 반례 집합 \(R\)을 정의하고 \(R \neq \varnothing\)이라 가정한다
② 최소원리로 최소 반례 \(n^*\)을 잡는다 ③ 기저에 해당하는 값이 반례가 아님을
보여 \(n^*\)의 위치를 밀어낸다 ④ \(n^* - 1\)이 반례가 아님(최소성)을 써서
\(n^*\)도 반례가 아님을 유도하고 모순을 선언한다.
힌트
걸음 ④에서 쓰는 것이 정확히 예제 2.1의 쪼개기와 소비다. \(n^*\)에서
\(n^* - 1\)로 내려가는 방향만 반대일 뿐 계산은 같은 계산이다. 두 답안을 나란히
적어 놓고 어느 줄과 어느 줄이 대응하는지 화살표로 이어 본다.
도전 ●●●#
15. \(F_1 = F_2 = 1\), \(F_{n+2} = F_{n+1} + F_n\)으로 정의된 피보나치 수열에 대해, 모든 자연수 \(n\)에서 \(F_n < 2^n\)임을 증명하시오. 기저가 두 개 필요한 이유도 쓰시오.
몸통에 들어오는 도구 — 두 칸 점화식
점화식 \(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\)이며 기저도 두 개다.
힌트
소비 후에 손에 있는 것은 \(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\)이 귀납 단계의 어느 줄에서 소비되는지 명시하시오.
몸통에 들어오는 도구 — 부등식 양변에 곱하기
부등식 \(A \ge B\)의 양변에 \(c\)를 곱할 때 부등호의 방향이 보존되는 것은 \(c > 0\)인
경우뿐이다(1권 16주차 (W3)). 그러므로 귀납 가정에 \((1+x)\)를 곱하려면 그 앞에
“\(x > -1\)이므로 \(1 + x > 0\)이다”라는 줄이 반드시 있어야 한다. 곱하는 것의 부호를
확인하는 이 한 줄이 부등식 귀납에서 가장 자주 빠지는 줄이다. 이 명제는 1권
32주차 문제 11에서 \(x \ge -1\)이라는 더 넓은 자격으로 다룬 것과 같은 부등식이다.
힌트
곱한 뒤 전개하면 \(1 + (n+1)x + nx^2\)이 나온다. 도착점은 \(1 + (n+1)x\)이므로
남는 항 하나를 버려야 하고, 버릴 수 있는 근거는 (W1)이다.
17. 다음 답안에 대해 (a)와 (b)에 답하시오.
“명제: 모든 자연수 \(n\)에 대해 \(n = n + 1\)이다. 증명: (귀납 단계) \(P(n)\): \(n = n+1\)을 가정하면 양변에 1을 더해 \(n + 1 = n + 2\), 곧 \(P(n+1)\)이다. 따라서 귀납 단계가 성립한다.”
(a) 이 귀납 단계가 조건문으로서 타당함을 확인하시오. (b) 그런데도 명제는 거짓이다. 무엇이 빠졌는지 지목하고, 예제 2.3 답안 2와 묶어 “귀납의 두 조건이 둘 다 필요한 이유”를 서술하시오.
힌트
(a)에서 검사할 것은 전건의 진위가 아니라 유도의 정당성이다 — 1권 8주차 진리표의
어느 행이 이 상황인지 지목한다. (b)에서는 정의 14.1의 조건 ①과 ②를 각각
확인하고, 하나만 성립할 때 확보되는 명제가 몇 개인지 세어 본다.
18. “모든 자연수 \(n\)에 대해, 임의의 \(n\)개의 실수는 모두 같다”는 거짓 명제의 다음 ‘증명’을 분석하시오.
“(기저) \(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의 어느 걸음에 해당하는지 쓰시오.
힌트
“두 묶음이 겹치므로”라는 줄이 성립하려면 공통 원소가 실제로 있어야 한다. 공통
부분은 \(a_2, \dots, a_n\)이고, 이 목록이 비지 않으려면 \(n\)에 조건이 붙는다.
가장 작은 \(n\)에서 그 조건을 확인해 본다. 이 답안은 1권 35주차 §1.2가 해부한
“모든 말은 같은 색”과 같은 구조의 사례이고, 오류 박물관 3관에 해당한다.
19. 12 이상의 모든 정수 \(n\)은 \(4a + 5b\) (\(a, b\)는 음이 아닌 정수) 꼴로 쓸 수 있음을 증명하시오. 어느 형태를 쓸지 판단하고, 기저를 몇 개 잡아야 하는지 결정한 근거도 쓰시오.
힌트
\(n+1\)을 만드는 길은 두 가지다 — 이미 만든 \(n - 3\)에 4를 더하거나, \(n - 4\)에
5를 더한다. 어느 쪽을 택하든 참조하는 항이 직전이 아니므로 형태는 정해진다.
기저 개수는 보폭과 같고, 보폭은 방금 택한 길이 몇 칸을 건너뛰는지로 정해진다.
훈련 3에서 같은 설계를 3원\(\cdot\)5원 우표로 이미 한 번 했다.
20. (서술) (a) “귀납 단계 = 조건문 증명”을 예제 2.1로 뒷받침하고, 그 증명에서 유일하게 새로운 것(가정 \(P(n)\)이라는 출발점과 쪼개기라는 소비 동작)이 무엇인지 세 문장 이내로 쓰시오. (b) 약한 귀납\(\cdot\)강한 귀납\(\cdot\)최소 반례법 세 형태가 하나의 원리의 세 표현임을, 문제 14의 결과를 근거로 두 문장 이내로 설명하시오.
힌트
(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\)을 넣어 정리한 것이다. 쪼개면
이고 둘째 등호가 가정 소비처다. 이어서
이다. 도착점과 일치하므로 \(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\)이다. 쪼개고 소비하면
이다. 공통인수 \((n+1)^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)\)이다. 전개해 재그룹하면
이고, 가정을 대입하면 \(= 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}\)이다. 거듭제곱을 쪼개고 가정을 소비하면
이다. 부등식 \(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를 곱했다, (W3)). 이제 연결 부등식 \(2n^2 > (n+1)^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\), 곧
이다. 그러면
이다. 이는 \(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}\)이다. 점화식으로 쪼개고 두 가정을 소비하면
이다(두 부등식을 변변 더했다, (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)). 거듭제곱을 쪼개고 소비하면
이다. \(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를 더하면
이고 \(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장을 통독하고 온다.