32주차 · 강의 — 예제 · 연습 · 해설#
예제 — 두 종류의 귀납 단계를 함께 만들기#
완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 설계부터 스스로 한다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.
예제 2.1 — \(2^n \ge n^2\) (\(n \ge 4\))#
명제. \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(2^n \ge n^2\)이다.
29주차 문제 8(b)에서 실험으로 범위만 제안하고 남겨 둔 명제다. 이번 주에 갚는다.
설계 — 쓰기 전에 정하는 네 칸. 귀납 증명은 증명이 두 개이므로 번역표도 네 칸이다 — 무대, 기초 단계에서 확인할 것, 귀납 단계의 출발점, 귀납 단계의 도착점.
말 |
수식 번역 |
|
|---|---|---|
무대 |
\(n \ge 4\)인 모든 정수 |
일반화된 귀납 원리, \(n_0 = 4\) |
기초 단계 |
\(P(4)\)를 직접 확인 |
\(2^4 \ge 4^2\) |
귀납 단계의 출발점 |
\(k \ge 4\)에서 \(P(k)\)를 가정 |
\(2^k \ge k^2\) |
귀납 단계의 도착점 |
\(P(k+1)\)을 만든다 |
\(2^{k+1} \ge \underline{\quad(?)\quad}\) |
확인 10. 도착점 칸의 빈칸을 채워 보자. \(P(n)\)이 “\(2^n \ge n^2\)”일 때 \(P(k+1)\)은 어떤 부등식인가.
답
\(2^{k+1} \ge (k+1)^2\). \(P(n)\)의 \(n\) 자리에 \(k+1\)을 양쪽 모두 대입한다.
왼쪽만 바꾸어 \(2^{k+1} \ge k^2\)을 도착점으로 적는 경우가 있는데, 그것은
증명해야 할 명제가 아니다 — 도착점을 잘못 적으면 그다음 계산은 전부 헛돈다.
1단계 — 기초 단계. 출발점 \(n_0 = 4\)에서 명제를 직접 확인한다. \(2^4 = 16\)이고 \(4^2 = 16\)이므로 \(16 \ge 16\) ✓. 등호이지만 부등호가 \(\ge\)이므로 성립한다. (\(n_0\)이 4인 이유는 §1.4의 실험 표에 있다 — \(n = 3\)에서 \(8 < 9\)로 한 번 끊긴다.)
2단계 — 귀납 가정 선언. 31주차 서식대로 가정을 선언하고 목표를 미리 적는다.
확인 11. 둘째 문장을 완성해 보자: “\(k \ge \underline{\quad}\)인 정수 \(k\)에 대해 \(\underline{\qquad}\)이라 가정하자. 목표는 \(\underline{\qquad}\)이다.”
답
“\(k \ge 4\)인 정수 \(k\)에 대해 \(2^k \ge k^2\)이라 가정하자. 목표는
\(2^{k+1} \ge (k+1)^2\)이다.”
\(k \ge 4\)를 명시하는 것이 중요하다 — 이 조건이 4단계(연결 부등식)에서 실제로 소비된다.
목표를 미리 적어 두면 계산이 어디로 가야 하는지가 시야에 고정된다.
3단계 — ① 변형과 ② 귀납 가정 투입. 2단 구조의 전반부다. \(2^{k+1}\) 안에 \(2^k\)가 보이도록 쪼갠 뒤 가정을 끼운다.
확인 12. 셋째 문장을 완성해 보자: “\(2^{k+1} = \underline{\quad} \cdot 2^k \ge \underline{\quad}\) (귀납 가정).” 부등호의 근거는 (W1)~(W6) 중 무엇인가.
답
“\(2^{k+1} = 2 \cdot 2^k \ge 2k^2\) (귀납 가정).”
근거는 (W3)이다 — \(2^k \ge k^2\)의 양변에 양수 \(2\)를 곱해도 부등호 방향이
유지된다. 곱하는 수가 양수라는 점을 확인하지 않으면 (W3)의 뒷부분(음수를
곱하면 방향이 뒤집힌다)에 걸린다.
4단계 — ③ 연결 부등식. 손에 있는 것은 \(2k^2\), 목표는 \((k+1)^2\)이다. 둘 사이의 부등식을 별도로 증명한다. 16주차의 표준 수법은 차를 계산해 부호를 판정하는 것이다.
확인 13. 연결 부등식으로 무엇을 증명해야 하는가. 그리고 차 \(2k^2 - (k+1)^2\)을 전개해 정리해 보자.
답
증명할 것은 \(2k^2 \ge (k+1)^2\)이다.
\(2k^2 - (k+1)^2 = 2k^2 - (k^2 + 2k + 1) = k^2 - 2k - 1 = (k^2 - 2k + 1) - 2 = (k-1)^2 - 2\).
\(-1\)을 \(+1 - 2\)로 쪼개 완전제곱을 만든 것이다 — 차를 제곱 꼴로 만들면
(W1)로 부호를 판정할 수 있다.
확인 14. \((k-1)^2 - 2 > 0\)을 보이려면 \(k\)에 어떤 조건이 필요한가. 가정 \(k \ge 4\)가 소비되는 지점이 정확히 어디인지 짚어 보자.
답
\(k \ge 4\)이면 \(k - 1 \ge 3\)이다. 여기서 두 경우로 나눈다 — \(k = 4\)이면
\((k-1)^2 = 9\)로 등호이고, \(k \ge 5\)이면 \(0 \le 3 < k - 1\)이므로 16주차 문제 11에
의해 \(9 < (k-1)^2\)이다. 어느 쪽이든 \((k-1)^2 \ge 9\)이다.
\(9 > 2\)이므로 \((k-1)^2 - 2 \ge 7 > 0\).
가정 \(k \ge 4\)가 소비되는 곳은 바로 이 줄이다 — 증명 전체에서 \(k \ge 4\)가
쓰이는 자리는 여기 한 곳뿐이다.
참고로 \((k-1)^2 > 2\)는 \(k - 1 \ge 2\), 곧 \(k \ge 3\)부터 참이다. 연결부가 요구하는
범위(\(k \ge 3\))가 \(n_0 = 4\)보다 넓으므로 확인 5(가)의 상황이고, 어긋남이 없다.
5단계 — 이어 붙이고 마감한다. 두 부등호를 추이성으로 잇고 원리를 인용한다.
확인 15. 마지막 두 문장을 완성해 보자: “따라서 \(2^{k+1} \ge \underline{\quad} \ge \underline{\qquad}\)이다. \(\underline{\qquad}\)에 의해 \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(2^n \ge n^2\)이다. \(\blacksquare\)”
답
“따라서 \(2^{k+1} \ge 2k^2 \ge (k+1)^2\)이다. 일반화된 귀납 원리에 의해
\(n \ge 4\)인 모든 정수 \(n\)에 대해 \(2^n \ge n^2\)이다. \(\blacksquare\)”
두 부등호를 잇는 근거는 (W6) 추이성이다. 마지막 문장에서 인용할 원리는
31주차의 원리가 아니라 \(n_0\)이 있는 §1.4의 원리다.
완성본. 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
귀납법으로 증명한다. [기초] \(n = 4\)일 때 \(2^4 = 16\)이고 \(4^2 = 16\)이므로 \(2^4 \ge 4^2\) ✓. |
출발점 \(n_0 = 4\)는 §1.4의 실험 결과다 — \(n = 3\)에서 \(8 < 9\)로 끊기므로 3 이하는 무대에서 제외된다. |
[귀납] \(k \ge 4\)인 정수 \(k\)에 대해 \(2^k \ge k^2\)이라 가정하자. 목표는 \(2^{k+1} \ge (k+1)^2\)이다. |
가정 선언(31주차 서식) + 도착점 명시. \(k \ge 4\)를 함께 적어 두어야 4단계에서 쓸 수 있다. |
\(2^{k+1} = 2 \cdot 2^k \ge 2k^2\) (귀납 가정). |
① \(2^k\)가 보이도록 변형 \(\to\) ② 귀납 가정 투입. 부등호의 근거는 (W3), 양변에 양수 2를 곱했다. |
연결 부등식: \(2k^2 \ge (k+1)^2\)을 보인다. 차는 \(2k^2 - (k+1)^2 = k^2 - 2k - 1 = (k-1)^2 - 2\)이고, \(k \ge 4\)이면 \(k - 1 \ge 3\)이므로 \((k-1)^2 \ge 9 > 2\)이고(\(k = 4\)는 등호, \(k \ge 5\)는 16주차 문제 11), 차는 양수다. |
③ — 귀납이 아니라 16주차의 차\(\cdot\)완전제곱 수법과 제곱 비교(16주차 문제 11)다. \(k \ge 4\) 가정이 소비되는 지점이 바로 이 줄이다. |
따라서 \(2^{k+1} \ge 2k^2 \ge (k+1)^2\)이다. 일반화된 귀납 원리에 의해 \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(2^n \ge n^2\)이다. \(\blacksquare\) |
두 부등호를 (W6) 추이성으로 잇고, \(n_0\)이 있는 원리를 인용해 마감한다. |
대입 시뮬레이션. 완성본의 \(k\)에 4를 넣어 읽어 보자.
확인 16. \(k = 4\)일 때 셋째 줄과 다섯째 줄은 각각 어떤 수의 부등식이 되는가. 등호가 나타나는 자리가 있는지도 확인해 보자.
답
셋째 줄은 \(2^5 = 32 \ge 2 \cdot 4^2 = 32\)(등호), 다섯째 줄은 \(32 \ge 32 \ge 25\)이다.
등호가 한 번 나타나지만 부등호가 \(\ge\)이므로 모든 줄이 그대로 성립한다.
\(k = 5\)로 바꾸면 \(64 \ge 50 \ge 36\)으로 여유가 벌어진다. 어느 정수 \(k \ge 4\)를
넣어도 다섯 줄이 작동한다 — 증명이 \(k\)에 대해 쓴 것은 “\(k \ge 4\)인 정수”라는
자격뿐이기 때문이다.
[주의] 자주 하는 실수: 연결 부등식의 방향. 연결부에서 \(2k^2 \le (k+1)^2\)을 증명하는 경우가 있다. 계산은 옳을 수 있지만, 그 부등식으로는 \(2^{k+1} \ge 2k^2\)과 이어 붙일 수 없다(확인 3). 연결 부등식의 방향은 귀납 가정이 만든 부등호와 같은 방향이어야 한다. 세울 때 “중간값 \(\ge\) 목표”인지 소리 내어 확인한다.
예제 2.2 — 나누어떨어짐 귀납: \(6 \mid (n^3 - n)\)#
명제. 모든 자연수 \(n\)에 대해 \(6 \mid (n^3 - n)\)이다.
30주차 문제 17에서 이미 증명한 명제다. 그때는 기성 부품 세 개(17주차 문제 7, 17주차 예제 2.1, 20주차 문제 13)를 조립했다. 이번에는 귀납으로 다시 증명한다 — 같은 정리의 두 번째 증명이다.
이번에는 설계만 함께 하고, 증명은 완성된 산문으로 본다.
확인 17. 번역표를 채워 보자. 기초 단계에서 확인할 것은 무엇이고, 귀납 단계의 출발점과 도착점은 각각 어떤 문장인가.
답
기초 단계: \(n = 1\)에서 \(1^3 - 1 = 0\)이고 \(6 \mid 0\)임을 확인한다
(\(0 = 6 \times 0\)이고 \(0\)은 정수이므로 참이다 — 2주차 §1.5의 판정).
출발점: \(6 \mid (k^3 - k)\), 곧 정의 2.1에 의해 \(k^3 - k = 6m\)인 정수 \(m\)이 존재한다.
도착점: \((k+1)^3 - (k+1) = 6 \times (\text{정수})\) 꼴을 만든다.
확인 18. ① 걸음을 수행해 보자. \((k+1)^3 - (k+1)\)을 전개한 뒤 \(k^3 - k\)를 떼어 내면 무엇이 남는가.
답
\((k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k\)이고,
남은 것은 \(3k^2 + 3k = 3k(k+1)\)이다.
잔여를 \(3k(k+1)\)로 묶어 두는 것이 요령이다. \(3k^2 + 3k\) 그대로 두면 6의
배수인지 판정하기 어렵지만, \(3 \times k(k+1)\)로 묶으면 “\(k(k+1)\)이 짝수인가”
하나만 물으면 된다.
증명. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(1^3 - 1 = 0\)이고 \(0 = 6 \times 0\)이므로 \(6 \mid 0\) ✓. [귀납] 자연수 \(k\)에 대해 \(6 \mid (k^3 - k)\)라 가정하자. 목표는 \(6 \mid \big((k+1)^3 - (k+1)\big)\)이다. 전개해 재배열하면
이다. 첫 항 \(k^3 - k\)는 귀납 가정에 의해 6의 배수다. 둘째 항에서 \(k(k+1)\)은 연속한 두 정수의 곱이므로 짝수이고(1주차 문제 16), 따라서 \(k(k+1) = 2m\)인 정수 \(m\)이 존재해 \(3k(k+1) = 3 \cdot 2m = 6m\) — 6의 배수다. 6의 배수 두 개의 합은 6의 배수이므로(2주차 예제 2.2) \(6 \mid \big((k+1)^3 - (k+1)\big)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(6 \mid (n^3 - n)\)이다. \(\blacksquare\)
(검산: \(k = 2\)에서 좌변 \(27 - 3 = 24\), 우변 \((8-2) + 3 \cdot 2 \cdot 3 = 6 + 18 = 24\) ✓.)
두 증명의 비교. 30주차의 조립 증명은 기성 부품 세 개를 인용해 세 줄로 끝났다. 이번 귀납 증명은 부품을 두 개(1주차 문제 16, 2주차 예제 2.2)만 쓰고 나머지는 자체 전개로 채웠다. 어느 쪽이 짧은지는 손에 어떤 부품이 있느냐에 달렸다 — 부품이 갖춰져 있으면 조립이 짧고, 없으면 귀납이 자급자족한다. 같은 정리에 성격이 다른 증명이 공존하는 사례이고, 이 비교를 문제 19에서 정리한다.
예제 2.3 — 팩토리얼 부등식: \(n! > 2^n\) (\(n \ge 4\))#
명제. \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(n! > 2^n\)이다.
이번에는 설계부터 스스로 한다. 연필로 다음을 먼저 수행한 뒤 아래와 대조한다: ① \(n_0\)을 실험으로 정한다 ② 귀납 단계의 세 걸음(①②③)을 각각 적는다.
확인 19. (가) \(n = 1, 2, 3, 4\)에서 \(n!\)과 \(2^n\)을 비교해 \(n_0\)을 정해 보자. (나) ① 변형, ② 귀납 가정 투입 후 중간값, ③ 연결 부등식을 각각 적어 보자.
답
(가) \(n = 1\): \(1 < 2\) ✗. \(n = 2\): \(2 < 4\) ✗. \(n = 3\): \(6 < 8\) ✗.
\(n = 4\): \(24 > 16\) ✓. 따라서 \(n_0 = 4\)이다.
(나) ① \((k+1)! = (k+1) \cdot k!\) ② \((k+1) \cdot k! > (k+1) \cdot 2^k\)
③ \((k+1) \cdot 2^k \ge 2 \cdot 2^k = 2^{k+1}\), 곧 \(k + 1 \ge 2\).
③의 근거: \(k \ge 4\)이므로 \(k + 1 \ge 5 > 2\)이고, 양변에 양수 \(2^k\)를 곱해도
방향이 유지된다(W3).
증명. 귀납법으로 증명한다. [기초] \(n = 4\)일 때 \(4! = 24\)이고 \(2^4 = 16\)이므로 \(24 > 16\) ✓. [귀납] \(k \ge 4\)인 정수 \(k\)에 대해 \(k! > 2^k\)이라 가정하자. 목표는 \((k+1)! > 2^{k+1}\)이다. \(k + 1 > 0\)이므로 귀납 가정의 양변에 \(k+1\)을 곱해도 부등호 방향이 유지되고(W3),
이다. 마지막 부등호의 근거는 연결 부등식 \(k + 1 \ge 2\)이다 — \(k \ge 4\)이므로 \(k + 1 \ge 5 \ge 2\)이고, 양변에 양수 \(2^k\)를 곱했다(W3). 두 부등호를 추이성으로 이으면(W6) \((k+1)! > 2^{k+1}\)이다. 일반화된 귀납 원리에 의해 \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(n! > 2^n\)이다. \(\blacksquare\)
(검산: \(n = 5\)에서 \(120 > 32\) ✓. \(n = 6\)에서 \(720 > 64\) ✓ — 여유가 빠르게 벌어진다.)
이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다.
연결부의 난이도. 예제 2.1의 연결 부등식은 차를 계산하고 완전제곱을 만들어야 했지만, 여기서는 \(k + 1 \ge 2\) 한 줄이다. 난이도는 문제마다 다르다. 그러나 존재 자체는 매번 확인해야 한다 — 한 줄짜리 연결부를 적지 않고 넘어가면, 그 자리가 실제로 한 줄로 끝나는지 아무도 알 수 없다.
관찰 — 두 소재의 같은 뼈대#
예제 2.1은 부등식, 예제 2.2는 나누어떨어짐이었다. 귀납 단계의 걸음이 실제로 대응하는지 표를 채워 확인해 보자.
걸음 |
예제 2.1 (부등식) |
예제 2.2 (나누어떨어짐) |
|---|---|---|
① \(k+1\)의 식에 \(k\)의 식을 드러낸다 |
\(2^{k+1} = 2 \cdot 2^k\) |
\(\underline{\quad(1)\quad}\) |
② 귀납 가정을 투입한다 |
\(2 \cdot 2^k \ge 2k^2\) |
\(\underline{\quad(2)\quad}\) |
③ 남은 것을 별도로 처리한다 |
연결 부등식 \(2k^2 \ge (k+1)^2\) |
\(\underline{\quad(3)\quad}\) |
확인 20. 대응표의 빈칸 (1)(2)(3)을 예제 2.2의 증명에서 찾아 채워 보자.
답
(1) \((k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)\) — \(k\)의 식 \(k^3 - k\)가 드러나도록 재배열.
(2) “첫 항 \(k^3 - k\)는 귀납 가정에 의해 6의 배수다.”
(3) “\(3k(k+1)\)이 6의 배수임을 1주차 문제 16으로 별도 증명한다.”
세 걸음이 정확히 대응한다. 소재가 바뀌면 ③에서 하는 일의 종류가
바뀔 뿐(부등식 증명 \(\leftrightarrow\) 잔여의 배수 판정), 자리와 임무는 같다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
귀납 단계의 세 걸음
① \(k+1\)의 식을 \(k\)의 식이 드러나도록 변형한다 \(\to\) ② 귀납 가정을 투입하고 그 줄에 표시를 단다 \(\to\) ③ 남은 것(부등식이면 연결 부등식, 나누어떨어짐이면 잔여)을 별도로 처리한다.
이 세 걸음은 33주차의 강한 귀납법에서도 그대로 쓴다. 달라지는 것은 ②에서 꺼내 쓸 수 있는 가정의 크기뿐이다.
빈칸 사다리 — 지지대를 하나씩 빼며#
필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.
훈련 1 ●○○ — 수식 빈칸#
명제. 모든 자연수 \(n\)에 대해 \(5 \mid (6^n - 1)\)이다.
증명. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(6 - 1 = 5\)이고 \(5 = 5 \times 1\)이므로 \(5 \mid 5\) ✓. [귀납] \(5 \mid (6^k - 1)\)이라 가정하자. 그러면
이다. 첫 항 \(6(6^k - 1)\)은 귀납 가정과 \(\underline{\quad(2)\quad}\)(2주차 훈련 1)에 의해 5의 배수이고, \(\underline{\quad(1)\quad}\)도 5의 배수이므로, 두 5의 배수의 합인 \(6^{k+1} - 1\)도 5의 배수이다(\(\underline{\quad(3)\quad}\)). 따라서 \(5 \mid (6^{k+1} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(5 \mid (6^n - 1)\)이다. \(\blacksquare\)
(검산: \(6(6^k - 1) + 5 = 6^{k+1} - 6 + 5 = 6^{k+1} - 1\) ✓ — 빼고 더하기가 맞는지 역전개로 확인하는 습관을 붙인다.)
훈련 2 ●●○ — 수식과 근거를 함께#
이번에는 구조 낱말과 근거 문장도 빈칸이다.
명제. 모든 자연수 \(n\)에 대해 \(2^n \ge n + 1\)이다.
증명. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(2^1 = 2\)이고 \(1 + 1 = 2\)이므로 \(2 \ge 2\) ✓. [귀납] \(k \ge 1\)인 자연수 \(k\)에 대해 \(2^k \ge k + 1\)이라 \(\underline{\quad(1)\quad}\)하자. 목표는 \(2^{k+1} \ge (k+1) + 1\)이다. 그러면
이고, 이 부등호의 근거는 \(\underline{\quad(3)\quad}\)이다. 연결 부등식으로 \(2k + 2 \ge k + 2\)를 보인다: 차를 계산하면 \((2k+2) - (k+2) = \underline{\quad(4)\quad}\)이고, \(k \ge 1\)이므로 \(\underline{\quad(5)\quad}\)이다. 따라서 \(\underline{\quad(6)\quad}\)에 의해 \(2^{k+1} \ge k + 2 = (k+1) + 1\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(2^n \ge n + 1\)이다. \(\blacksquare\)
훈련 3 ●●● — 뼈대만 남기고#
이번에는 세 걸음의 각 칸을 통째로 채운다.
명제. 모든 자연수 \(n\)에 대해 \(9 \mid (10^n - 1)\)이다.
증명의 뼈대.
[기초]: \(\underline{\quad(1)\quad}\)
[귀납] ① 재배열: \(\underline{\quad(2)\quad}\)
[귀납] ②③ 잔여 처리와 마무리: \(\underline{\quad(3)\quad}\)
(이 훈련이 문제 18의 예행연습이다. 문제 18은 곱해지는 수가 100이고 잔여가 음수로 나오는 판이라 한 걸음 더 간다.)
연습문제 (20문항)#
해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 부등식 귀납 문제는 반드시 예제 2.1의 번역표(무대 / 기초 / 출발점 / 도착점)부터 채우고 시작한다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. “\(2^{k+1} \ge 2k^2\)이므로 \(2^{k+1} \ge (k+1)^2\)이다”는
0점이고, 연결 부등식 \(2k^2 \ge (k+1)^2\)을 별도로 증명한 답안이 만점이다.
모든 귀납 답안에 [기초]/[귀납] 표기와 “(귀납 가정)” 사용 지점 표시를 단다
(31주차 서식). 부등식 귀납은 연결 부등식을 별도 줄로 표시하고, 그것이
요구하는 \(k\)의 범위가 기초 단계의 \(n_0\)과 맞물리는지 한 줄로 확인한다.
난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. 실험으로 기초 단계의 위치를 찾으시오 (증명 불필요). (a) \(2^n > n^2\) (등호 없는 부등식이다)은 어느 \(n\)부터 계속 성립하는가? (\(n = 1, \dots, 6\) 실험) (b) \(n! > 3^n\)은? (\(n = 1, \dots, 7\) 실험)
힌트
표를 만들어 좌변과 우변을 각각 계산한 뒤 ✓/✗를 적는다. §1.4의 표가 양식이다.
“계속 성립하기 시작하는 첫 지점”을 묻고 있으므로, 도중에 한 번 ✗가 나오면
그 앞의 ✓들은 고립된 성립으로 보고 지나간다.
2. [백지] 부등식 귀납의 2단 구조(①②③)와 “연결 부등식” 개념을 쓰시오.
힌트
①은 무엇을 드러내기 위한 변형인가, ②는 어느 줄에 표시를 다는가,
③은 어떤 근거로 증명하는가 — 세 물음에 각각 한 줄씩 답하면 된다.
3. 모든 자연수 \(n\)에 대해 \(3^n \ge 2n + 1\)임을 증명하시오.
힌트
① \(3^{k+1} = 3 \cdot 3^k\). ② 귀납 가정을 넣으면 중간값은 \(3(2k+1) = 6k+3\).
③ 목표는 \(2(k+1) + 1 = 2k + 3\)이다 — \(6k + 3\)과 \(2k + 3\)의 차를 계산해 보자.
4. 빈칸 훈련(\(5 \mid 6^n - 1\))을 백지에서 완성하시오.
힌트
막히는 자리는 대개 재배열 한 줄이다. \(6 \cdot 6^k - 1\)에서 \(6(6^k - 1)\)을
만들면 \(-6\)이 되므로 \(-1\)과 맞추려면 얼마를 되돌려 주어야 하는가.
5. 예제 2.1(\(2^n \ge n^2\), \(n \ge 4\))을 백지에 재현하시오.
힌트
다섯 줄이다. 기초 / 가정 선언 + 목표 / ①② / ③ 연결 부등식 / 이어 붙이기.
연결 부등식의 차를 완전제곱으로 만드는 줄과, 거기서 \(k \ge 4\)를 쓰는 줄을
빠뜨리지 않았는지 스스로 채점한다.
6. 예제 2.2(\(6 \mid n^3 - n\) 귀납)를 백지에 재현하시오.
힌트
전개 뒤 잔여를 \(3k(k+1)\)로 묶는 것이 관건이다. 묶고 나면 물을 것이
하나뿐이다 — \(k(k+1)\)이 짝수인 근거는 어느 문제였는가.
표준 ●●○#
7. \(n \ge 1\)인 모든 자연수에 대해 \(n! \ge 2^{n-1}\)임을 증명하시오.
힌트
기초는 \(n = 1\)이고, 우변이 \(2^0 = 1\)이라는 점에 주의한다.
도착점도 미리 정리해 둔다: \((k+1)! \ge 2^{(k+1)-1} = 2^k\).
예제 2.3과 같은 ①이고 연결 부등식도 같은 꼴이다.
8. 모든 자연수 \(n\)에 대해 \(4 \mid (5^n - 1)\)임을 증명하시오.
9. 모든 자연수 \(n\)에 대해 \(7 \mid (8^n - 1)\)임을 (a) 귀납법으로 (b) 합동식(\(8 \equiv 1 \pmod 7\) + 31주차 문제 13)으로 각각 증명하고 두 증명을 비교하시오.
합에 대한 부등식 귀납 — 문제 10과 16에서 처음 쓴다
좌변이 \(\sum_{i=1}^{n}\) 꼴이면 ① 걸음은 마지막 항 분리다:
\(\sum_{i=1}^{k+1} a_i = \left(\sum_{i=1}^{k} a_i\right) + a_{k+1}\).
31주차 예제 2.1에서 등식 귀납에 쓴 그 변형이 그대로 ① 자리에 온다.
달라지는 것은 그 뒤다 — 귀납 가정은 등식이 아니라 부등식이므로, 분리한
마지막 항까지 얹은 중간값에서 목표까지 연결 부등식이 한 번 더 필요하다.
10. 모든 자연수 \(n\)에 대해 \(\displaystyle \sum_{i=1}^{n} \frac{1}{i^2} \le 2 - \frac{1}{n}\)임을 증명하시오. (연결 부등식: \(\frac{1}{(k+1)^2} \le \frac{1}{k} - \frac{1}{k+1}\) — 통분해 비교)
힌트
우변의 \(\frac1k - \frac{1}{k+1}\)을 통분하면 \(\frac{1}{k(k+1)}\)이다
(31주차 문제 10에서 쓴 분해와 같은 등식). 그러면 비교할 것은
\(\frac{1}{(k+1)^2}\)과 \(\frac{1}{k(k+1)}\)뿐이고, 분자가 같으므로 분모만 본다.
무대가 실수로 넓어진다 — 문제 11
지금까지의 귀납은 전부 정수 위의 명제였다. 베르누이 부등식에는 실수 \(x\)가
함께 등장한다. 헷갈리지 않는 방법은 하나다 — 귀납의 변수는 \(n\) 하나뿐이다.
\(x\)는 증명 첫 줄에서 “\(x \ge -1\)인 실수 \(x\)를 하나 고정하자”로 잡아 두고
끝까지 건드리지 않는다. \(P(n)\)은 “\((1+x)^n \ge 1 + nx\)”라는 \(n\)만의 명제가 된다.
11. (베르누이 부등식) \(x \ge -1\)인 실수 \(x\)와 모든 자연수 \(n\)에 대해 \((1+x)^n \ge 1 + nx\)임을 증명하시오. 그리고 조건 \(x \ge -1\)이 귀납 단계 어디서 소비되는지 명시하시오.
힌트
① 걸음은 \((1+x)^{k+1} = (1+x)^k (1+x)\)이다. ②에서 귀납 가정의 양변에
\((1+x)\)를 곱하는데, (W3)을 쓰려면 곱하는 수의 부호를 알아야 한다 —
그 부호를 보장하는 것이 조건 \(x \ge -1\)이다. ③에서는 전개한 뒤 남는 항
\(kx^2\)의 부호를 (W1)로 판정한다.
연결 부등식의 우변을 갈아 끼운다 — 문제 12에서 처음 쓴다
연결 부등식의 우변이 삼항식처럼 복잡하면 직접 비교가 번거롭다. 이때
눌러놓기를 쓴다 — 복잡한 우변을 그보다 크거나 같은 간단한 식으로 교체해
비교를 단순화하는 수법이다.
방향 규칙이 하나 있다: 우변을 키우는 교체만 섞는다. 새 우변을 이기면
원래 우변도 (W6) 추이성으로 이기기 때문이다. 우변을 줄이는 교체를 하나라도
섞으면 새 우변을 이겨도 원래 우변에 대해서는 아무 결론이 나오지 않는다.
이 수법은 45주차의 \(\varepsilon\)–\(N\) 논증에서 분모를 갈아 끼울 때 다시 쓴다.
12. (29주차 예제 2.3의 빚) \(n \ge 4\)인 모든 정수에 대해 \(3^n > n^3\)임을 증명하시오. (연결 부등식 힌트: \(3k^3 \ge (k+1)^3\)을 보이려면 \(2k^3 \ge 3k^2 + 3k + 1\) — 우변을 \(7k^2\)으로 눌러 놓고 \(2k \ge 7\)을 쓰라)
힌트
\(k \ge 1\)이면 \(3k \le 3k^2\)이고 \(1 \le k^2\)이므로
\(3k^2 + 3k + 1 \le 3k^2 + 3k^2 + k^2\)이다. 오른쪽 끝이 무엇이 되는지 계산한 뒤,
\(2k^3\)이 그것보다 큰 조건을 \(k\)에 대해 풀어 본다.
13. 모든 자연수 \(n\)에 대해 \(6 \mid (7^n - 1)\)임을 증명하시오.
14. 모든 자연수 \(n\)에 대해 \(8 \mid (3^{2n} - 1)\)임을 증명하시오. (힌트: \(3^{2(k+1)} = 9 \cdot 3^{2k}\))
힌트
지수가 \(2n\)이므로 \(n\)이 1 늘면 지수는 2 는다 — 그래서 곱해지는 수가 3이
아니라 \(3^2 = 9\)다. 나머지는 훈련 1과 같은 재배열이다:
\(9 \cdot 3^{2k} - 1 = 9(3^{2k} - 1) + \underline{\quad}\)의 빈칸을 채운다.
도전 ●●●#
귀납 단계 안에서 경우를 나눈다 — 문제 15
지금까지의 귀납 단계는 한 줄기였다. 문제 15에서는 \(P(k)\)가 주는 정보가
한 가지가 아니라 여러 모양 중 하나여서, 모양별로 다른 처리를 해야 한다.
그럴 때는 귀납 단계 안에서 경우를 나눈다(17주차의 경우 나누기).
채점 기준도 그대로다: ① 경우들이 가능한 모양을 빠짐없이 덮는가
② 각 경우가 각각 \(P(k+1)\)까지 완결되는가.
또 하나 새로운 점은 결론이 “존재한다” 꼴이라는 것이다 — \(P(k)\)가 주는
표현 하나를 고쳐서 \(P(k+1)\)의 표현을 만들어 제시한다.
15. (우표 문제) 8 이상의 모든 정수는 3원 우표와 5원 우표의 합으로 만들 수 있음 — 즉 \(n \ge 8\)이면 \(n = 3a + 5b\)인 음이 아닌 정수 \(a, b\)가 존재함 — 을 귀납법으로 증명하시오. (귀납 단계 힌트: \(k\)의 표현에 5가 있으면 \(5 \to 3+3\) 교체, 없으면(\(3\)뿐이면) \(k \ge 9\)이므로 \(3\)이 세 장 이상 — \(3+3+3 \to 5+5\) 교체. 케이스 안의 케이스다.)
힌트
교체가 왜 \(+1\)을 만드는지 계산으로 확인해 두면 나머지는 대입이다:
\(5\) 한 장을 \(3\) 두 장으로 바꾸면 금액이 \(6 - 5 = 1\)만큼 늘고,
\(3\) 세 장을 \(5\) 두 장으로 바꾸면 \(10 - 9 = 1\)만큼 는다.
둘째 경우에서 “\(3\)이 세 장 이상”을 보장하는 것은 \(k \ge 8\)과 \(k = 3a\)다.
16. 모든 자연수 \(n\)에 대해 \(\displaystyle \sum_{i=1}^{n} \frac{1}{\sqrt{i}} \ge \sqrt{n}\)임을 증명하시오. (연결 부등식: \(\sqrt{k} + \frac{1}{\sqrt{k+1}} \ge \sqrt{k+1}\) — 양변에 \(\sqrt{k+1}\)을 곱하고 16주차 제곱 비교로)
힌트
양변에 \(\sqrt{k+1} > 0\)을 곱하면 (W3)에 의해 방향이 유지되고
\(\sqrt{k}\sqrt{k+1} + 1 \ge k + 1\)이 된다. 양변에서 1을 빼면(W2)
남는 것은 \(\sqrt{k(k+1)} \ge k\) 하나다. 양변이 0 이상이므로 제곱해서
비교할 수 있다(16주차 문제 11의 대우, 16주차 문제 17).
17. (진단) 다음 답안의 결함을 지적하시오.
“명제: \(n \ge 4\)에서 \(2^n \ge n^2\). … [귀납] \(2^k \ge k^2\)이라 가정하자. \(2^{k+1} = 2 \cdot 2^k \ge 2k^2\)이고, \(2k^2 \ge (k+1)^2\)은 \(k\)가 충분히 크면 당연하므로 \(2^{k+1} \ge (k+1)^2\)이다. \(\blacksquare\)”
18. 모든 정수 \(n \ge 0\)에 대해 \(11 \mid \big(10^{2n+1} + 1\big)\)임을 증명하시오 (즉 \(11 \mid 11, 1001, 100001, \dots\)). (힌트: \(10^{2(k+1)+1} + 1 = 100 \cdot 10^{2k+1} + 1 = 100(10^{2k+1} + 1) - 99\))
힌트
기초 단계의 출발점이 \(n_0 = 0\)이라는 점을 놓치지 않는다.
잔여가 \(+99\)가 아니라 \(-99\)인 것이 훈련 3과 다른 점이다 — 배수 두 개의
차도 배수라는 사실이 필요하고, 그것은 2주차 문제 7이다.
그리고 \(99\)가 11의 배수인지는 \(99 = 11 \times 9\)로 확인한다.
19. 예제 2.2와 30주차 문제 17은 같은 정리(\(6 \mid n^3 - n\))의 두 증명이다. (a) 두 증명이 각각 의존하는 부품 목록을 쓰시오. (b) “\(30 \mid n^5 - n\)”을 증명하고 싶다면 어느 스타일이 더 유망해 보이는지, 이유와 함께 한 문장으로 쓰시오 (증명은 하지 않아도 됨).
힌트
(a)는 두 증명문을 나란히 놓고 “~에 의해”, “~이므로”가 붙은 인용을 전부
뽑아 적으면 된다. (b)는 \(30\)을 소인수로 쪼개 보고, 각 스타일에서 무엇이
늘어나는지 비교한다 — 조립은 부품 개수가, 귀납은 전개의 크기가 는다.
20. (서술) (a) 기초 단계의 위치(\(n_0\))를 정하는 절차(실험 \(\to\) 첫 지점 \(\to\) 연결 부등식의 요구 조건 확인)를 요약하시오. (b) “연결 부등식을 빼먹는 실수”가 왜 부등식 귀납 특유의 함정인지 — 등식 귀납과 비교해 — 두 문장 이내로 쓰시오.
백지 재현 — 복습 프로토콜#
권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.
1차 시도 (4일차) — 틀 카드 허용. 세 걸음(§2 관찰)과 일반화된 귀납 원리, 근거 목록(§1.7)만 펴 놓고, 예제 2.1(\(2^n \ge n^2\))을 처음부터 끝까지 적는다. 본문과 완성본 표는 보지 않는다.
2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다.
부등식 귀납의 2단 구조(①②③)를 백지에 썼다 — 특히 ③이 “별도로 증명하는 독립 명제”라는 점까지.
일반화된 귀납 원리를 \(n_0\)을 포함한 문장으로 썼다.
예제 2.1을 처음부터 끝까지 재현했다 — 연결 부등식의 차 계산과 \(k \ge 4\) 소비처 표시 포함.
나누어떨어짐 귀납의 표준 수(잔여 제작 + 배수 판정)를 재현했다 (예제 2.2 또는 훈련 1).
베르누이 부등식(문제 11)과 조건 \(x \ge -1\)의 소비처를 설명했다.
\(n_0\)을 정하는 절차(실험 \(\to\) 첫 지점 \(\to\) 연결부의 요구 범위와 대조)를 말할 수 있다.
각 줄의 근거가 ①~④ 중 무엇인지, 부등호마다 (W1)~(W6) 중 무엇인지 말할 수 있다.
막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.
막힌 지점 |
처방 |
|---|---|
기초 단계를 몇에서 시작할지 모르겠다 |
§1.4 — 실험 표를 만들고, 연결부가 요구하는 범위와 큰 쪽을 택한다 |
귀납 가정을 어디에 끼우는지 모르겠다 |
§1.3의 ① — \(k+1\)의 식에 \(k\)의 식이 드러나도록 먼저 변형한다 |
귀납 가정을 넣은 뒤 다음 줄이 나오지 않는다 |
예제 2.1의 4단계 — 중간값과 목표를 나란히 적고 그 사이의 부등식을 별도 명제로 세운다 |
연결 부등식을 세웠는데 증명이 안 된다 |
16주차의 차 계산과 완전제곱, 그리고 문제 12의 눌러놓기 |
나누어떨어짐에서 잔여가 안 보인다 |
§1.5 — 빼고 더하기로 \(f(k)\) 항을 강제로 만들고 역전개로 검산한다 |
부등호 방향이 헷갈린다 |
(W3)과 (W6) — 곱하는 수의 부호를 먼저 확인하고, 두 부등호의 방향을 맞춘다 |
하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.
해설#
각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.
준비 운동#
두 단계는 기초 단계와 귀납 단계다. 사용 지점 표시가 필요한 이유:
표시가 없으면 그 증명이 귀납 가정을 실제로 썼는지 검사할 수 없고, 쓰지 않았다면 애초에 귀납이 필요 없는 명제였다는 뜻이 된다(31주차 문제 20).
\(2 \cdot 2^k > 2k = k + k \ge k + 1\) — 마지막 부등호가 연결 부등식이고,
근거는 \(k \ge 1\)이다. 이 한 걸음이 이번 주 내내 반복된다.
16주차의 원문 그대로 옮기면 다음과 같다.
(W1) 모든 실수 \(x\)에 대해 \(x^2 \ge 0\)이다. 등호는 \(x = 0\)일 때만 성립한다. (W3) \(a \le b\)이고 \(c > 0\)이면 \(ac \le bc\)이다. \(a \le b\)이고 \(c < 0\)이면 \(ac \ge bc\)이다(방향 반전). 부등호가 \(<\)일 때도 같다. (W4) \(a > 0\)이고 \(b > 0\)이면 \(a + b > 0\)이고 \(ab > 0\)이다. \(a \ge 0\)이고 \(b \ge 0\)이면 \(a + b \ge 0\)이고 \(ab \ge 0\)이다 — 두 판본이 모두 필요하다. 이번 주에는 앞 판본(양수끼리)이 문제 3의 “\(k \ge 1 > 0\)이므로 \(4k > 0\)”에서, 뒤 판본(0 이상끼리)이 문제 11의 “\(kx^2 \ge 0\)”에서 쓰인다. (W6) (추이성) \(a < b\)이고 \(b < c\)이면 \(a < c\)이다. 부등호 하나가 \(\le\)로 바뀌어도 같다. 두 부등호가 모두 \(\le\)이면 결론도 \(\le\)이다 — 16주차의 유도가 그대로 덮는다: 두 차 \(b - a\)와 \(c - b\)가 모두 0 이상이면 (W4)의 뒤 판본에 의해 그 합 \(c - a\)도 0 이상이다. 이번 주의 부등식 귀납은 대부분 이 \(\ge\) 연쇄 판본을 쓴다(문제 7의 \(k = 1\)에서는 두 부등호가 실제로 모두 등호가 된다).
빈칸 사다리 — 훈련 1#
(1) \(5\) (2) 배수의 정수배는 배수 (3) 2주차 예제 2.2 (배수 두 개의 합은 배수)
※ (1)은 역전개로 확인한다: \(6(6^k - 1) + 5 = 6^{k+1} - 6 + 5 = 6^{k+1} - 1\) ✓. (2)의 정확한 형태는 “\(a \mid b\)이면 \(a \mid bc\)”이고, 여기서는 \(5 \mid (6^k - 1)\)에 \(c = 6\)을 곱한 것이다.
빈칸 사다리 — 훈련 2#
(1) 가정 (2) \(k + 1\) (3) 귀납 가정의 양변에 양수 \(2\)를 곱함 — (W3) (4) \(k\) (5) 차가 0보다 크므로 \(2k + 2 \ge k + 2\)이다 (6) 부등호의 추이성 (W6)
※ 이 명제는 \(2^n \ge n + 1\)이고 31주차 문제 16(\(n < 2^n\))과 사실상 같은 내용이다. 정수 위에서 \(n < 2^n\)과 \(n + 1 \le 2^n\)이 같은 말이기 때문이다. 연결 부등식의 차가 \(k\) 하나로 떨어지는 것이 이 훈련이 쉬운 이유다.
빈칸 사다리 — 훈련 3#
(1) \(n = 1\)일 때 \(10^1 - 1 = 9\)이고 \(9 = 9 \times 1\)이므로 \(9 \mid 9\) ✓. (2) \(10^{k+1} - 1 = 10 \cdot 10^k - 1 = 10(10^k - 1) + 9\) (3) 첫 항 \(10(10^k - 1)\)은 귀납 가정과 “배수의 정수배는 배수”(2주차 훈련 1)에 의해 9의 배수이고, 잔여 \(9\)도 9의 배수다. 9의 배수 두 개의 합은 9의 배수이므로(2주차 예제 2.2) \(9 \mid (10^{k+1} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(9 \mid (10^n - 1)\)이다. \(\blacksquare\)
※ 검산: \(10(10^k - 1) + 9 = 10^{k+1} - 10 + 9 = 10^{k+1} - 1\) ✓. 이 명제는 “9의 배수 판정법(각 자리 수의 합)”의 씨앗이다 — \(10 \equiv 1 \pmod 9\)이므로 \(10^n \equiv 1\)이고, 그래서 자릿수를 다 더해도 나머지가 변하지 않는다.
문제 1#
접근. 좌변과 우변을 각각 계산해 표로 만들고 ✓/✗를 적는다. 등호 유무에 민감해야 한다 — 이번 문제의 부등호는 둘 다 \(>\)이므로 좌우가 같은 자리는 ✗다. “계속 성립하기 시작하는 첫 지점”을 묻고 있으므로, 도중에 한 번이라도 ✗가 나오면 그 앞의 ✓는 고립된 성립으로 보고 지나간다.
풀이. (a) \(n = 1\): \(2 > 1\) ✓. \(n = 2\): \(4 > 4\) ✗ (등호이므로 \(>\)는 거짓). \(n = 3\): \(8 > 9\) ✗. \(n = 4\): \(16 > 16\) ✗ (등호). \(n = 5\): \(32 > 25\) ✓. \(n = 6\): \(64 > 36\) ✓. 따라서 \(n = 5\)부터 계속 성립한다(\(n = 1\)의 성립은 고립되어 있다). (b) \(n = 1\): \(1 < 3\) ✗. \(n = 2\): \(2 < 9\) ✗. \(n = 3\): \(6 < 27\) ✗. \(n = 4\): \(24 < 81\) ✗. \(n = 5\): \(120 < 243\) ✗. \(n = 6\): \(720 < 729\) ✗ (아슬아슬하게 실패). \(n = 7\): \(5040 > 2187\) ✓. 따라서 \(n = 7\)부터이다.
복기. (a)의 답이 예제 2.1(\(2^n \ge n^2\), \(n_0 = 4\))과 다른 이유는 등호 하나다 — \(n = 4\)에서 \(16 = 16\)이므로 \(\ge\)는 참이고 \(>\)는 거짓이다. 부등호의 종류가 \(n_0\)을 바꾼다. (b)에서 \(n = 6\)이 \(720\) 대 \(729\)로 아슬아슬하게 실패하는 것도 같은 교훈이다 — 표를 서너 개만 만들고 멈추면 이 자리를 놓친다.
문제 2#
접근. §1.2의 명명 상자를 재현하는 문제다. 세 걸음 각각에 대해 “무엇을 하는가”와 “왜 하는가”를 한 줄씩 적는다.
풀이. 목표가 \(A_{k+1} \ge B_{k+1}\) 꼴일 때 귀납 단계는 세 걸음이다. ① \(A_{k+1}\)을 \(A_k\)가 드러나도록 변형한다 — 귀납 가정을 끼워 넣을 자리를 만들기 위해서다 (예: \(2^{k+1} = 2 \cdot 2^k\), \((k+1)! = (k+1) \cdot k!\), \(\sum_{i=1}^{k+1} = \sum_{i=1}^{k} + a_{k+1}\)). ② 귀납 가정 \(A_k \ge B_k\)를 투입해 중간값까지 온다. 이 줄에 “(귀납 가정)” 표시를 단다. 부등호가 유지되는 근거는 대개 (W3)이다. ③ 연결 부등식: “중간값 \(\ge B_{k+1}\)”을 별도로 증명한다. 이것은 귀납과 무관한 독립 명제이고, 근거는 16주차의 (W1)~(W6)과 대수 변형이다. 마지막으로 ②와 ③의 부등호를 (W6) 추이성으로 이어 \(A_{k+1} \ge B_{k+1}\)을 얻는다.
복기. “연결 부등식”이 가리키는 것은 중간값과 목표 사이의 간격이다. 등식 귀납에는 이 간격이 없어(항등식이라 자동으로 닫힌다) 이 낱말도 쓰이지 않는다.
문제 3#
접근. 기초는 \(n = 1\)이고 \(3 \ge 3\)이므로 등호로 성립한다. 귀납 단계에서 ① \(3^{k+1} = 3 \cdot 3^k\), ② 귀납 가정으로 중간값 \(3(2k+1) = 6k + 3\), ③ 목표 \(2(k+1) + 1 = 2k + 3\)과의 차를 계산한다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(3^1 = 3\)이고 \(2 \cdot 1 + 1 = 3\)이므로 \(3 \ge 3\) ✓. [귀납] 자연수 \(k\)에 대해 \(3^k \ge 2k + 1\)이라 가정하자. 목표는 \(3^{k+1} \ge 2(k+1) + 1 = 2k + 3\)이다. \(3 > 0\)이므로 귀납 가정의 양변에 3을 곱해도 방향이 유지되고(W3),
이다(가운데 부등호가 귀납 가정). 연결 부등식: \(6k + 3 \ge 2k + 3\)을 보인다. 차를 계산하면 \((6k + 3) - (2k + 3) = 4k\)이고, \(k \ge 1 > 0\)이므로 \(4k > 0\)이다(W4). 따라서 \(6k + 3 \ge 2k + 3\)이고, 추이성(W6)에 의해 \(3^{k+1} \ge 2k + 3 = 2(k+1) + 1\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(3^n \ge 2n + 1\)이다. \(\blacksquare\)
복기. 연결 부등식의 차가 \(4k\)처럼 단항식으로 떨어지면 (W4) 한 줄로 끝난다. 차가 \((k-1)^2 - 2\)처럼 이차식이면 완전제곱을 만들어 (W1)에 넘긴다(예제 2.1). 차를 계산해 부호를 판정한다는 방침은 같고, 판정 도구만 바뀐다. (검산: \(n = 3\)에서 \(27 \ge 7\) ✓. \(n = 4\)에서 \(81 \ge 9\) ✓.)
문제 4#
접근. 훈련 1의 재현이다. 막히는 자리는 재배열 한 줄뿐이므로, 그 줄을 역전개로 검산하는 습관까지 함께 재현한다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(6^1 - 1 = 5\)이고 \(5 = 5 \times 1\)이므로 \(5 \mid 5\) ✓. [귀납] 자연수 \(k\)에 대해 \(5 \mid (6^k - 1)\)이라 가정하자. 목표는 \(5 \mid (6^{k+1} - 1)\)이다. 재배열하면
이다. 첫 항 \(6(6^k - 1)\)은 귀납 가정과 “배수의 정수배는 배수”(2주차 훈련 1)에 의해 5의 배수이고, 잔여 \(5\)도 \(5 = 5 \times 1\)이므로 5의 배수다. 5의 배수 두 개의 합은 5의 배수이므로(2주차 예제 2.2) \(5 \mid (6^{k+1} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(5 \mid (6^n - 1)\)이다. \(\blacksquare\)
복기. 재배열 줄의 검산: \(6(6^k - 1) + 5 = 6^{k+1} - 6 + 5 = 6^{k+1} - 1\) ✓. 빼고 더하기에서 되돌려 줄 양은 “곱한 수 \(-\) 원래 상수”로 나온다 — 여기서는 \(6 - 1 = 5\)다. 문제 8, 13, 14에서 이 값이 각각 \(5 - 1 = 4\), \(7 - 1 = 6\), \(9 - 1 = 8\)로 바뀔 뿐 절차는 같다. (검산: \(n = 2\)에서 \(36 - 1 = 35 = 5 \times 7\) ✓.)
문제 5#
접근. 예제 2.1의 재현이다. 다섯 줄 중 어느 줄이 빠지기 쉬운지 미리 알고 시작한다 — 연결 부등식 줄과, 그 안에서 \(k \ge 4\)를 쓰는 대목이다.
풀이. 귀납법으로 증명한다. [기초] \(n = 4\)일 때 \(2^4 = 16\)이고 \(4^2 = 16\)이므로 \(2^4 \ge 4^2\) ✓. [귀납] \(k \ge 4\)인 정수 \(k\)에 대해 \(2^k \ge k^2\)이라 가정하자. 목표는 \(2^{k+1} \ge (k+1)^2\)이다. \(2 > 0\)이므로 (W3)에 의해
이다(부등호가 귀납 가정). 연결 부등식: \(2k^2 \ge (k+1)^2\)을 보인다. 차를 계산하면
이고, \(k \ge 4\)이면 \(k - 1 \ge 3\)이다. \(k = 4\)이면 \((k-1)^2 = 9\)로 등호이고, \(k \ge 5\)이면 \(0 \le 3 < k - 1\)이므로 16주차 문제 11에 의해 \(9 < (k-1)^2\)이다. 어느 쪽이든 \((k-1)^2 \ge 9\)이므로 \((k-1)^2 - 2 \ge 7 > 0\)이다. 따라서 \(2k^2 \ge (k+1)^2\)이다. 추이성(W6)에 의해 \(2^{k+1} \ge 2k^2 \ge (k+1)^2\)이다. 일반화된 귀납 원리에 의해 \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(2^n \ge n^2\)이다. \(\blacksquare\)
복기. 자가 채점 항목은 셋이다 — ① 기초를 \(n = 4\)에서 확인했는가 ② 연결 부등식을 별도 줄로 세웠는가 ③ 그 줄에서 \(k \ge 4\)를 실제로 썼는가. 셋째 항목이 없으면 가정 \(k \ge 4\)가 증명 어디에서도 소비되지 않고, 그러면 \(n \ge 1\)에서도 증명한 셈이 되어 \(n = 3\)의 반례와 충돌한다. 쓰이지 않는 가정이 있으면 증명을 의심한다. (검산: \(n = 5\)에서 \(32 \ge 25\) ✓. \(n = 6\)에서 \(64 \ge 36\) ✓.)
문제 6#
접근. 예제 2.2의 재현이다. 관건은 전개 뒤 잔여를 \(3k(k+1)\)로 묶는 것이다. 묶고 나면 물을 것은 “\(k(k+1)\)이 짝수인가” 하나로 줄어든다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(1^3 - 1 = 0\)이고 \(0 = 6 \times 0\)이므로 \(6 \mid 0\) ✓. [귀납] 자연수 \(k\)에 대해 \(6 \mid (k^3 - k)\)라 가정하자. 목표는 \(6 \mid \big((k+1)^3 - (k+1)\big)\)이다. 전개해 재배열하면
이다. 첫 항 \(k^3 - k\)는 귀납 가정에 의해 6의 배수다. 둘째 항에서 \(k\)와 \(k+1\)은 연속한 두 정수이므로 그 곱 \(k(k+1)\)은 짝수이고(1주차 문제 16), \(k(k+1) = 2m\)인 정수 \(m\)이 존재한다. 따라서 \(3k(k+1) = 3 \cdot 2m = 6m\)이고 \(m\)은 정수이므로 \(6 \mid 3k(k+1)\)이다. 6의 배수 두 개의 합은 6의 배수이므로 (2주차 예제 2.2) \(6 \mid \big((k+1)^3 - (k+1)\big)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(6 \mid (n^3 - n)\)이다. \(\blacksquare\)
복기. 잔여가 다항식일 때는 묶어서 인수를 드러내는 것이 판정을 쉽게 만든다. \(3k^2 + 3k\)를 그대로 두면 6의 배수인지 바로 보이지 않지만, \(3 \cdot k(k+1)\)로 묶으면 “3 곱하기 짝수”라는 구조가 드러난다. (검산: \(n = 4\)에서 \(64 - 4 = 60 = 6 \times 10\) ✓.)
문제 7#
접근. 예제 2.3과 ①이 같다: \((k+1)! = (k+1) \cdot k!\). 다른 점은 우변의 지수다 — 목표는 \(2^{(k+1)-1} = 2^k\)이므로, 중간값 \((k+1) \cdot 2^{k-1}\)에서 \(2 \cdot 2^{k-1} = 2^k\)까지 가는 연결 부등식이 필요하다. 기초에서 \(2^{n-1}\)의 \(n = 1\) 값이 \(2^0 = 1\)이라는 점을 놓치지 않는다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(1! = 1\)이고 \(2^{1-1} = 2^0 = 1\)이므로 \(1 \ge 1\) ✓. [귀납] \(k \ge 1\)인 자연수 \(k\)에 대해 \(k! \ge 2^{k-1}\)이라 가정하자. 목표는 \((k+1)! \ge 2^{(k+1)-1} = 2^k\)이다. \(k + 1 > 0\)이므로 귀납 가정의 양변에 \(k+1\)을 곱해도 방향이 유지되고(W3),
이다(부등호가 귀납 가정). 연결 부등식: \((k+1) \cdot 2^{k-1} \ge 2 \cdot 2^{k-1} = 2^k\)을 보인다. \(k \ge 1\)이므로 \(k + 1 \ge 2\)이고, 양변에 양수 \(2^{k-1}\)을 곱하면(W3) \((k+1)2^{k-1} \ge 2 \cdot 2^{k-1} = 2^k\)이다. 추이성(W6)에 의해 \((k+1)! \ge 2^k = 2^{(k+1)-1}\)이다. 수학적 귀납법에 의해 \(n \ge 1\)인 모든 자연수 \(n\)에 대해 \(n! \ge 2^{n-1}\)이다. \(\blacksquare\)
복기. 예제 2.3(\(n! > 2^n\), \(n \ge 4\))과 이 문제(\(n! \ge 2^{n-1}\), \(n \ge 1\))의 차이는 우변을 절반으로 낮춘 것이고, 그 대가로 \(n_0\)이 4에서 1로 내려왔다. 목표를 약하게 잡으면 무대가 넓어진다 — 어느 쪽이 필요한지는 이 부등식을 어디에 쓸지가 정한다. (검산: \(n = 5\)에서 \(120 \ge 16\) ✓. \(n = 2\)에서 \(2 \ge 2\) ✓ — 등호.)
문제 8#
접근. 나누어떨어짐 귀납의 표준 수 그대로다. \(5^{k+1} - 1\)에서 \(5^k - 1\)을 강제로 만들면 \(5(5^k - 1) = 5^{k+1} - 5\)이므로 잔여는 \(-1 - (-5) = 4\)다. 잔여 4가 4의 배수인지만 확인하면 끝난다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(5^1 - 1 = 4\)이고 \(4 = 4 \times 1\)이므로 \(4 \mid 4\) ✓. [귀납] 자연수 \(k\)에 대해 \(4 \mid (5^k - 1)\)이라 가정하자. 목표는 \(4 \mid (5^{k+1} - 1)\)이다. 재배열하면
이다. 첫 항 \(5(5^k - 1)\)은 귀납 가정과 “배수의 정수배는 배수”(2주차 훈련 1)에 의해 4의 배수이고, 잔여 \(4\)도 4의 배수다. 4의 배수 두 개의 합은 4의 배수이므로(2주차 예제 2.2) \(4 \mid (5^{k+1} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(4 \mid (5^n - 1)\)이다. \(\blacksquare\)
복기. 검산: \(5(5^k - 1) + 4 = 5^{k+1} - 1\) ✓. \(n = 3\)에서 \(124 = 4 \times 31\) ✓. 같은 절차가 밑이 \(a\)이고 나누는 수가 \(a - 1\)인 모든 경우에 작동한다 — \((a-1) \mid (a^n - 1)\)이 일반형이고, 문제 9(\(a=8\))\(\cdot\)13(\(a=7\))\(\cdot\)훈련 1(\(a=6\))\(\cdot\)훈련 3(\(a=10\))이 전부 같은 정리의 사례다.
문제 9#
접근. (a)는 문제 8과 같은 재배열이다. (b)는 \(8 - 1 = 7\)이므로 \(8 \equiv 1 \pmod 7\)이고, 31주차 문제 13(합동은 거듭제곱을 보존한다)을 한 번 적용하면 끝난다. 비교는 “어느 쪽이 짧은가”가 아니라 “짧아진 부분이 어디로 갔는가”를 묻는 것으로 읽는다.
풀이. (a) 귀납법. [기초] \(n = 1\)일 때 \(8^1 - 1 = 7\)이고 \(7 \mid 7\) ✓. [귀납] 자연수 \(k\)에 대해 \(7 \mid (8^k - 1)\)이라 가정하자. 재배열하면
이다. 첫 항은 귀납 가정과 2주차 훈련 1에 의해 7의 배수이고, 잔여 \(7\)도 7의 배수다. 두 배수의 합은 배수이므로(2주차 예제 2.2) \(7 \mid (8^{k+1} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(7 \mid (8^n - 1)\)이다. \(\blacksquare\)
(b) 합동식. \(8 - 1 = 7\)이고 \(7 \mid 7\)이므로 정의에 의해 \(8 \equiv 1 \pmod 7\)이다. 31주차 문제 13에 의해 모든 자연수 \(n\)에 대해 \(8^n \equiv 1^n \pmod 7\)이고, \(1^n = 1\)이므로 \(8^n \equiv 1 \pmod 7\)이다. 합동의 정의에 의해 \(7 \mid (8^n - 1)\)이다. \(\blacksquare\)
비교. (b)가 세 줄로 끝난다. 그러나 (b)가 인용한 31주차 문제 13은 \(m\)에 대한 귀납법으로 증명된 정리다 — (b)는 귀납을 없앤 것이 아니라 이미 증명해 둔 부품 안에 넣어 둔 것이고, 이것이 근거 ④가 하는 일이다. 부품이 없는 상황(예제 2.2처럼 밑이 고정된 거듭제곱이 아닌 경우)에서는 (a)의 절차를 직접 써야 한다.
복기. 검산: \(n = 2\)에서 \(63 = 7 \times 9\) ✓.
문제 10#
접근. 좌변이 합이므로 ①은 마지막 항 분리다: \(\sum_{i=1}^{k+1} \frac{1}{i^2} = \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2}\). ②로 귀납 가정을 넣으면 중간값이 \(2 - \frac1k + \frac{1}{(k+1)^2}\)이고 목표는 \(2 - \frac{1}{k+1}\)이므로, 남는 것은 \(\frac{1}{(k+1)^2} \le \frac1k - \frac{1}{k+1}\) 하나다. 우변을 통분하면 \(\frac{1}{k(k+1)}\)이니 분자가 같은 두 분수의 분모만 비교한다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 좌변 \(\frac{1}{1^2} = 1\), 우변 \(2 - \frac11 = 1\)이므로 \(1 \le 1\) ✓. [귀납] 자연수 \(k\)에 대해 \(\sum_{i=1}^{k} \frac{1}{i^2} \le 2 - \frac1k\)이라 가정하자. 목표는 \(\sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac{1}{k+1}\)이다. 마지막 항을 분리하고 귀납 가정을 넣으면(양변에 같은 수를 더해도 방향 유지 — W2)
이다. 연결 부등식: \(\frac{1}{(k+1)^2} \le \frac1k - \frac{1}{k+1}\)을 보인다. 우변을 통분하면 \(\frac{(k+1) - k}{k(k+1)} = \frac{1}{k(k+1)}\)이다. \(k \ge 1\)이므로 \(k+1 > k > 0\)이고, 양변에 양수 \(k+1\)을 곱하면 \((k+1)^2 > k(k+1) > 0\)이다(W3). 여기서 두 분수의 비교는 다시 (W3)으로 만든다: \(k(k+1) > 0\)이고 \((k+1)^2 > 0\)이므로 그 곱도 양수이고(W4), 따라서 \(c = \frac{1}{k(k+1)(k+1)^2}\)은 양수다(W5). \(k(k+1) < (k+1)^2\)의 양변에 이 양수 \(c\)를 곱하면 방향이 유지되어(W3)
이다. 따라서
이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 성립한다. \(\blacksquare\)
복기. 분해 \(\frac{1}{k(k+1)} = \frac1k - \frac{1}{k+1}\)은 31주차 문제 10에서 망원 합을 만들 때 쓴 등식이다. 여기서는 합을 계산하는 데가 아니라 연결 부등식의 우변을 만드는 데 쓰였다. 결과의 의미: \(\sum_{i=1}^{n} \frac{1}{i^2}\)은 \(n\)이 아무리 커져도 2를 넘지 않는다 — 46주차에서 “수렴”의 근거가 된다. (검산: \(n = 2\)에서 좌변 \(1.25 \le\) 우변 \(1.5\) ✓.)
문제 11#
접근. 귀납의 변수는 \(n\) 하나다. \(x\)는 첫 줄에서 고정하고 끝까지 둔다. ①은 \((1+x)^{k+1} = (1+x)^k (1+x)\)이고, ②에서 귀납 가정의 양변에 \((1+x)\)를 곱하는데 (W3)을 쓰려면 곱하는 수가 0 이상이어야 한다 — 그 보장이 \(x \ge -1\)이다. ③에서는 곱을 전개해 남는 항 \(kx^2\)의 부호를 (W1)로 판정한다.
풀이. \(x \ge -1\)인 실수 \(x\)를 하나 고정하고 \(n\)에 대한 귀납법으로 증명한다. [기초] \(n = 1\)일 때 좌변 \((1+x)^1 = 1 + x\), 우변 \(1 + 1 \cdot x = 1 + x\)이므로 등호로 성립한다 ✓. [귀납] 자연수 \(k\)에 대해 \((1+x)^k \ge 1 + kx\)라 가정하자. 목표는 \((1+x)^{k+1} \ge 1 + (k+1)x\)이다. \(x \ge -1\)의 양변에 1을 더하면 \(1 + x \ge 0\)이고(W2), 귀납 가정의 양변에 \(1+x\)를 곱해도 방향이 유지된다(W3 — 여기가 \(x \ge -1\)의 소비처다):
연결 부등식: \((1+kx)(1+x) \ge 1 + (k+1)x\)를 보인다. 좌변을 전개하면 \((1 + kx)(1 + x) = 1 + x + kx + kx^2 = 1 + (k+1)x + kx^2\)이고, \(x^2 \ge 0\)이며(W1) \(k > 0\)이므로 \(kx^2 \ge 0\)이다(W4). 따라서 \(1 + (k+1)x + kx^2 \ge 1 + (k+1)x\)이다(W2). 추이성(W6)에 의해 \((1+x)^{k+1} \ge 1 + (k+1)x\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \((1+x)^n \ge 1 + nx\)이다. \(\blacksquare\)
조건의 소비처. \(x \ge -1\)은 귀납 단계 ②에서 단 한 번, 곱하는 수 \(1+x\)가 0 이상임을 보장하는 데 쓰인다. 이 조건이 없으면 (W3)의 뒷부분(음수를 곱하면 방향이 뒤집힌다)에 걸려 부등호가 반대로 간다.
복기. 검산: \(x = 0.5\), \(n = 2\)에서 \(2.25 \ge 2\) ✓. \(x = -0.5\), \(n = 3\)에서 \(0.125 \ge -0.5\) ✓. 이 부등식은 46주차 문제 16에서 “\(0 < r < 1\)이면 \(r^n \to 0\)”의 핵심 부품이 된다 — \(\frac{1}{r^n} = (1+h)^n \ge 1 + nh\)로 아래에서 밀어 올린다.
문제 12#
접근. 29주차 예제 2.3에서 \(n = 3\)의 반례로 무너뜨린 뒤 “\(n \ge 4\)로 고치면 참”이라고 예고만 해 둔 명제다. ①②는 예제 2.1과 같은 꼴이고, 어려운 곳은 ③이다. \(3k^3 \ge (k+1)^3\)을 전개하면 \(2k^3 \ge 3k^2 + 3k + 1\)이 남는데 우변이 삼항이라 직접 비교가 번거롭다. 이럴 때 눌러놓기 — 우변을 그보다 크거나 같은 단항식으로 바꿔 비교를 단순화한다.
풀이. 귀납법으로 증명한다. [기초] \(n = 4\)일 때 \(3^4 = 81 > 64 = 4^3\) ✓. [귀납] \(k \ge 4\)인 정수 \(k\)에 대해 \(3^k > k^3\)이라 가정하자. 목표는 \(3^{k+1} > (k+1)^3\)이다. \(3 > 0\)이므로 (W3)에 의해 \(3^{k+1} = 3 \cdot 3^k > 3k^3\)이다 (부등호가 귀납 가정). 연결 부등식: \(3k^3 \ge (k+1)^3\)을 보인다. \((k+1)^3 = k^3 + 3k^2 + 3k + 1\)이므로 보일 것은 \(2k^3 \ge 3k^2 + 3k + 1\)이다. \(k \ge 4 \ge 1\)이므로 \(3k \le 3k^2\)이고 \(1 \le k^2\)이므로
이다. 한편 \(k \ge 4\)이므로 \(2k \ge 8 > 7\)이고, 양변에 양수 \(k^2\)을 곱하면(W3) \(2k^3 = (2k)k^2 > 7k^2\)이다. 추이성(W6)에 의해 \(2k^3 > 3k^2 + 3k + 1\), 곧 \(3k^3 > (k+1)^3\)이다. 다시 추이성에 의해 \(3^{k+1} > 3k^3 > (k+1)^3\)이다. 일반화된 귀납 원리에 의해 \(n \ge 4\)인 모든 정수 \(n\)에 대해 \(3^n > n^3\)이다. \(\blacksquare\)
복기. 눌러놓기의 요령은 같은 방향으로만 갈아 끼운다는 것이다. \(3k \le 3k^2\)과 \(1 \le k^2\)은 둘 다 우변을 키우는 교체이므로 새 우변 \(7k^2\)을 이기면 원래 우변도 이긴다. 우변을 줄이는 교체를 섞으면 결론이 나오지 않는다. 이 수법은 45주차의 \(\varepsilon\)–\(N\) 논증에서 분모를 갈아 끼울 때 다시 쓴다. (검산: \(n = 5\)에서 \(243 > 125\) ✓. \(n = 3\)에서는 \(27 > 27\)이 거짓이므로 \(n_0 = 4\)가 맞다.)
문제 13#
접근. 문제 8\(\cdot\)9와 같은 정리의 사례다(밑 \(a = 7\), 나누는 수 \(a - 1 = 6\)). \(7^{k+1} - 1 = 7(7^k - 1) + 6\)의 잔여 6이 6의 배수이므로 곧바로 닫힌다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(7^1 - 1 = 6\)이고 \(6 = 6 \times 1\)이므로 \(6 \mid 6\) ✓. [귀납] 자연수 \(k\)에 대해 \(6 \mid (7^k - 1)\)이라 가정하자. 재배열하면
이다. 첫 항 \(7(7^k - 1)\)은 귀납 가정과 2주차 훈련 1에 의해 6의 배수이고, 잔여 \(6\)도 6의 배수다. 6의 배수 두 개의 합은 6의 배수이므로(2주차 예제 2.2) \(6 \mid (7^{k+1} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(6 \mid (7^n - 1)\)이다. \(\blacksquare\)
복기. 합동으로 적으면 두 줄이다 — \(7 \equiv 1 \pmod 6\)이므로 31주차 문제 13에 의해 \(7^n \equiv 1\), 곧 \(6 \mid (7^n - 1)\). 문제 9의 비교가 그대로 성립한다. (검산: \(7(7^k-1) + 6 = 7^{k+1} - 1\) ✓. \(n = 2\)에서 \(48 = 6 \times 8\) ✓.)
문제 14#
접근. 지수가 \(2n\)이므로 \(n\)이 1 늘면 지수는 2 는다 — 곱해지는 수가 3이 아니라 \(3^2 = 9\)다. 그 점만 조정하면 나머지는 문제 8\(\cdot\)13과 같은 재배열이고 잔여는 \(9 - 1 = 8\)이 된다.
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 \(3^{2 \cdot 1} - 1 = 9 - 1 = 8\)이고 \(8 \mid 8\) ✓. [귀납] 자연수 \(k\)에 대해 \(8 \mid (3^{2k} - 1)\)이라 가정하자. \(3^{2(k+1)} = 3^{2k+2} = 3^2 \cdot 3^{2k} = 9 \cdot 3^{2k}\)이므로
이다. 첫 항은 귀납 가정과 2주차 훈련 1에 의해 8의 배수이고, 잔여 \(8\)도 8의 배수다. 8의 배수 두 개의 합은 8의 배수이므로(2주차 예제 2.2) \(8 \mid (3^{2(k+1)} - 1)\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 \(8 \mid (3^{2n} - 1)\)이다. \(\blacksquare\)
복기. 이 사실은 17주차 문제 15(“홀수의 제곱을 8로 나눈 나머지는 1”)의 사례이기도 하다 — \(3^{2n} = (3^n)^2\)이고 \(3^n\)은 홀수다. 같은 사실에 이르는 길이 셋이다(귀납, 홀수 제곱의 정리, 합동 \(9 \equiv 1 \pmod 8\)). (검산: \(9(3^{2k}-1) + 8 = 3^{2k+2} - 1\) ✓. \(n = 2\)에서 \(80 = 8 \times 10\) ✓.)
문제 15#
접근. 결론이 “존재한다” 꼴이므로 \(P(k)\)가 주는 표현 \(k = 3a + 5b\)를 고쳐서 \(k+1\)의 표현을 만들어 제시한다. 금액을 1만큼 늘리는 교체는 두 가지다 — 5원 한 장을 3원 두 장으로(\(6 - 5 = 1\)), 3원 세 장을 5원 두 장으로(\(10 - 9 = 1\)). 어느 교체를 쓸 수 있는지는 \(b\)가 1 이상인지에 달렸으므로 귀납 단계 안에서 경우를 나눈다.
풀이. 귀납법으로 증명한다. [기초] \(n = 8\)일 때 \(8 = 3 \cdot 1 + 5 \cdot 1\)이고 \(1, 1\)은 음이 아닌 정수 ✓. [귀납] \(k \ge 8\)인 정수 \(k\)에 대해 \(k = 3a + 5b\)인 음이 아닌 정수 \(a, b\)가 존재한다고 가정하자. 목표는 \(k + 1\)을 같은 꼴로 쓰는 것이다. \(b\)의 값으로 경우를 나눈다. 경우 1: \(b \ge 1\). 5원 한 장을 3원 두 장으로 바꾼다: \(3(a+2) + 5(b-1) = 3a + 6 + 5b - 5 = (3a + 5b) + 1 = k + 1\). \(a + 2 \ge 0\)이고 \(b - 1 \ge 0\)이므로 음이 아닌 정수 계수다 ✓. 경우 2: \(b = 0\). 이때 \(k = 3a\)이고 \(k \ge 8\)이므로 \(3a \ge 8\), 곧 \(a \ge \frac83 > 2\)이고 \(a\)는 정수이므로 \(a \ge 3\)이다. 3원 세 장을 5원 두 장으로 바꾼다: \(3(a-3) + 5 \cdot 2 = 3a - 9 + 10 = 3a + 1 = k + 1\). \(a - 3 \ge 0\)이므로 음이 아닌 정수 계수다 ✓. \(b\)는 음이 아닌 정수이므로 두 경우가 가능한 값을 빠짐없이 덮고, 어느 경우든 \(k+1\)의 표현이 존재한다. 일반화된 귀납 원리에 의해 \(n \ge 8\)인 모든 정수 \(n\)은 \(3a + 5b\) 꼴로 쓰인다. \(\blacksquare\)
복기. 경우 나누기의 채점 기준 두 가지(17주차)를 그대로 확인한다 — ① \(b \ge 1\)과 \(b = 0\)이 전체를 덮는가 ② 각 경우가 각각 \(k+1\)의 표현까지 완결되는가. 그리고 이 증명은 구성적이다: 8의 표현에서 시작해 교체를 반복하면 임의의 \(n\)의 표현이 실제로 손에 들어온다. (검산: \(8 = 3 + 5\) \(\to\) 경우 1로 \(9 = 3 \cdot 3\) \(\to\) 경우 2로 \(10 = 5 \cdot 2\) ✓.) 33주차 문제 8에서 같은 명제를 강한 귀납법으로 다시 증명하고 두 증명을 비교한다.
문제 16#
접근. ①은 마지막 항 분리, ②는 귀납 가정 투입, ③은 연결 부등식 \(\sqrt{k} + \frac{1}{\sqrt{k+1}} \ge \sqrt{k+1}\)이다. 근호가 있는 부등식은 양변을 양수로 곱해 근호를 정리한 뒤 제곱 비교로 넘긴다(16주차).
풀이. 귀납법으로 증명한다. [기초] \(n = 1\)일 때 좌변 \(\frac{1}{\sqrt1} = 1\), 우변 \(\sqrt1 = 1\)이므로 \(1 \ge 1\) ✓. [귀납] 자연수 \(k\)에 대해 \(\sum_{i=1}^{k} \frac{1}{\sqrt i} \ge \sqrt k\)라 가정하자. 목표는 \(\sum_{i=1}^{k+1} \frac{1}{\sqrt i} \ge \sqrt{k+1}\)이다. 마지막 항을 분리하고 귀납 가정을 넣으면(W2)
이다. 연결 부등식: \(\sqrt k + \frac{1}{\sqrt{k+1}} \ge \sqrt{k+1}\)을 보인다. \(\sqrt{k+1} > 0\)이므로 양변에 곱해도 방향이 유지되고(W3), 보일 것은 \(\sqrt{k}\sqrt{k+1} + 1 \ge k + 1\), 곧 양변에서 1을 빼면(W2) \(\sqrt{k(k+1)} \ge k\)이다. 여기서 \(k(k+1) = k^2 + k \ge k^2\)이고 양변이 0 이상이므로, 0 이상인 두 수는 제곱해서 비교해도 된다는 원리(16주차 문제 11의 대우, 16주차 문제 17)에 의해 \(\sqrt{k(k+1)} \ge \sqrt{k^2} = k\)이다. 따라서 연결 부등식이 성립하고, 추이성(W6)에 의해 \(\sum_{i=1}^{k+1} \frac{1}{\sqrt i} \ge \sqrt{k+1}\)이다. 수학적 귀납법에 의해 모든 자연수 \(n\)에 대해 성립한다. \(\blacksquare\)
복기. 문제 10과 나란히 놓으면 대비가 선명하다. \(\sum \frac{1}{i^2}\)은 \(2\) 아래에 갇히고, \(\sum \frac{1}{\sqrt i}\)은 \(\sqrt n\) 위에 있어 한없이 커진다. 분모의 지수 하나(\(i^2\) 대 \(\sqrt i\))가 갈라놓는 이 차이가 46주차 급수의 주제다. (검산: \(n = 2\)에서 좌변 \(1 + \frac{1}{\sqrt2} \approx 1.707\), 우변 \(\sqrt2 \approx 1.414\) ✓.)
문제 17#
접근. 2단 구조의 어느 걸음이 비었는지부터 짚는다. ①과 ②는 제대로 있다 — \(2^{k+1} = 2 \cdot 2^k \ge 2k^2\)은 옳은 줄이다. 비어 있는 것은 ③이고, 그 자리에 “당연하므로”가 들어앉았다. 그다음으로 볼 것은 그 ‘당연’이 실제로 언제부터 참인지다.
풀이. 결함은 연결 부등식 \(2k^2 \ge (k+1)^2\)을 증명 없이 “당연”으로 처리한 것이다. 15주차의 규범과 이번 주 §1.7의 근거 목록에 따르면 증명의 몸통에서 쓸 수 있는 것은 정의\(\cdot\)닫힘성\(\cdot\)등식과 부등식의 성질\(\cdot\)이미 증명한 명제뿐이고, “당연”은 그 어디에도 없다. 게다가 이 부등식은 모든 \(k\)에서 참도 아니다 — \(k = 1\)에서 \(2 \ge 4\)는 거짓이고, \(k = 2\)에서도 \(8 \ge 9\)는 거짓이다. 곧 “\(k\)가 충분히 크면”이 정확히 어디부터인지를 밝히지 않으면 그 범위가 기초 단계의 \(n_0 = 4\)와 맞물리는지 확인할 수 없다(§1.4의 확인 5). 수정. 예제 2.1의 넷째 줄을 삽입한다: 차를 계산하면 \(2k^2 - (k+1)^2 = (k-1)^2 - 2\)이고, \(k \ge 4\)이면 \((k-1)^2 \ge 9 > 2\)이므로 차는 양수다. 이로써 연결 부등식이 \(k \ge 4\)에서 성립함이 확인되고, 기초 단계의 \(n_0 = 4\)와 맞물린다.
복기. 이 답안이 그럴듯한 이유는 ①②가 한 줄도 틀리지 않았기 때문이다. 결함은 계산이 아니라 비어 있는 걸음에 있다. 귀납 답안을 검사할 때는 계산을 따라가기 전에 세 걸음이 모두 적혀 있는지부터 센다. 35주차의 판별 시험에서 이 유형이 “4관 — 연결 부등식 생략”으로 다시 나온다.
문제 18#
접근. 기초의 출발점이 \(n_0 = 0\)이라는 점을 먼저 확인한다. 지수가 \(2n+1\)이므로 \(n\)이 1 늘면 지수는 2 늘고, 곱해지는 수는 \(10^2 = 100\)이다. 재배열하면 \(100(10^{2k+1} + 1)\)을 만들 때 \(+100\)이 생기므로 \(+1\)과 맞추려면 99를 빼야 한다 — 잔여가 음수인 것이 훈련 3과 다른 점이고, 그래서 합이 아니라 차를 쓴다.
풀이. 귀납법으로 증명한다. [기초] \(n = 0\)일 때 \(10^{2 \cdot 0 + 1} + 1 = 10 + 1 = 11\)이고 \(11 \mid 11\) ✓. [귀납] \(k \ge 0\)인 정수 \(k\)에 대해 \(11 \mid (10^{2k+1} + 1)\)이라 가정하자. \(2(k+1) + 1 = 2k + 3\)이고 \(10^{2k+3} = 10^2 \cdot 10^{2k+1} = 100 \cdot 10^{2k+1}\)이므로
이다. 첫 항은 귀납 가정과 2주차 훈련 1에 의해 11의 배수이고, \(99 = 11 \times 9\)이므로 99도 11의 배수다. 11의 배수 두 개의 차는 11의 배수이므로(2주차 문제 7) \(11 \mid \big(10^{2(k+1)+1} + 1\big)\)이다. 일반화된 귀납 원리에 의해 \(n \ge 0\)인 모든 정수 \(n\)에 대해 \(11 \mid \big(10^{2n+1} + 1\big)\)이다. \(\blacksquare\)
복기. 검산: \(100(10^{2k+1} + 1) - 99 = 100 \cdot 10^{2k+1} + 100 - 99 = 10^{2k+3} + 1\) ✓. 잔여가 음수일 때는 “합이 배수”(2주차 예제 2.2)가 아니라 “차가 배수”(2주차 문제 7)를 인용해야 한다 — 인용할 정리를 잔여의 부호가 정한다. 이 명제는 11의 배수 판정법(“교대 자릿수 합”)의 씨앗이다: \(10 \equiv -1 \pmod{11}\)이라 홀수 거듭제곱이 \(-1\)이 되고, 그래서 \(10^{2n+1} + 1 \equiv 0\)이다. (검산: \(n = 2\)에서 \(10^5 + 1 = 100001 = 11 \times 9091\) ✓.)
문제 19#
접근. (a)는 두 증명문에서 “~에 의해”, “~이므로”가 붙은 인용을 전부 뽑아 적으면 된다. (b)는 \(30\)을 소인수로 쪼개 보고 각 스타일에서 무엇이 늘어나는지 비교한다 — 조립은 부품 개수가 늘고, 귀납은 전개의 크기가 는다.
풀이. (a) 부품 목록. 조립 증명(30주차 문제 17)이 쓴 것: 17주차 문제 7(\(2 \mid (n^3 - n)\)), 17주차 예제 2.1(\(3 \mid (n^3 - n)\)), 20주차 문제 13(”\(2 \mid x\)이고 \(3 \mid x\)이면 \(6 \mid x\)”). 기성 부품 셋을 인용하고 자체 계산은 하지 않는다. 귀납 증명(예제 2.2)이 쓴 것: 1주차 문제 16(연속한 두 정수의 곱은 짝수), 2주차 예제 2.2(배수 두 개의 합은 배수), 그리고 자체 전개 \((k+1)^3 - (k+1) = (k^3 - k) + 3k(k+1)\). 저수준 부품 둘에 자체 전개를 더한 구조다. (b) \(30 \mid (n^5 - n)\)은 조립 스타일이 유망하다. \(30 = 2 \cdot 3 \cdot 5\)이므로 “\(2 \mid\), \(3 \mid\), \(5 \mid\)을 각각 보이고 결합한다”는 구조가 그대로 확장되는 반면, 귀납은 \((k+1)^5\) 전개가 여섯 항으로 늘어 잔여를 30의 배수로 정리하는 작업이 크게 번거로워진다.
복기. 두 증명의 성격 차이를 한 줄로 정리하면 — 조립은 부품이 갖춰져 있을 때 짧고, 귀납은 부품이 없을 때 자급자족한다. 어느 쪽이 “더 좋은가”는 정리 자체가 아니라 그 시점에 손에 있는 부품 목록이 정한다. (참고: \(n^5 - n = n(n^2 - 1)(n^2 + 1) = (n-1)n(n+1)(n^2+1)\)로 인수분해되므로 \(2 \mid\)와 \(3 \mid\)은 연속 정수 곱에서 곧바로 나오고, \(5 \mid\)은 \(n\)을 5로 나눈 나머지로 경우를 나누면 된다.)
문제 20#
접근. (a)는 §1.4의 절차를 세 단계로 적는다. (b)는 §1.1에서 확인한 차이 — 등식 귀납에는 남는 명제가 없고 부등식 귀납에는 있다 — 를 두 문장으로 압축한다.
풀이. (예시 답안) (a) ① 작은 값을 차례로 대입해 성립/실패 표를 만든다. ② 실패가 끝나고 계속 성립하기 시작하는 첫 지점을 \(n_0\) 후보로 잡는다(도중에 한 번 실패하면 그 앞의 성립은 고립된 것으로 보고 버린다). ③ 귀납 단계의 연결 부등식이 요구하는 \(k\)의 범위를 계산해 \(n_0\)과 맞물리는지 확인한다 — 요구 범위가 \(n_0\)보다 넓으면 그대로 두고, 좁으면 \(n_0\)을 그 값까지 올린 뒤 새 \(n_0\)에서 기초 단계를 다시 확인한다. 곧 \(n_0\)은 실험이 준 값과 연결부가 요구하는 값 중 큰 쪽이다. (b) 등식 귀납에서는 귀납 가정을 투입한 뒤 목표까지가 항등식 변형이라 길이 하나뿐이고 변형을 끝까지 밀면 반드시 닫힌다. 부등식 귀납에서는 귀납 가정이 데려다주는 중간값과 목표 사이에 독립적으로 참임을 보여야 하는 새 부등식이 남고, 그 부등식은 자동으로 참이 아니므로(\(k\)에 따라 거짓일 수 있으므로) 그 존재를 잊는 것이 부등식 귀납 특유의 함정이다.
복기. (b)를 스스로 검사하는 방법: 완성한 증명에서 부등호를 하나씩 짚으며 “이 부등호의 근거는 무엇인가”를 묻는다. 근거가 “귀납 가정”인 부등호와 “(W1)~(W6) 중 하나”인 부등호가 각각 최소 하나씩 있어야 정상이다. 후자가 없다면 연결 부등식을 빼먹은 것이다.
다음 주 예고: 귀납 가정을 “직전 하나”가 아니라 “지금까지 전부”로 강화한 강한 귀납법, 그리고 귀납법의 쌍둥이 원리인 최소원리(최소 반례법)를 배운다. 21주차에서 증명 없이 인정하고 썼던 두 사실 — “모든 유리수는 기약분수로 쓸 수 있다”, “2 이상의 정수는 소수인 약수를 가진다” — 의 빚을 갚고, 17주차에서 인정하고 쓴 나눗셈 정리도 증명한다. 이번 주의 세 걸음은 그대로 쓰인다 — 달라지는 것은 ②에서 꺼내 쓸 수 있는 가정의 크기뿐이다.