35주차 · 강의 — 예제 · 연습 · 해설#
백지 시험 (31~34주차, 20문항)#
규칙. 교재를 덮고 150분 안에 푼다. 귀납 답안에는 [기초]/[귀납]과 “(귀납 가정)” 표시를 반드시 단다. 부등식 귀납에서는 연결 부등식을 별도의 줄로 표시한다.
기본 ●○○#
1. [백지] (a) 수학적 귀납법의 원리 (b) 강한 귀납법의 원리 (c) 최소원리를 각각 진술하시오.
2. 모든 자연수 \(n\)에 대해 \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\)임을 귀납법으로 증명하시오.
3. 모든 자연수 \(n\)에 대해 \(1 + 3 + 5 + \cdots + (2n-1) = n^2\)임을 귀납법으로 증명하시오.
4. \(a_1 = 1\), \(a_{n+1} = a_n + 5\)로 정의된 수열의 닫힌 꼴을 추측하고 귀납으로 확정하시오.
5. 실험으로 기초 위치를 찾으시오 (증명 불필요): “\(2^n > 10n\)”은 어느 자연수부터 계속 성립하는가? (\(n = 1, \dots, 7\) 대입)
6. 오류 박물관 1~5관의 이름(오류 유형)을 쓰고, 각 관의 탐지 질문을 한 줄씩 쓰시오.
표준 ●●○#
7. 모든 자연수 \(n\)에 대해 \(\displaystyle \sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}\)임을 증명하시오.
8. \(n \ge 4\)인 모든 정수에 대해 \(2^n \ge n^2\)임을 증명하시오 (32주차 예제 2.1 백지 재현 — 연결 부등식 포함).
9. 모든 자연수 \(n\)에 대해 \(9 \mid (10^n - 1)\)임을 귀납법으로 증명하시오.
10. \(a_1 = 2\), \(a_{n+1} = 3a_n\)의 닫힌 꼴을 추측하고 귀납으로 증명하시오.
11. 모든 자연수 \(n\)에 대해 \(F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1\)임을 증명하시오 (짝수 번째 피보나치의 합).
12. \(n \ge 12\)인 모든 정수는 \(3a + 7b\) (\(a, b \ge 0\)) 꼴임을 강한 귀납법으로 증명하시오 (기초 몇 개가 필요한지부터 판단할 것).
13. “모든 말은 같은 색” 가짜 증명을 요약해 쓰고, 전달이 무너지는 정확한 지점(\(k\) 값과 이유)을 해부하시오.
14. 연속한 두 피보나치 수는 서로소임을 귀납법으로 증명하시오 (34주차 문제 12 백지 재현).
도전 ●●●#
15. \(n \ge 1\)인 모든 자연수에 대해 \(3^n > n \cdot 2^n\)임을 귀납법으로 증명하시오. (기초 위치와 개수를 실험으로 정하고, 연결 부등식 \(3k \ge 2(k+1)\)의 성립 범위를 확인하시오)
16. “모든 자연수 \(n\)에 대해 \(n^2 + n\)은 짝수”를 최소 반례법으로 증명하시오 (1주차 문제 16의 명제를 자연수로 제한한 형태의 세 번째 증명 — 귀납 없이 최소원리로).
17. (진단 — 결함 2개) 다음 답안의 결함을 지적하고 수정하시오.
“명제: \(n \ge 1\)에서 \(4^n > n^2 + 3\). [기초] \(n=1\): \(4 > 4\)는 성립하지 않으므로 \(n = 2\): \(16 > 7\) ✓부터 시작한다. [귀납] \(4^k > k^2 + 3\) 가정. \(4^{k+1} = 4 \cdot 4^k > 4(k^2+3)\)이고, \(4(k^2+3)\)은 \((k+1)^2 + 3\)보다 크니까 성립한다. \(\blacksquare\)”
18. (진단 — 5관) 다음 답안을 진단하시오: 논리적 오류는 없는가? 그런데 왜 “나쁜 답안”인가? 어떻게 고쳐야 하는가?
“명제: 모든 자연수 \(n\)에 대해 \(6 \mid (n^3 + 5n)\). 증명: 귀납법. [기초] \(n=1\): \(6 \mid 6\) ✓. [귀납] \(6 \mid (k^3 + 5k)\) 가정. \((k+1)^3 + 5(k+1) = k^3 + 3k^2 + 8k + 6\). 그런데 \(k^3 + 5k = k(k^2+5)\)에서 \(k\) 홀짝 케이스와 mod 3 케이스로 \(k^3 + 5k = (k^3 - k) + 6k\)이고 \(6 \mid (k^3 - k)\)(30주차)이므로 \(6 \mid (k^3+5k)\) — 즉 임의의 \(k+1\)에서도 같은 논증으로 \(6 \mid ((k+1)^3 + 5(k+1))\). \(\blacksquare\)”
19. 모든 자연수 \(n\)에 대해 \(3 \mid (n^3 + 2n)\)임을 귀납법으로 증명하시오.
20. (서술) 자신의 “귀납 답안 자가 점검 체크리스트”를 다섯 항목(박물관 5관 대응)으로 작성하고, 이번 시험에서 실제로 걸린(틀릴 뻔한) 지점이 어느 관이었는지 기록하시오.
백지 복습 체크리스트 (시험 후)#
세 원리(귀납\(\cdot\)강귀납\(\cdot\)최소원리)를 정확히 진술했다 (1번).
말 역설의 붕괴 지점(\(P(1) \to P(2)\))을 해부했다 (13번).
부등식 귀납(8\(\cdot\)15번)에서 연결 부등식을 별도 표시했다.
진단 문제(17\(\cdot\)18번)에서 오류를 빠짐없이 짚었다 — 17번은 두 개(명제 범위 불일치 + 4관), 18번은 5관.
오류 체크리스트 5항목을 자기 언어로 만들었다 (20번).
해설#
틀린 문제는 접근만 읽고 재시도한 뒤 풀이를 확인한다.
문제 1#
접근. 세 원리는 각각 31주차 §1.3, 33주차 §1.3\(\cdot\)§1.5의 암기 상자다. 채점의 초점은 낱말 하나하나에 있다 — 조각이 하나 빠지면 원리가 무엇을 보장하지 못하게 되는지까지 짚는다.
풀이. (a) 수학적 귀납법의 원리. 자연수에 대한 명제 \(P(n)\)에 대해 ① \(P(1)\)이 참이고 ② 모든 \(k \ge 1\)에 대해 “\(P(k)\)가 참이면 \(P(k+1)\)도 참”이라는 것, 이 둘이 증명되면 모든 자연수 \(n\)에 대해 \(P(n)\)이 참이다. (b) 강한 귀납법의 원리. ① \(P(1)\)이 참이고(필요하면 \(P(1), P(2), \dots, P(n_0)\) 여러 개), ② 모든 \(k\)에 대해 “\(P(1), P(2), \dots, P(k)\)가 전부 참이면 \(P(k+1)\)도 참”이면, 모든 자연수 \(n\)에 대해 \(P(n)\)이 참이다. (c) 최소원리. 공집합이 아닌 자연수의 부분집합은 반드시 최소원소를 가진다. (음이 아닌 정수의 부분집합에서도 같다.)
복기. (b)에서 “\(P(1)\)부터 \(P(k)\)까지 전부”를 “\(P(k)\)”로 줄여 쓰면 보통 귀납법이 되어, 12번처럼 여러 칸 과거를 참조하는 증명이 근거를 잃는다. (c)에서 “공집합이 아닌”을 빠뜨리면 원소가 없는 집합에 최소원소를 요구하게 되어 진술 자체가 거짓이 되고, “자연수의”를 빠뜨리면 \(\{x \in \mathbb{Q} : x > 0\}\)이 반례가 된다.
문제 2#
접근. 31주차 예제 2.1과 같은 명제다. 합 공식의 귀납은 언제나 같은 두 동작으로 끝난다 — 좌변에서 마지막 항 \((k+1)\)을 떼어내 귀납 가정을 끼우고, 남은 식을 \((k+1)\)로 묶어 목표 꼴을 만든다.
풀이. [기초] \(n = 1\): 좌변은 \(1\), 우변은 \(\frac{1 \cdot 2}{2} = 1\)이므로 양변이 같다 ✓. [귀납] \(k \ge 1\)인 정수 \(k\)에 대해 \(1 + 2 + \cdots + k = \frac{k(k+1)}{2}\)라고 가정하자. 목표는 \(1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}\)이다.
곧 \(P(k+1)\)이 참이다. 귀납법의 원리에 의해 모든 자연수 \(n\)에서 성립한다. \(\blacksquare\)
복기. 검산: \(n = 4\)에서 좌변 \(1+2+3+4 = 10\), 우변 \(\frac{4 \cdot 5}{2} = 10\) ✓.
문제 3#
접근. 좌변은 홀수를 작은 것부터 더한 것이고, \(n\)번째 홀수가 \(2n - 1\)이다. \(P(k+1)\)의 좌변에서 마지막 항은 \(2(k+1) - 1 = 2k+1\)이다.
풀이. [기초] \(n = 1\): 좌변은 \(1\), 우변은 \(1^2 = 1\) ✓. [귀납] \(1 + 3 + \cdots + (2k-1) = k^2\)이라고 가정하자. 목표는 \(1 + 3 + \cdots + (2k+1) = (k+1)^2\)이다.
\(\blacksquare\)
복기. 검산: \(n = 3\)에서 \(1 + 3 + 5 = 9 = 3^2\) ✓. 마지막 항을 \(2k - 1\) 그대로 두고 계산하는 경우가 있는데, 도착점의 좌변은 \(n\) 자리에 \(k+1\)을 넣은 것이므로 마지막 항도 \(2(k+1) - 1\)로 바뀐다.
문제 4#
접근. 항을 계산하면 \(a_1 = 1\), \(a_2 = 6\), \(a_3 = 11\), \(a_4 = 16\) — 공차 5의 등차수열이다. 34주차 §1.6의 사이클대로 ①~③으로 추측을 만들고 ④에서 귀납으로 확정한다.
풀이. 추측: \(a_n = 5n - 4\). [기초] \(a_1 = 1\)이고 \(5 \cdot 1 - 4 = 1\) ✓. [귀납] \(a_k = 5k - 4\)라고 가정하자. 점화식을 먼저 대입하면
곧 \(P(k+1)\)이 참이다. \(\blacksquare\)
복기. 귀납 단계에서 가장 먼저 하는 일은 추측식 대입이 아니라 점화식 대입이다. 점화식으로 \(a_{k+1}\)을 \(a_k\)로 바꾼 다음에야 귀납 가정을 끼울 자리가 생긴다. 검산: \(a_4 = 16 = 5 \cdot 4 - 4\) ✓.
문제 5#
접근. 증명이 아니라 기초 위치의 탐색이므로 대입 표를 정확히 채우는 것이 전부다. 한 번 성립한 뒤에 다시 끊기지 않는지까지 보아야 “계속 성립”을 말할 수 있다.
풀이.
\(n\) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|---|---|---|---|---|---|---|---|
\(2^n\) |
2 |
4 |
8 |
16 |
32 |
64 |
128 |
\(10n\) |
10 |
20 |
30 |
40 |
50 |
60 |
70 |
판정 |
✗ |
✗ |
✗ |
✗ |
✗ |
✓ |
✓ |
따라서 \(n = 6\)부터 계속 성립한다.
복기. 이 뒤로 끊기지 않는 이유는 좌변이 2배씩 커지는 동안 우변은 10씩만 커지기 때문이다. 이 직관을 연결 부등식으로 굳히면 증명도 완성된다: \(k \ge 6\)에서 \(2^{k+1} = 2 \cdot 2^k > 2 \cdot 10k = 10k + 10k \ge 10(k+1)\)이다(마지막 부등호는 \(10k \ge 10\), 곧 \(k \ge 1\)에서 성립).
문제 6#
접근. 개념 절의 박물관 표를 백지에서 재현하는 문제다. 이름 다섯 개와 탐지 질문 다섯 개가 모두 필요하다.
풀이. 1관 기초 누락 — 기초를 실제로 계산\(\cdot\)확인했는가? 2관 기초 부족 / 가정 범위 초과 — 귀납 단계가 소비하는 가정이 몇 개인가(첨자에 \(F_{k-1}\)이 보이는 것과 \(P(k-1)\)을 가정으로 쓰는 것은 다르다 — 34주차 §1.5), 그만큼 기초가 있는가, 그리고 실제로 쓴 과거가 선언한 가정 안에 있는가(\(P(k)\)만 가정하고 \(P(k-1)\)을 쓰지 않았는가)? 3관 전달의 첫 고리 붕괴 — \(P(k) \Rightarrow P(k+1)\)이 모든 \(k\)에서, 특히 가장 작은 \(k\)에서 성립하는가? 4관 연결 부등식 생략 — 귀납 가정이 데려다준 중간값에서 목표까지의 다리를 실제로 놓았는가? 5관 귀납 가정 미사용 — “(귀납 가정)” 표시가 본문에 있는가, 없다면 귀납이 필요했는가?
복기. 다섯 관의 순서는 답안을 읽어 내려가는 순서와 같다. 채점할 때도 위에서부터 차례로 물으면 빠뜨리는 관이 없다.
문제 7#
접근. 합 공식이므로 마지막 항 \((k+1)(k+2)\)를 떼어내 귀납 가정을 끼운다. 그다음 목표 꼴 \(\frac{(k+1)(k+2)(k+3)}{3}\)을 보고 공통인수 \((k+1)(k+2)\)로 묶을 것을 미리 정해 둔다.
풀이. [기초] \(n = 1\): 좌변 \(1 \cdot 2 = 2\), 우변 \(\frac{1 \cdot 2 \cdot 3}{3} = 2\) ✓. [귀납] \(\sum_{i=1}^{k} i(i+1) = \frac{k(k+1)(k+2)}{3}\)이라고 가정하자. 목표는 \(\sum_{i=1}^{k+1} i(i+1) = \frac{(k+1)(k+2)(k+3)}{3}\)이다.
목표 꼴과 일치한다. \(\blacksquare\)
복기. 검산: \(n = 3\)에서 좌변 \(2 + 6 + 12 = 20\), 우변 \(\frac{3 \cdot 4 \cdot 5}{3} = 20\) ✓.
문제 8#
접근. 32주차 예제 2.1의 백지 재현이다. 부등식 귀납의 2단 구조를 그대로 쓴다 — ① 귀납 가정 투입으로 중간값 \(2k^2\)까지 간 뒤 ② 연결 부등식 \(2k^2 \ge (k+1)^2\)을 별도로 증명하고 ③ 추이성으로 잇는다. 가정 \(k \ge 4\)가 소비되는 곳이 어디인지 표시하는 것까지가 답안이다.
풀이. [기초] \(n = 4\): \(2^4 = 16\), \(4^2 = 16\)이므로 \(16 \ge 16\) ✓ (등호이지만 부등호가 \(\ge\)이므로 성립한다). [귀납] \(k \ge 4\)인 정수 \(k\)에 대해 \(2^k \ge k^2\)이라고 가정하자. 목표는 \(2^{k+1} \ge (k+1)^2\)이다. ① \(2^{k+1} = 2 \cdot 2^k \ge 2k^2\) (귀납 가정; 양변에 양수 \(2\)를 곱했으므로 16주차의 (W3)). ② 연결 부등식 \(2k^2 \ge (k+1)^2\)을 증명한다. 차를 계산하면
이고, \(k \ge 4\)이면 \(k - 1 \ge 3\)이므로 \((k-1)^2 \ge 9\), 따라서 \((k-1)^2 - 2 \ge 7 > 0\)이다. ③ 두 부등식을 추이성((W6))으로 이으면 \(2^{k+1} \ge 2k^2 \ge (k+1)^2\). \(\blacksquare\)
복기. 가정 \(k \ge 4\)가 쓰이는 자리는 ②의 한 줄뿐이다. 연결 부등식 자체는 \(k \ge 3\)부터 참이므로 기초 위치 \(n_0 = 4\)와 어긋나지 않는다. ②를 생략하면 그대로 4관 오류가 된다(32주차 문제 17).
문제 9#
접근. 목표 식 \(10^{k+1} - 1\) 안에 귀납 가정의 식 \(10^k - 1\)이 보이도록 쪼갠다: \(10^{k+1} - 1 = 10 \cdot 10^k - 1 = 10(10^k - 1) + 9\). 나누어떨어짐 귀납의 표준 동작이다.
풀이. [기초] \(n = 1\): \(10^1 - 1 = 9 = 9 \cdot 1\)이므로 \(9 \mid 9\) ✓. [귀납] \(9 \mid (10^k - 1)\)이라고 가정하자. 정의에 의해 \(10^k - 1 = 9m\)인 정수 \(m\)이 존재한다. 그러면
이고 \(10m + 1\)은 정수이므로 \(9 \mid (10^{k+1} - 1)\)이다. \(\blacksquare\)
복기. 마지막 두 줄을 “첫 항은 귀납 가정으로 9의 배수, 둘째 항 9도 9의 배수, 배수의 합도 배수(2주차 예제 2.2)”로 적어도 같은 증명이다. 31주차 문제 15(a)는 같은 사실을 합동으로 적은 것이다 — \(10^k \equiv 1 \pmod 9\).
문제 10#
접근. 항을 계산하면 \(2, 6, 18, 54\) — 공비 3의 등비수열이다. 닫힌 꼴의 지수를 \(n\)이 아니라 \(n-1\)로 잡아야 \(a_1 = 2\)와 맞는다.
풀이. 추측: \(a_n = 2 \cdot 3^{n-1}\). [기초] \(a_1 = 2\)이고 \(2 \cdot 3^0 = 2\) ✓. [귀납] \(a_k = 2 \cdot 3^{k-1}\)이라고 가정하자. 점화식을 대입하면
이고 \(3^k = 3^{(k+1)-1}\)이므로 \(P(k+1)\)이 참이다. \(\blacksquare\)
복기. 검산: \(a_4 = 2 \cdot 3^3 = 54\) ✓. 지수를 \(n\)으로 잡아 \(a_n = 2 \cdot 3^n\)으로 추측하면 기초에서 \(a_1 = 6 \ne 2\)로 즉시 걸린다 — 기초 확인이 추측의 검산 역할까지 한다.
문제 11#
접근. 좌변의 다음 항은 \(F_{2(k+1)} = F_{2k+2}\)이다. 귀납 가정을 끼우면 \(F_{2k+1} + F_{2k+2}\)가 남고, 이것이 정확히 피보나치 점화식의 좌변 꼴이므로 \(F_{2k+3}\)으로 접힌다.
풀이. [기초] \(n = 1\): 좌변 \(F_2 = 1\), 우변 \(F_3 - 1 = 2 - 1 = 1\) ✓. [귀납] \(F_2 + F_4 + \cdots + F_{2k} = F_{2k+1} - 1\)이라고 가정하자. 목표는 \(F_2 + \cdots + F_{2k+2} = F_{2k+3} - 1\)이다.
마지막 등호는 점화식 \(F_{n} = F_{n-1} + F_{n-2}\)를 \(n = 2k+3\)에 쓴 것이다. \(F_{2k+3} = F_{2(k+1)+1}\)이므로 목표 꼴과 일치한다. \(\blacksquare\)
복기. 검산: \(n = 3\)에서 좌변 \(F_2 + F_4 + F_6 = 1 + 3 + 8 = 12\), 우변 \(F_7 - 1 = 13 - 1 = 12\) ✓.
문제 12#
접근. 귀납 단계에서 \(k+1\)을 만드는 가장 간단한 길은 3원짜리를 한 장 더 얹는 것이므로, 참조하는 과거는 \(k+1-3 = k-2\) — 보폭이 3이다. 따라서 기초도 3개(\(12, 13, 14\)) 필요하다.
풀이. [기초] \(12 = 3 \cdot 4 + 7 \cdot 0\), \(13 = 3 \cdot 2 + 7 \cdot 1\), \(14 = 3 \cdot 0 + 7 \cdot 2\) ✓✓✓. [귀납] \(k \ge 14\)이고, \(12 \le j \le k\)인 모든 정수 \(j\)가 \(3a + 7b\) 꼴이라고 가정하자(강한 귀납 가정). 목표는 \(k+1\)도 그 꼴임을 보이는 것이다. \(k \ge 14\)에서 \(k + 1 \ge 15\)이므로 \(k - 2 = (k+1) - 3 \ge 12\)이고, 또 \(k - 2 \le k\)이므로 \(k-2\)는 강한 가정의 범위 안에 있다. 따라서 \(k - 2 = 3a + 7b\)인 음이 아닌 정수 \(a, b\)가 존재한다(강한 귀납 가정). 그러면
이고 \(a + 1 \ge 0\), \(b \ge 0\)이므로 \(k+1\)도 목표 꼴이다. \(\blacksquare\)
복기. 기초를 12 하나만 두면 \(k+1 = 13, 14\)에서 참조할 과거(\(10, 11\))가 무대 밖이라 근거가 없다 — 2관 오류다. 참고로 \(11 = 3 \cdot 7 - 3 - 7\)이 3원\(\cdot\)7원으로 만들 수 없는 마지막 금액인데, 이는 33주차 문제 19의 복기에 나온, 서로소인 \(m, n\)에 대한 프로베니우스 수 \(mn - m - n\)과 같은 꼴이다(3과 7은 서로소다. 그때는 \(4 \cdot 7 - 4 - 7 = 17\)이었고 4와 7도 서로소다). 서로소 조건을 빼면 거짓이다 — \(m = 4\), \(n = 6\)이면 공식값은 \(14\)지만 두 우표로는 홀수 금액을 아무리 큰 것이라도 만들 수 없어 “마지막 불가능 금액” 자체가 존재하지 않는다.
문제 13#
접근. 요약과 해부 두 부분으로 나뉜다. 해부에서 먼저 할 일은 “기초는 참이고 \(k \ge 2\)의 전달도 유효하다”를 인정하는 것이다. 무엇이 멀쩡한지 확정해야 무너진 한 곳을 정확히 지목할 수 있다.
풀이. 요약. 기초에서 \(n = 1\)을 확인한다(말 1마리는 자기 자신과 같은 색). 귀납 단계에서는 말 \(k+1\)마리를 앞 \(k\)마리 \(\{1, \dots, k\}\)와 뒤 \(k\)마리 \(\{2, \dots, k+1\}\)로 나누고, 각각 귀납 가정으로 단색이라 한 뒤, 두 무리가 공유하는 말을 다리 삼아 전체가 단색이라고 결론짓는다. 해부. 무너지는 지점은 \(k = 1\)이다. 이때 앞 무리는 \(\{1\}\), 뒤 무리는 \(\{2\}\)이고 공유 무리 \(\{2, \dots, k\}\)는 공집합이므로, 두 무리의 색을 이을 다리가 존재하지 않는다. 즉 이 논증은 \(k \ge 2\)에서만 작동하고 \(P(1) \Rightarrow P(2)\)라는 고리가 성립하지 않는다. 기초 \(P(1)\)은 참이며 \(P(2) \Rightarrow P(3) \Rightarrow \cdots\)도 전부 유효하지만, \(P(2)\)에 도달할 길이 없으므로 그 뒤 전부가 근거를 잃는다. 실제로 \(P(2)\)는 거짓이다.
복기. 채점의 세 지점: ① 기초와 \(k \ge 2\)의 전달이 유효함을 인정했는가 ② 무너지는 것이 \(P(1) \Rightarrow P(2)\) 한 고리임을 지목했는가 ③ 원인이 “겹침이 비는” 퇴화 상황임을 명시했는가. 이 역설을 “기초가 틀렸다”로 적으면 진단이 어긋난다.
문제 14#
접근. 34주차 문제 12의 백지 재현이다. 공약수 \(d\)를 잡고, 점화식의 차를 이용해 \(d\)를 한 칸 아래 피보나치 수의 약수로 내려보낸 뒤 귀납 가정을 쓴다. 필요한 부품은 “\(d \mid x\)이고 \(d \mid y\)이면 \(d \mid (x - y)\)”(2주차 문제 7)뿐이다.
풀이. 명제 \(P(n)\)을 “\(F_n\)과 \(F_{n+1}\)의 공약수는 \(\pm 1\)뿐이다”로 둔다. [기초] \(n = 1\): \(F_1 = F_2 = 1\)이고, \(1\)의 약수는 \(\pm 1\)뿐이므로 공약수도 \(\pm 1\)뿐이다 ✓. [귀납] \(F_k\)와 \(F_{k+1}\)의 공약수가 \(\pm 1\)뿐이라고 가정하자. \(d\)를 \(F_{k+1}\)과 \(F_{k+2}\)의 임의의 공약수라 하자. \(d \mid F_{k+2}\)이고 \(d \mid F_{k+1}\)이므로
이다(2주차 문제 7과 점화식 \(F_{k+2} = F_{k+1} + F_k\)). 따라서 \(d\)는 \(F_k\)와 \(F_{k+1}\)의 공약수이고, 귀납 가정에 의해 \(d = \pm 1\)이다. 곧 \(F_{k+1}\)과 \(F_{k+2}\)의 공약수도 \(\pm 1\)뿐이다. \(\blacksquare\)
복기. 점화식을 앞으로 밀지 않고 뒤로 감아 귀납 가정이 있는 자리로 내려온 것이 이 증명의 전부다. 이 명제의 \(P(n)\)은 \(F_n\)과 \(F_{n+1}\)을 한 문장으로 묶은 것이므로 \(P(k)\) 하나만 소비된다 — 두 칸 점화 수열인데도 기초가 \(n = 1\) 하나인 이유다(34주차 §1.5). 검산: \(F_5 = 5\), \(F_6 = 8\)의 공약수는 \(\pm 1\) ✓.
문제 15#
접근. 먼저 실험한다. \(n = 1\): \(3 > 2\) ✓, \(n = 2\): \(9 > 8\) ✓ — 처음부터 성립한다. 그다음 연결 부등식을 미리 계산해 유효 범위를 본다: \(3k \cdot 2^k \ge (k+1) 2^{k+1}\)은 양변을 \(2^k\)로 나누면 \(3k \ge 2(k+1)\), 곧 \(k \ge 2\)와 같다. 연결이 \(k \ge 2\)부터만 작동하므로 기초는 \(n = 1\)과 \(n = 2\) 두 개를 놓아야 한다.
풀이. [기초] \(n = 1\): \(3^1 = 3 > 1 \cdot 2^1 = 2\) ✓. \(n = 2\): \(3^2 = 9 > 2 \cdot 2^2 = 8\) ✓. [귀납] \(k \ge 2\)인 정수 \(k\)에 대해 \(3^k > k \cdot 2^k\)라고 가정하자. 목표는 \(3^{k+1} > (k+1) \cdot 2^{k+1}\)이다. ① \(3^{k+1} = 3 \cdot 3^k > 3k \cdot 2^k\) (귀납 가정; 양변에 양수 \(3\)을 곱했으므로 (W3)). ② 연결 부등식: \(k \ge 2\)이면 \(3k - 2(k+1) = k - 2 \ge 0\)이므로 \(3k \ge 2(k+1)\)이고, 양변에 양수 \(2^k\)를 곱하면
③ ①과 ②를 추이성((W6))으로 이으면 \(3^{k+1} > (k+1) \cdot 2^{k+1}\)이다. \(\blacksquare\)
복기. 기초가 2개인 이유는 보폭 때문이 아니다 — 보폭은 1칸이다. 이유는 **연결 부등식의 유효 범위가 \(k \ge 2\)**라는 것이고, 그래서 \(P(2)\)는 전달로 얻을 수 없어 직접 확인해야 한다. 기초 개수는 “보폭”과 “연결부의 요구 조건” 두 곳에서 온다.
문제 16#
접근. 최소 반례법의 뼈대는 정해져 있다 — 반례가 있다고 가정하고, 최소원리로 최소 반례 \(m\)을 잡고, 가장 작은 값에서 \(m\)을 배제한 뒤, \(m - 1\)이 반례가 아니라는 사실로부터 \(m\)도 반례가 아님을 끌어내 모순을 만든다. 필요한 관계식은 \(m^2 + m\)과 \((m-1)^2 + (m-1)\)의 차다.
풀이. 모순을 위해 반례가 존재한다고 가정하자. 반례가 되는 자연수를 모두 모은 집합 \(S\)는 공집합이 아닌 자연수의 부분집합이므로, 최소원리에 의해 최소원소 \(m = \min S\)가 존재한다. \(1^2 + 1 = 2\)는 짝수이므로 \(1 \notin S\)이고, 따라서 \(m \ge 2\)이다. 그러면 \(m - 1\)은 자연수이면서 \(m\)보다 작으므로 \(m - 1 \notin S\), 곧 \((m-1)^2 + (m-1)\)은 짝수다. 한편
이다(전개 확인: \((m-1)^2 + (m-1) + 2m = m^2 - 2m + 1 + m - 1 + 2m = m^2 + m\) ✓). 우변은 짝수와 짝수의 합이므로 짝수이고(2주차 예제 2.2), 따라서 \(m^2 + m\)도 짝수다. 이는 \(m \in S\), 곧 \(m\)이 반례라는 것과 모순이다. 그러므로 반례는 존재하지 않는다. \(\blacksquare\)
복기. 같은 명제의 세 번째 증명이다 — 1주차 문제 16은 연속한 두 정수의 곱으로, 17주차 §3 훈련 1은 \(n\)의 홀짝 케이스로, 이번은 최소원리로 증명했다. 기법이 달라도 뼈대는 같지만, 무대는 같지 않다 — 최소원리는 자연수(음이 아닌 정수)의 부분집합에만 쓸 수 있으므로 이번 증명이 덮는 것은 자연수 \(n\)뿐인 반면, 앞의 두 증명은 모든 정수를 덮는다. 음의 정수까지 넓히려면 \(n \le -1\)에서 \(m = -(n+1) \ge 0\)으로 옮겨 \(n^2 + n = m^2 + m\)임을 확인하거나, 1주차 문제 16의 연속 곱 논증을 그대로 인용해야 한다.
문제 17#
접근. 결함은 두 개다. 하나는 기초를 \(n = 2\)로 옮겨 놓고 명제의 범위는 \(n \ge 1\)인 채로 둔 것이고, 다른 하나는 연결 부등식을 “크니까”로 넘어간 것(4관)이다. 둘 다 지적하고, 4관 쪽은 실제로 증명해 메워야 수정이 끝난다.
풀이. 결함 ① — 기초 이동의 뒤처리 누락. \(n = 1\)에서 \(4^1 = 4\)이고 \(1^2 + 3 = 4\)이므로 등호이고, 원명제의 부등호는 \(>\)이므로 \(P(1)\)은 거짓이다. 답안은 \(P(1)\)이 거짓임을 알아차렸지만 거기서 멈췄다 — 기초를 옮겼으면 명제의 주장 범위도 함께 옮겨야 한다. 명제 자체를 “\(n \ge 2\)인 모든 자연수에 대해 \(4^n > n^2 + 3\)”으로 고쳐 선언해야 한다. 그러지 않으면 증명이 확보하는 범위(\(n \ge 2\))와 명제가 주장하는 범위(\(n \ge 1\))가 어긋난 채로 남는다. 결함 ② — 4관(연결 부등식 생략). “\(4(k^2+3)\)은 \((k+1)^2 + 3\)보다 크니까”는 증명이 아니라 주장이다. 차를 계산해 메운다.
\(k \ge 1\)이면 \(3k^2 \ge 3k \ge 2k\)이므로 \(3k^2 - 2k \ge 0\)이고, 따라서 \(3k^2 - 2k + 8 \ge 8 > 0\)이다. (완전제곱으로 처리해도 된다: \(3k^2 - 2k + 8 = 3\left(k - \tfrac13\right)^2 + \tfrac{23}{3} > 0\).) 곧 \(4(k^2+3) > (k+1)^2 + 3\)이다. 수정된 증명. [기초] 새 명제의 무대가 \(n \ge 2\)이므로 기초는 \(n = 2\)다: \(4^2 = 16\)이고 \(2^2 + 3 = 7\)이며 \(16 > 7\) ✓. (원답안이 적은 “\(n = 2\): \(16 > 7\)”은 \(n \ge 1\) 명제의 기초로 잘못 붙어 있던 줄인데, 명제를 \(n \ge 2\)로 고쳐 선언하고 나면 그 줄이 제자리를 찾아 그대로 재사용된다.) [귀납] \(k \ge 2\)에서 \(4^k > k^2 + 3\)을 가정하면, \(4^{k+1} = 4 \cdot 4^k > 4(k^2 + 3)\) (귀납 가정, (W3))이고 위 연결 부등식에 의해 \(4(k^2+3) > (k+1)^2 + 3\)이므로, 추이성((W6))으로 \(4^{k+1} > (k+1)^2 + 3\)이다. \(\blacksquare\)
복기. 4관 오류라고 해서 연결 부등식이 거짓인 것은 아니다 — 여기서는 모든 \(k \ge 1\)에서 참이었다. 결함은 참\(\cdot\)거짓이 아니라 확인하지 않았다는 것이다.
문제 18#
접근. 몸통을 한 줄씩 따라가며 “(귀납 가정)”이 소비되는 자리를 찾는다. 찾을 수 없다면 그 답안은 귀납의 껍데기 안에 직접 증명을 넣은 것이다(5관). 22주차 §1.7 기법 선택 가이드 ④의 귀납판이다.
풀이. 논리적 오류는 없다. 각 문장은 참이고 결론도 참이다. (다만 “\(k\) 홀짝 케이스와 mod 3 케이스로”는 예고만 하고 한 경우도 다루지 않은 빈 구절이다 — 실제로 쓰인 근거는 30주차 문제 17이고, 케이스 분석은 필요조차 없다. 참인 문장들 사이에 낀 이런 빈 구절도 지적 대상이다.) 그런데도 나쁜 답안인 이유는 **5관(귀납 가정 미사용)**이다. 가정 “\(6 \mid (k^3 + 5k)\)”가 본문 어디에서도 쓰이지 않았고, 실제로 사용된 논증 — \(n^3 + 5n = (n^3 - n) + 6n\)이고 \(6 \mid (n^3 - n)\)(30주차 문제 17), \(6 \mid 6n\)이므로 합도 6의 배수 — 은 임의의 자연수 \(n\)에 대해 그대로 성립하는 직접 증명이다. 답안은 그 직접 증명을 \(k\)에 한 번, \(k+1\)에 한 번 반복했을 뿐이며, 귀납의 틀은 아무 일도 하지 않는다. 수정 (직접 증명으로). “임의의 자연수 \(n\)에 대해 \(n^3 + 5n = (n^3 - n) + 6n\)이다. \(6 \mid (n^3 - n)\)이고(30주차 문제 17) \(6 \mid 6n\)이므로, 배수의 합도 배수여서(2주차 예제 2.2) \(6 \mid (n^3 + 5n)\)이다. \(\blacksquare\)” — 세 줄로 끝난다.
복기. 굳이 귀납으로 쓰고 싶다면 귀납 가정이 실제로 소비되도록 식을 배치하면 된다: \((k+1)^3 + 5(k+1) = (k^3 + 5k) + 3k^2 + 3k + 6 = (k^3 + 5k) + 3k(k+1) + 6\)에서 첫 항은 귀납 가정으로 6의 배수, \(3k(k+1)\)은 \(k(k+1)\)이 짝수이므로(1주차 문제 16) 6의 배수, \(6\)도 6의 배수다. 이렇게 쓰면 “(귀납 가정)” 표시가 실제 근거가 된다.
문제 19#
접근. \((k+1)^3 + 2(k+1)\)을 전개한 뒤, 귀납 가정의 식 \(k^3 + 2k\)가 통째로 드러나도록 재배열한다. 남는 항이 3의 배수임을 보이면 끝난다.
풀이. [기초] \(n = 1\): \(1^3 + 2 \cdot 1 = 3\)이고 \(3 \mid 3\) ✓. [귀납] \(3 \mid (k^3 + 2k)\)라고 가정하자. 목표는 \(3 \mid \big((k+1)^3 + 2(k+1)\big)\)이다.
첫 항은 귀납 가정에 의해 3의 배수이고, 둘째 항은 \(k^2 + k + 1\)이 정수이므로 그 자체로 3의 배수다. 배수의 합도 배수이므로(2주차 예제 2.2) \(3 \mid \big((k+1)^3 + 2(k+1)\big)\)이다. \(\blacksquare\)
복기. 검산: \(n = 2\)에서 \(8 + 4 = 12 = 3 \cdot 4\) ✓, \(n = 3\)에서 \(27 + 6 = 33 = 3 \cdot 11\) ✓. \(n^3 + 2n = n(n^2 + 2)\)를 \(n\)의 나머지 세 경우로 갈라 증명할 수도 있다(17주차 §3 훈련 1의 방식) — 기법 선택은 늘 복수다.
문제 20#
접근. 박물관 5관을 그대로 다섯 문항으로 옮기되, 남의 표현이 아니라 답안을 검사할 때 실제로 던질 질문 꼴로 적는다. 그리고 이번 시험에서 걸린 자리를 관 번호로 기록해 둔다.
풀이. (예시 답안) ① 기초를 실제로 계산했는가 — 좌변과 우변을 각각 계산해 비교했는가? ② 귀납 단계가 소비하는 가정이 몇 개인지 세고(첨자에 \(F_{k-1}\)이 보이는 것과 \(P(k-1)\)을 가정으로 쓰는 것은 다르다 — 34주차 §1.5), 그 수만큼(그리고 연결부의 유효 범위가 요구하는 만큼) 기초를 놓았는가 — 또 그 과거가 선언한 가정 안에 들어 있는가(\(P(k)\)만 가정하고 \(P(k-1)\)을 쓰지 않았는가)? ③ 전달 논증이 가장 작은 \(k\)에서도 작동하는가 — 겹침\(\cdot\)항\(\cdot\)분모가 비거나 사라지지 않는가? ④ (부등식) 귀납 가정이 데려다준 중간값에서 목표까지의 연결 부등식을 별도로 증명했는가? ⑤ “(귀납 가정)” 표시가 본문에 실제로 있는가 — 없다면 직접 증명으로 다시 쓸 것.
복기. 기록 예시: “15번에서 기초를 1개만 두려다 연결부의 \(k \ge 2\) 조건에 걸렸다 — 2관과 4관의 복합.” 이렇게 관 번호로 적어 두면 다음 복습에서 어느 주차로 돌아갈지가 바로 정해진다.
채점 가이드와 7부 수료#
수료 기준: 1번(원리 진술)을 만점으로 쓰고, 증명 문항(2~4, 7~12, 14~16, 19) 중 9개 이상을 서식\(\cdot\)논리 무결로, 진단(13, 17, 18) 중 2개 이상을 정확히 짚었으면 7부 수료로 보고 36주차로 넘어간다.
부등식(8, 15)에서 연결부 누락이 반복되면 32주차를 재복습한다.
기초 개수를 잘못 잡았다면(12, 15) 33주차 문제 17을 재복습한다. 보통 귀납으로 선언해 놓고 \(P(k-1)\)을 쓴 줄이 나왔다면 34주차 문제 17을 재복습한다 — 그 답안은 기초를 하나 더 놓아도 선언이 보통 귀납인 한 \(P(k-1)\)을 쓸 권리가 없다(33주차 §1.4).
13번(말 역설)을 “기초가 틀렸다”로 진단했다면 §1.2를 다시 읽는다 — 이 역설의 기초는 참이다.
7부까지의 지도. 직접\(\cdot\)케이스\(\cdot\)대우\(\cdot\)귀류에 귀납까지, 증명의 다섯 기법이 모두 갖추어졌다. 남은 것은 기법이 아니라 대상이다: 관계(36~39주), 함수(40~44주), 극한(45~47주), 무한(48~49주) — 대학 수학이 실제로 다루는 무대들이다.
다음 주 예고: 8부 개막 — 관계(relation). “\(x < y\)”, “\(a \equiv b\)”, “\(A \subseteq B\)”처럼 두 대상 사이의 관계를 집합(데카르트 곱의 부분집합)으로 정의하고, 반사\(\cdot\)대칭\(\cdot\)추이라는 세 성질로 분류한다. 20주차에서 합동이 등호처럼 굴던 이유가 여기서 이름을 얻는다.