# 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}$ | :::{container} quotebox **확인 10.** 도착점 칸의 빈칸을 채워 보자. $P(n)$이 "$2^n \ge n^2$"일 때 $P(k+1)$은 어떤 부등식인가. ::: :::{admonition} 답 :class: quotebox dropdown $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주차 서식대로 가정을 선언하고 목표를 미리 적는다. :::{container} quotebox **확인 11.** 둘째 문장을 완성해 보자: "$k \ge \underline{\quad}$인 정수 $k$에 대해 $\underline{\qquad}$이라 가정하자. 목표는 $\underline{\qquad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown "$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$가 보이도록 쪼갠 뒤 가정을 끼운다. :::{container} quotebox **확인 12.** 셋째 문장을 완성해 보자: "$2^{k+1} = \underline{\quad} \cdot 2^k \ge \underline{\quad}$ (귀납 가정)." 부등호의 근거는 (W1)~(W6) 중 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown "$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주차의 표준 수법은 차를 계산해 부호를 판정하는 것이다. :::{container} quotebox **확인 13.** 연결 부등식으로 무엇을 증명해야 하는가. 그리고 차 $2k^2 - (k+1)^2$을 전개해 정리해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 증명할 것은 $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)로 부호를 판정할 수 있다. ::: :::{container} quotebox **확인 14.** $(k-1)^2 - 2 > 0$을 보이려면 $k$에 어떤 조건이 필요한가. 가정 $k \ge 4$가 소비되는 지점이 정확히 어디인지 짚어 보자. ::: :::{admonition} 답 :class: quotebox dropdown $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단계 — 이어 붙이고 마감한다.** 두 부등호를 추이성으로 잇고 원리를 인용한다. :::{container} quotebox **확인 15.** 마지막 두 문장을 완성해 보자: "따라서 $2^{k+1} \ge \underline{\quad} \ge \underline{\qquad}$이다. $\underline{\qquad}$에 의해 $n \ge 4$인 모든 정수 $n$에 대해 $2^n \ge n^2$이다. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown "따라서 $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를 넣어 읽어 보자. :::{container} quotebox **확인 16.** $k = 4$일 때 셋째 줄과 다섯째 줄은 각각 어떤 수의 부등식이 되는가. 등호가 나타나는 자리가 있는지도 확인해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 셋째 줄은 $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)를 조립했다. 이번에는 귀납으로 다시 증명한다 — 같은 정리의 두 번째 증명이다. 이번에는 설계만 함께 하고, 증명은 완성된 산문으로 본다. :::{container} quotebox **확인 17.** 번역표를 채워 보자. 기초 단계에서 확인할 것은 무엇이고, 귀납 단계의 출발점과 도착점은 각각 어떤 문장인가. ::: :::{admonition} 답 :class: quotebox dropdown 기초 단계: $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{정수})$ 꼴을 만든다. ::: :::{container} quotebox **확인 18.** ① 걸음을 수행해 보자. $(k+1)^3 - (k+1)$을 전개한 뒤 $k^3 - k$를 떼어 내면 무엇이 남는가. ::: :::{admonition} 답 :class: quotebox dropdown $(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+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k(k+1) $$ 이다. 첫 항 $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$을 실험으로 정한다 ② 귀납 단계의 세 걸음(①②③)을 각각 적는다. :::{container} quotebox **확인 19.** (가) $n = 1, 2, 3, 4$에서 $n!$과 $2^n$을 비교해 $n_0$을 정해 보자. (나) ① 변형, ② 귀납 가정 투입 후 중간값, ③ 연결 부등식을 각각 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (가) $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)! = (k+1) \cdot 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 \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}$ | :::{container} quotebox **확인 20.** 대응표의 빈칸 (1)(2)(3)을 예제 2.2의 증명에서 찾아 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (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$ 잔여의 배수 판정), 자리와 임무는 같다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **귀납 단계의 세 걸음** ① $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^{k+1} - 1 = 6 \cdot 6^k - 1 = 6(6^k - 1) + \underline{\quad(1)\quad} $$ 이다. 첫 항 $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$이다. 그러면 $$ 2^{k+1} = 2 \cdot 2^k \ge 2(\underline{\quad(2)\quad}) = 2k + 2 $$ 이고, 이 부등호의 근거는 $\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의 번역표(무대 / 기초 / 출발점 / 도착점)부터 채우고 시작한다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "$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$ 실험) :::{admonition} 힌트 :class: quotebox dropdown 표를 만들어 좌변과 우변을 각각 계산한 뒤 ✓/✗를 적는다. §1.4의 표가 양식이다. "계속 성립하기 시작하는 첫 지점"을 묻고 있으므로, 도중에 한 번 ✗가 나오면 그 앞의 ✓들은 고립된 성립으로 보고 지나간다. ::: **2.** [백지] 부등식 귀납의 2단 구조(①②③)와 "연결 부등식" 개념을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown ①은 무엇을 드러내기 위한 변형인가, ②는 어느 줄에 표시를 다는가, ③은 어떤 근거로 증명하는가 — 세 물음에 각각 한 줄씩 답하면 된다. ::: **3.** 모든 자연수 $n$에 대해 $3^n \ge 2n + 1$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown ① $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$)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 막히는 자리는 대개 재배열 한 줄이다. $6 \cdot 6^k - 1$에서 $6(6^k - 1)$을 만들면 $-6$이 되므로 $-1$과 맞추려면 얼마를 되돌려 주어야 하는가. ::: **5.** 예제 2.1($2^n \ge n^2$, $n \ge 4$)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 다섯 줄이다. 기초 / 가정 선언 + 목표 / ①② / ③ 연결 부등식 / 이어 붙이기. 연결 부등식의 차를 완전제곱으로 만드는 줄과, 거기서 $k \ge 4$를 쓰는 줄을 빠뜨리지 않았는지 스스로 채점한다. ::: **6.** 예제 2.2($6 \mid n^3 - n$ 귀납)를 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 전개 뒤 잔여를 $3k(k+1)$로 **묶는** 것이 관건이다. 묶고 나면 물을 것이 하나뿐이다 — $k(k+1)$이 짝수인 근거는 어느 문제였는가. ::: ### 표준 ●●○ **7.** $n \ge 1$인 모든 자연수에 대해 $n! \ge 2^{n-1}$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 기초는 $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)으로 각각 증명하고 두 증명을 비교하시오. :::{admonition} 합에 대한 부등식 귀납 — 문제 10과 16에서 처음 쓴다 :class: quotebox 좌변이 $\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}$ — 통분해 비교) :::{admonition} 힌트 :class: quotebox dropdown 우변의 $\frac1k - \frac{1}{k+1}$을 통분하면 $\frac{1}{k(k+1)}$이다 (31주차 문제 10에서 쓴 분해와 같은 등식). 그러면 비교할 것은 $\frac{1}{(k+1)^2}$과 $\frac{1}{k(k+1)}$뿐이고, 분자가 같으므로 분모만 본다. ::: :::{admonition} 무대가 실수로 넓어진다 — 문제 11 :class: quotebox 지금까지의 귀납은 전부 정수 위의 명제였다. 베르누이 부등식에는 실수 $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$이 귀납 단계 어디서 소비되는지 명시하시오. :::{admonition} 힌트 :class: quotebox dropdown ① 걸음은 $(1+x)^{k+1} = (1+x)^k (1+x)$이다. ②에서 귀납 가정의 양변에 $(1+x)$를 곱하는데, (W3)을 쓰려면 곱하는 수의 **부호**를 알아야 한다 — 그 부호를 보장하는 것이 조건 $x \ge -1$이다. ③에서는 전개한 뒤 남는 항 $kx^2$의 부호를 (W1)로 판정한다. ::: :::{admonition} 연결 부등식의 우변을 갈아 끼운다 — 문제 12에서 처음 쓴다 :class: quotebox 연결 부등식의 우변이 삼항식처럼 복잡하면 직접 비교가 번거롭다. 이때 **눌러놓기**를 쓴다 — 복잡한 우변을 그보다 크거나 같은 간단한 식으로 교체해 비교를 단순화하는 수법이다. 방향 규칙이 하나 있다: **우변을 키우는 교체만 섞는다.** 새 우변을 이기면 원래 우변도 (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$을 쓰라) :::{admonition} 힌트 :class: quotebox dropdown $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}$) :::{admonition} 힌트 :class: quotebox dropdown 지수가 $2n$이므로 $n$이 1 늘면 지수는 2 는다 — 그래서 곱해지는 수가 3이 아니라 $3^2 = 9$다. 나머지는 훈련 1과 같은 재배열이다: $9 \cdot 3^{2k} - 1 = 9(3^{2k} - 1) + \underline{\quad}$의 빈칸을 채운다. ::: ### 도전 ●●● :::{admonition} 귀납 단계 안에서 경우를 나눈다 — 문제 15 :class: quotebox 지금까지의 귀납 단계는 한 줄기였다. 문제 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$ 교체. 케이스 안의 케이스다.) :::{admonition} 힌트 :class: quotebox dropdown 교체가 왜 $+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주차 제곱 비교로) :::{admonition} 힌트 :class: quotebox dropdown 양변에 $\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.** (진단) 다음 답안의 결함을 지적하시오. :::{container} quotebox "명제: $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$) :::{admonition} 힌트 :class: quotebox dropdown 기초 단계의 출발점이 $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$"을 증명하고 싶다면 어느 스타일이 더 유망해 보이는지, 이유와 함께 한 문장으로 쓰시오 (증명은 하지 않아도 됨). :::{admonition} 힌트 :class: quotebox dropdown (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) — 곱하는 수의 부호를 먼저 확인하고, 두 부등호의 방향을 맞춘다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 준비 운동 1. 두 단계는 **기초 단계**와 **귀납 단계**다. 사용 지점 표시가 필요한 이유: 표시가 없으면 그 증명이 귀납 가정을 실제로 썼는지 검사할 수 없고, 쓰지 않았다면 애초에 귀납이 필요 없는 명제였다는 뜻이 된다(31주차 문제 20). 1. $2 \cdot 2^k > 2k = k + k \ge k + 1$ — 마지막 부등호가 연결 부등식이고, 근거는 $k \ge 1$이다. 이 한 걸음이 이번 주 내내 반복된다. 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), $$ 3^{k+1} = 3 \cdot 3^k \ge 3(2k + 1) = 6k + 3 $$ 이다(가운데 부등호가 귀납 가정). **연결 부등식**: $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^{k+1} - 1 = 6 \cdot 6^k - 1 = (6 \cdot 6^k - 6) + 5 = 6(6^k - 1) + 5 $$ 이다. 첫 항 $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)에 의해 $$ 2^{k+1} = 2 \cdot 2^k \ge 2k^2 $$ 이다(부등호가 귀납 가정). **연결 부등식**: $2k^2 \ge (k+1)^2$을 보인다. 차를 계산하면 $$ 2k^2 - (k+1)^2 = 2k^2 - k^2 - 2k - 1 = k^2 - 2k - 1 = (k-1)^2 - 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+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3k^2 + 3k = (k^3 - k) + 3k(k+1) $$ 이다. 첫 항 $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)! = (k+1) \cdot k! \ge (k+1) \cdot 2^{k-1} $$ 이다(부등호가 귀납 가정). **연결 부등식**: $(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^{k+1} - 1 = 5 \cdot 5^k - 1 = (5 \cdot 5^k - 5) + 4 = 5(5^k - 1) + 4 $$ 이다. 첫 항 $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)$이라 가정하자. 재배열하면 $$ 8^{k+1} - 1 = 8 \cdot 8^k - 1 = (8 \cdot 8^k - 8) + 7 = 8(8^k - 1) + 7 $$ 이다. 첫 항은 귀납 가정과 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) $$ \sum_{i=1}^{k+1} \frac{1}{i^2} = \sum_{i=1}^{k} \frac{1}{i^2} + \frac{1}{(k+1)^2} \le \left(2 - \frac1k\right) + \frac{1}{(k+1)^2} $$ 이다. **연결 부등식**: $\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) $$ \frac{k(k+1)}{k(k+1)(k+1)^2} < \frac{(k+1)^2}{k(k+1)(k+1)^2}, \qquad \text{곧} \quad \frac{1}{(k+1)^2} < \frac{1}{k(k+1)} $$ 이다. 따라서 $$ \sum_{i=1}^{k+1} \frac{1}{i^2} \le 2 - \frac1k + \frac1k - \frac{1}{k+1} = 2 - \frac{1}{k+1} $$ 이다. 수학적 귀납법에 의해 모든 자연수 $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+x)^{k+1} = (1+x)^k (1+x) \ge (1 + kx)(1 + x) $$ **연결 부등식**: $(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$이므로 $$ 3k^2 + 3k + 1 \le 3k^2 + 3k^2 + k^2 = 7k^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^{k+1} - 1 = 7 \cdot 7^k - 1 = (7 \cdot 7^k - 7) + 6 = 7(7^k - 1) + 6 $$ 이다. 첫 항 $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}$이므로 $$ 3^{2(k+1)} - 1 = 9 \cdot 3^{2k} - 1 = (9 \cdot 3^{2k} - 9) + 8 = 9\big(3^{2k} - 1\big) + 8 $$ 이다. 첫 항은 귀납 가정과 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) $$ \sum_{i=1}^{k+1} \frac{1}{\sqrt i} = \sum_{i=1}^{k} \frac{1}{\sqrt i} + \frac{1}{\sqrt{k+1}} \ge \sqrt k + \frac{1}{\sqrt{k+1}} $$ 이다. **연결 부등식**: $\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}$이므로 $$ 10^{2(k+1)+1} + 1 = 100 \cdot 10^{2k+1} + 1 = \big(100 \cdot 10^{2k+1} + 100\big) - 99 = 100\big(10^{2k+1} + 1\big) - 99 $$ 이다. 첫 항은 귀납 가정과 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주차에서 인정하고 쓴 나눗셈 정리도 증명한다. 이번 주의 세 걸음은 그대로 쓰인다 — 달라지는 것은 ②에서 꺼내 쓸 수 있는 가정의 크기뿐이다.