# 32주차 — 귀납법 연습: 부등식과 나누어떨어짐 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 부등식 귀납은 2단 구조다 — 귀납 가정이 데려다주는 중간값까지가 절반이고, 거기서 목표까지는 연결 부등식으로 따로 놓는다. **이 주의 위치**: 50주 과정의 32주차. 31주차에서 세운 귀납법 서식을 등식이 아닌 명제 — 부등식과 나누어떨어짐 — 에 적용한다. **원서 대응**: BoP(Book of Proof) 10장의 부등식$\cdot$나누어떨어짐 연습문제군. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 부등식 귀납의 2단 구조(귀납 가정 투입 $\to$ 연결 부등식)를 백지에 쓰고, 증명 안에서 두 단을 손가락으로 짚을 수 있다. 1. 기초 단계가 1이 아닌 귀납($n \ge 4$부터 등)을 다룬다 — $2^n \ge n^2$, $3^n > n^3$, $n! > 2^n$. 기초의 위치 $n_0$을 실험으로 정하고, 연결 부등식이 요구하는 범위와 맞물리는지 확인한다. 1. 나누어떨어짐 귀납의 표준 수("$f(k)$의 배수 항을 강제로 만들고 잔여를 확인한다")를 익힌다. 1. 베르누이 부등식을 확보한다 — 46주차의 급수(문제 16, $r^n \to 0$)에서 부품으로 쓴다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (31주차 복습) 1. 귀납법 서식의 두 단계 이름을 쓰고, "귀납 가정을 사용한 지점에 표시를 단다"는 규칙이 왜 필요한지 한 문장으로 쓰시오. 1. $n < 2^n$의 귀납 단계를 재현하시오 (31주차 문제 16). 특히 $2 \cdot 2^k > 2k$ 다음에 무엇을 적었는지 기억해 보자. 1. 16주차의 부등식 기본 성질 (W1)~(W6) 중 (W1)$\cdot$(W3)$\cdot$(W4)$\cdot$(W6)을 쓰시오. 이번 주 연결 부등식의 근거는 전부 이 넷에서 나온다. 답을 노트에 적어 둔다. 2번이 이번 주 전체의 축이다. ### 자주 나오는 세 가지 답 — 2번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 귀납 가정까지만.** "$2^{k+1} = 2 \cdot 2^k > 2k$"까지 적고 멈춘다. 그 줄은 옳다 — 귀납 가정을 정확한 자리에 정확한 근거((W3), 양변에 양수 2를 곱함)로 투입했다. 빠진 것은 그다음이다: 목표는 $k+1$인데 손에 있는 것은 $2k$이고, $2k$에서 $k+1$까지는 아직 한 걸음이 남아 있다. - **유형 2 — 목표를 근거 자리에 놓기.** "$2^{k+1} > k+1$이어야 하므로 $2k \ge k+1$이다"처럼 결론에서 거꾸로 적는다. 도착점을 보고 있다는 점은 옳다 — 설계 단계에서는 오히려 그렇게 생각해야 한다. 문제는 증명문에서 아직 확보되지 않은 것("$2^{k+1} > k+1$")을 근거 자리에 놓았다는 점이다. 설계에서 거꾸로 찾은 것을 증명문에서는 바로 세워 적는다. - **유형 3 — 범위 없이 단언.** "$2k \ge k+1$은 당연하다"고 적는다. 부등식 자체는 참이다. 빠진 것은 성립 범위와 근거다 — 차를 계산하면 $2k - (k+1) = k - 1$이고, 이것이 0 이상이 되는 것은 $k \ge 1$일 때다. 이번 주에는 "당연하다"가 근거 목록에 없다는 점이 반복해서 문제가 된다 (문제 17이 그 진단이다). ## 개념 — 두 종류의 귀납 단계 ### 1 등식 귀납의 절차를 그대로 쓰면 어디서 막히는가 31주차의 예제는 전부 등식이었다. 예제 2.1(가우스의 합 공식)의 귀납 단계는 "마지막 항을 분리한다 $\to$ 귀납 가정을 대입한다 $\to$ 대수 변형으로 목표 꼴을 만든다"로 끝났고, 마지막 변형은 전부 항등식이었다. 부등식이 나온 곳은 문제 16 ($n < 2^n$) 한 곳뿐이고, 거기서 이미 한 걸음을 더 밟아야 했다 — $2 \cdot 2^k > 2k$ 다음에 $2k \ge k+1$을 따로 세운 그 걸음이다. 이번 주에는 그 한 걸음이 무엇이었는지에 이름을 붙이고, 등식 귀납의 절차만으로는 왜 닿지 않는지를 일반화한다. 같은 절차를 부등식 명제에 그대로 밀어붙여 보자. 소재는 29주차 문제 8(b)에서 실험으로 범위만 제안해 두고 증명을 미뤄 둔 명제다. :::{admonition} 시도 — 등식 귀납의 절차를 그대로 :class: quotebox 명제: $n \ge 4$인 모든 정수 $n$에 대해 $2^n \ge n^2$. "$2^k \ge k^2$이라 가정하자. 목표는 $2^{k+1} \ge (k+1)^2$이다. $2^{k+1} = 2 \cdot 2^k \ge 2k^2$ (귀납 가정). 그러므로 $2^{k+1} \ge \dots$ " ::: 여기서 멈춘다. 손에 들어온 것은 $2^{k+1} \ge 2k^2$인데, 적어야 할 것은 $2^{k+1} \ge (k+1)^2$이다. 그런데 $2k^2$과 $(k+1)^2$은 **같은 식이 아니다**. 31주차 예제에서는 이 자리에 항등식이 있어서 변형만 하면 도착했지만, 지금은 변형으로 이을 수 없는 두 식이 마주 보고 있다. :::{container} quotebox **확인 1.** 멈춘 자리에서 결론이 나오려면 $2k^2$과 $(k+1)^2$ 사이에 무엇이 있어야 하는가. 그리고 그것이 저절로 성립하는지 $k = 1$을 넣어 확인해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $2k^2 \ge (k+1)^2$이라는 **부등식 하나**가 더 있어야 한다. 그것이 있으면 부등호의 추이성 (W6)으로 $2^{k+1} \ge 2k^2 \ge (k+1)^2$이 이어진다. 저절로 성립하지는 않는다: $k = 1$에서 $2k^2 = 2$이고 $(k+1)^2 = 4$이므로 $2 \ge 4$는 거짓이다. 곧 이 부등식은 **따로 증명해야 하는 새 명제**이고, 참이 되는 $k$의 범위도 따로 확인해야 한다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 등식 귀납에서는 귀납 가정을 투입한 뒤 남는 것이 항등식이라 변형만 하면 닫힌다. 부등식 귀납에서는 귀납 가정이 데려다준 **중간값**과 목표 사이에, 독립적으로 참임을 보여야 하는 부등식이 남는다. ::: ### 2 남는 부등식의 정체 — 사례 표를 채워 보자 같은 자리가 다른 명제에서도 나타나는지 확인한다. 세 명제의 귀납 단계를 한 표에 늘어놓고 빈칸을 채워 보자. | **명제** | **① $A_{k+1}$을 $A_k$가 보이게** | **② 귀납 가정 투입 후 중간값** | **목표 $B_{k+1}$** | **③ 남는 부등식** | |---|---|---|---|---| | $n < 2^n$ (31주차 문제 16) | $2^{k+1} = 2 \cdot 2^k$ | $2k$ | $k+1$ | $2k \ge k+1$ | | $2^n \ge n^2$ | $2^{k+1} = 2 \cdot 2^k$ | $\underline{\quad(1)\quad}$ | $(k+1)^2$ | $\underline{\quad(2)\quad}$ | | $n! > 2^n$ | $(k+1)! = (k+1) \cdot k!$ | $\underline{\quad(3)\quad}$ | $2^{k+1}$ | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(4)를 채우고, 세 줄에 공통으로 나타나는 걸음의 개수를 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $2k^2$ (2) $2k^2 \ge (k+1)^2$ (3) $(k+1) \cdot 2^k$ (4) $(k+1)2^k \ge 2^{k+1}$, 곧 양변을 $2^k > 0$으로 나누면 $k + 1 \ge 2$. 공통으로 나타나는 걸음은 **셋**이다 — ① 변형, ② 귀납 가정 투입, ③ 남는 부등식. 셋째 걸음의 난이도는 줄마다 다르다(첫 줄과 셋째 줄은 한 줄, 둘째 줄은 차를 계산해야 한다). 그러나 **셋째 걸음이 있다는 사실 자체는 세 줄 모두 같다.** ::: 이 관찰에 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 일을 문장으로 굳혔을 뿐이다. :::{admonition} 백지 암기 대상 :class: keybox **부등식 귀납의 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!$). ② **귀납 가정 투입**: $A_k \ge B_k$를 끼워 중간값까지 온다. 이 줄에 "(귀납 가정)" 표시를 단다. ③ **연결 부등식**: "중간값 $\ge B_{k+1}$"을 **별도로 증명한다** — 여기는 귀납이 아니라 16주차의 (W1)~(W6)과 대수의 몫이다. ::: $$ A_{k+1} \;\overset{\text{①}}{=}\; c \cdot A_k \;\overset{\text{② IH}}{\ge}\; c \cdot B_k \;\overset{\text{③ 연결}}{\ge}\; B_{k+1} $$ "2단"이라 부르는 이유는 ②와 ③이 서로 다른 성격의 단계이기 때문이다. ②는 귀납이 주는 것이고, ③은 이번 $k$에서 손으로 증명하는 보통의 부등식 문제다. :::{admonition} 표기 — $n!$과 그 재귀 :class: quotebox $n!$은 "엔 팩토리얼"로 읽고 $1 \times 2 \times \cdots \times n$을 뜻한다. 이번 주에 쓰는 성질은 하나뿐이다: $(k+1)! = (k+1) \cdot k!$. 이 등식이 위 표의 ① 칸에서 $A_k = k!$을 드러내는 도구다. ::: ### 3 2단 구조 해부 — 걸음마다 하는 일 세 걸음은 증명에서 각각 다른 임무를 맡는다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | ① $A_{k+1}$ 변형 | $A_k$를 식 안에 등장시킨다 | 귀납 가정을 끼워 넣을 자리를 만든다. 이 걸음이 없으면 가정을 쓸 곳이 없다 | | ② 귀납 가정 투입 | 부등호 하나를 확보한다 | 31주차 서식대로 "(귀납 가정)" 표시를 단다 — 이 표시가 없으면 귀납이 필요했는지 검사할 수 없다 | | ③ 연결 부등식 | 중간값에서 목표까지 | 귀납과 무관한 **독립 명제**. 근거는 (W1)~(W6)과 대수 | | 방향 점검 | ②와 ③의 부등호 방향 확인 | 두 부등호의 방향이 같아야 (W6) 추이성으로 이어 붙일 수 있다 | **조각 삭제 실험.** 셋째 걸음을 지우고 "$2^{k+1} \ge 2k^2$이므로 $2^{k+1} \ge (k+1)^2$"이라고 적어 보자. $k = 2$를 넣으면 앞의 전제 $2^3 = 8 \ge 2 \cdot 2^2 = 8$은 참인데, 지운 채로 적은 결론 $2^{k+1} \ge (k+1)^2$은 $8 \ge 9$로 **거짓**이다. 곧 중간값 $2k^2 = 8$이 목표 $(k+1)^2 = 9$보다 작은 상황이 실제로 존재하고, 그런 $k$에서는 $2^{k+1} \ge 2k^2$이라는 정보만으로 $2^{k+1} \ge (k+1)^2$이 따라 나오지 않는다 — 참인 전제에서 거짓인 결론이 나온 셈이다. :::{container} quotebox **확인 3.** 셋째 걸음을 지우면 정확히 무엇이 무너지는가. "$A \ge B$이고 $C \le B$이면 $A \ge C$"와 "$A \ge B$이고 $C \ge B$이면 $A \ge C$" 중 어느 쪽이 참인지와 함께 생각해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 앞쪽만 참이다 — 추이성 (W6)은 부등호가 **한 방향으로 이어질 때만** 작동한다. 셋째 걸음을 지우면 중간값 $2k^2$이 목표 $(k+1)^2$ 위에 있는지 아래에 있는지가 미확정인 채 남고, 아래에 있는 $k$에서는 아무 결론도 나오지 않는다. 곧 무너지는 것은 결론 한 줄이 아니라 **귀납 단계 전체**다: $P(k) \Rightarrow P(k+1)$이 증명되지 않았으므로 전달이 끊기고, 기초 단계만 남는다. 이 결함을 실제 답안에서 찾아내는 것이 문제 17이다. ::: ### 4 기초 단계의 위치 — 실험으로 $n_0$을 정한다 31주차의 원리 상자는 $P(1)$로 적혀 있었고, 시작점을 옮겨도 된다는 것은 본문에서 말로만 다루었다(31주차 §1.3 — 거기서도 예제 2.3과 문제 11$\cdot$14$\cdot$18은 각각 $0$, $0$, $2$, $0$에서 시작했다). 이번 주에는 그것을 $n_0$이 들어간 정식 원리로 승격하고, $n_0$을 실험으로 정하는 절차까지 붙인다. :::{admonition} 표기 — $n_0$ :class: quotebox $n_0$은 "엔 제로"로 읽고, 귀납이 출발하는 첫 번호를 가리키는 이름이다. 아래 첨자는 변수 $n$의 특정한 값 하나를 지목할 때 쓴다. ::: 절차의 첫 걸음은 실험이다. 이번 주의 $2^n \ge n^2$에 작은 값을 넣어 표를 채워 보자. | **$n$** | **$2^n$** | **$n^2$** | **$2^n \ge n^2$** | |---|---|---|---| | $1$ | $2$ | $1$ | ✓ | | $2$ | $4$ | $4$ | ✓ | | $3$ | $8$ | $9$ | ✗ | | $4$ | $16$ | $16$ | $\underline{\quad(1)\quad}$ | | $5$ | $32$ | $25$ | $\underline{\quad(2)\quad}$ | | $6$ | $64$ | $36$ | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 4.** 빈칸 (1)(2)(3)을 채우고, "그 뒤로 계속 성립하는 첫 지점"을 $n_0$이라 할 때 $n_0$을 정해 보자. $n = 1, 2$에서도 성립하는데 $n_0 = 1$로 잡으면 안 되는 이유도 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) ✓ (등호이므로 $\ge$는 성립) (2) ✓ (3) ✓. $n_0 = 4$이다. $n_0 = 1$로 잡으면 안 되는 이유: 귀납법이 주장하는 것은 "$n_0$ 이후 **전부**"인데 $n = 3$에서 명제가 거짓이므로 그 주장이 거짓이 된다. 실제로 $k = 2$에서 $P(k) \Rightarrow P(k+1)$이 무너지므로 전달 장치도 그 자리에서 끊긴다. $n = 1, 2$의 성립은 고립된 성립이고, 귀납이 필요로 하는 것은 끊기지 않는 구간이다. ::: 31주차의 원리 상자는 $n = 1$에서 출발했다. 출발점만 옮기면 그대로 쓸 수 있다. :::{admonition} 백지 암기 대상 :class: keybox **일반화된 귀납 원리 (induction from $n_0$)** 정수 $n_0$과 명제 $P(n)$에 대해, 다음 두 가지가 증명되면 **$n \ge n_0$인 모든 정수 $n$**에 대해 $P(n)$이 참이다. **(기초 단계)** $P(n_0)$이 참이다. **(귀납 단계)** $k \ge n_0$인 모든 정수 $k$에 대해, $P(k)$가 참이면 $P(k+1)$도 참이다. ::: 31주차의 원리에서 달라진 것은 출발 번호 하나뿐이다. 전달 장치가 $n_0$번부터 작동할 뿐 구조는 같다. $n_0$을 정할 때 확인할 것이 하나 더 있다. 귀납 단계의 **연결 부등식이 요구하는 범위**다. 예제 2.1에서 보겠지만 연결 부등식 $2k^2 \ge (k+1)^2$은 $k \ge 3$부터 참이다. 실험이 준 $n_0 = 4$와 연결부가 요구하는 $k \ge 3$이 어긋나지 않는지를 반드시 맞춰 봐야 한다. :::{container} quotebox **확인 5.** 기초를 $n_0 = 4$로 잡았다. (가) 연결 부등식이 $k \ge 3$에서 성립한다면 문제가 되는가. (나) 연결 부등식이 $k \ge 6$에서만 성립한다면 어떻게 되는가. ::: :::{admonition} 답 :class: quotebox dropdown (가) 문제없다. 귀납 단계는 $k \ge 4$에서만 쓰이고 $k \ge 4$이면 $k \ge 3$도 참이므로, 연결부의 요구 범위가 $n_0$보다 넓은 것은 여유일 뿐이다. (나) 결함이 된다. $k = 4, 5$에서 연결 부등식을 쓸 수 없어 $P(4) \Rightarrow P(5)$와 $P(5) \Rightarrow P(6)$이 증명되지 않고 전달이 끊긴다. 처방은 $n_0$을 6으로 올려 $P(6)$을 확인하거나, 연결 부등식을 $k \ge 4$까지 다시 증명하는 것이다. 정리하면 **$n_0$은 실험이 준 값과 연결부가 요구하는 값 중 큰 쪽**이다. ::: ### 5 나누어떨어짐 귀납 — 잔여를 만들어 확인한다 이번에는 소재를 바꾼다. 목표가 부등식이 아니라 "$d \mid f(n)$"인 명제다. 같은 자리에서 같은 막힘이 나타나는지 보자. $5 \mid (6^n - 1)$을 증명하려고 귀납 가정 $5 \mid (6^k - 1)$을 손에 들었다. :::{admonition} 시도 — 가정을 쓸 자리를 찾지 못한 채 :class: quotebox "$5 \mid (6^k - 1)$이라 가정하자. 목표는 $5 \mid (6^{k+1} - 1)$이다. $6^{k+1} - 1$에서 … " ::: 여기서 멈춘다. $6^{k+1} - 1$이라는 식 안에 $6^k - 1$이라는 덩어리가 **보이지 않는다**. 가정은 그 덩어리에 대한 정보인데 식에 그 덩어리가 없으니 끼워 넣을 자리가 없다. 부등식 귀납의 첫째 걸음(① $A_k$가 보이게 변형)이 여기서도 그대로 필요하다는 뜻이다. $6^{k+1} = 6 \cdot 6^k$까지는 쉽다. 문제는 $-1$이다. $6 \cdot 6^k - 1$에서 $6(6^k - 1)$을 강제로 만들면 $6 \cdot 6^k - 6$이 되어 원래의 $-1$보다 5만큼 더 뺀 셈이므로, 5를 되돌려 주어야 한다. 20주차의 **빼고 더하기**가 하던 일이 바로 이것이다. $$ 6^{k+1} - 1 = 6 \cdot 6^k - 1 = (6 \cdot 6^k - 6) + 5 = 6(6^k - 1) + 5 $$ 같은 수를 다른 명제에서도 써 보자. 표의 빈칸을 채운다. | **목표** | **$f(k+1)$** | **$f(k)$가 보이게 재배열** | **잔여** | **잔여가 $d$의 배수인가** | |---|---|---|---|---| | $5 \mid (6^n - 1)$ | $6^{k+1} - 1$ | $6(6^k - 1) + 5$ | $5$ | 예 | | $3 \mid (4^n - 1)$ | $4^{k+1} - 1$ | $4(4^k - 1) + \underline{\quad(1)\quad}$ | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ | | $2 \mid (n^2 + n)$ | $(k+1)^2 + (k+1)$ | $(k^2 + k) + \underline{\quad(3)\quad}$ | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 6.** 빈칸 (1)~(4)를 채워 보자. 셋째 줄은 전개부터 해야 한다: $(k+1)^2 + (k+1)$을 전개해 $k^2 + k$를 떼어 내면 무엇이 남는가. ::: :::{admonition} 답 :class: quotebox dropdown (1) $3$ (2) 예 — $3 = 3 \times 1$이다. (3) $2(k+1)$ (4) 예 — $2 \times (k+1)$이고 $k+1$은 정수다. 셋째 줄의 전개: $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + 3k + 2$이고, 여기서 $k^2 + k$를 떼면 $2k + 2 = 2(k+1)$이 남는다. 세 줄의 공통 절차는 하나다 — **$f(k)$의 배수 항을 강제로 만들고, 남은 잔여가 $d$의 배수인지 확인한다.** ::: 이 절차에 이름을 붙인다. 여기에도 새로운 것은 없다 — 재배열과 확인뿐이다. :::{admonition} 백지 암기 대상 :class: keybox **나누어떨어짐 귀납의 표준 수** 목표가 $d \mid f(k+1)$이고 가정이 $d \mid f(k)$일 때: ① $f(k+1)$을 "$f(k)$의 정수배 $+$ 잔여" 꼴로 재배열한다 (필요하면 20주차의 빼고 더하기). ② 첫 항은 귀납 가정과 "배수의 정수배는 배수"(2주차 훈련 1)에 의해 $d$의 배수다. ③ 잔여가 $d$의 배수인지 확인한다. ④ $d$의 배수 두 개의 합(또는 차)은 $d$의 배수이므로(2주차 예제 2.2, 문제 7) 결론이 나온다. ::: ② 걸음이 부등식 귀납의 "귀납 가정 투입"에 해당하고, ③ 걸음이 "연결 부등식"에 해당한다. 소재가 달라도 귀납 단계의 뼈대는 같다. 빼고 더하기는 손이 미끄러지기 쉬운 변형이다. 검산 한 줄을 붙이는 습관을 들인다. :::{container} quotebox **확인 7.** $6(6^k - 1) + 5$를 도로 전개해서 $6^{k+1} - 1$이 되는지 확인해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $6(6^k - 1) + 5 = 6 \cdot 6^k - 6 + 5 = 6^{k+1} - 1$ ✓. 재배열은 등식이어야 한다 — 값이 달라졌다면 증명이 아니라 계산 실수다. 이 역전개 검산은 문제 8, 13, 14, 18에서 매번 한 줄로 붙인다. ::: ### 6 같은 사실의 두 언어 — 합동으로 적으면 $5 \mid (6^n - 1)$은 합동의 언어로도 적을 수 있다. $6 - 1 = 5$이므로 $6 \equiv 1 \pmod 5$이고, 31주차 문제 13(합동은 거듭제곱을 보존한다)에 의해 $$ 6^n \equiv 1^n = 1 \pmod 5, \qquad \text{곧} \quad 5 \mid (6^n - 1) $$ 두 줄이면 끝난다. 앞 절의 귀납 증명은 다섯 줄이었다. :::{container} quotebox **확인 8.** 합동 풀이가 더 짧아 보인다. 그렇다면 이번 주에 귀납 절차를 따로 익히는 이유는 무엇인가. 31주차 문제 13이 어떻게 증명되었는지 떠올려 보자. ::: :::{admonition} 답 :class: quotebox dropdown 31주차 문제 13 자체가 **$m$에 대한 귀납법으로 증명된 정리**다. 곧 합동 풀이는 귀납을 없앤 것이 아니라 이미 증명해 둔 부품 안으로 넣어 둔 것이다 — 근거 ④의 전형적인 사용이다. 부품이 손에 없는 명제(예제 2.2의 $6 \mid (n^3 - n)$처럼 지수가 아니라 다항식인 경우)에서는 표준 수를 직접 써야 한다. 두 스타일 모두 훈련한다. 문제 9가 같은 명제를 두 방식으로 쓰고 비교하는 자리다. ::: ### 7 근거 목록 — 이번 주의 갱신 증명에서 쓸 수 있는 근거는 1주차 §1.6에서 세운 ①~④ 그대로다. 칸의 개수는 늘지 않는다. 이번 주에는 각 칸에서 꺼내 쓰는 물건이 다음과 같다. 근거 목록과 별개로 답안의 **서술 규범**도 그대로 적용된다 — 15주차의 증명 글쓰기 규범(생략한 걸음은 읽는 사람이 복원할 수 없다)과, 귀납 단계 안에서 경우를 나눌 때 쓰는 17주차의 채점 기준 두 가지(빠짐없음 + 각 경우 완결)다. 규범은 근거가 아니므로 아래 표에 넣지 않지만, 문제 15와 문제 17에서 실제로 요구된다. | **근거** | **이번 주에 꺼내 쓰는 것** | |---|---| | ① 정의 | 정의 2.1($a \mid b$), 20주차 합동의 정의, $(k+1)! = (k+1) \cdot k!$ | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 — 잔여가 정수임을 확인할 때 | | ③ 등식$\cdot$부등식의 성질 | 전개$\cdot$묶기, 그리고 (W1)~(W6) — 특히 (W3) 양수 곱, (W4) 부호, (W6) 추이성 | | ④ 이미 증명한 명제 | **일반화된 귀납 원리**(§1.4), 31주차 문제 13$\cdot$문제 10(분해 $\frac{1}{k(k+1)} = \frac1k - \frac{1}{k+1}$), 2주차 훈련 1$\cdot$예제 2.2$\cdot$문제 7, 1주차 문제 16, 16주차 문제 11(제곱 비교)$\cdot$문제 17(0 이상인 두 수는 제곱해서 비교해도 된다) | 이번 주에 목록에 새로 들어오는 것은 하나 — §1.4의 **일반화된 귀납 원리**이고, ④ 칸에 놓인다. "당연하다", "$k$가 충분히 크면"은 네 칸 어디에도 없다. :::{container} quotebox **확인 9.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "$2k^2 \ge (k+1)^2$은 $k$가 충분히 크면 당연하므로" (나) "귀납 가정의 양변에 $2 > 0$을 곱하면 부등호가 유지되므로" (다) "$8 \equiv 1 \pmod 7$이므로 $8^n \equiv 1^n \pmod 7$이다 (31주차 문제 13)" ::: :::{admonition} 답 :class: quotebox dropdown (가) 불허. "당연"은 목록 밖이고, "충분히 크면"은 범위를 지정하지 않았다. 같은 내용을 근거로 만들려면 차 $2k^2 - (k+1)^2 = (k-1)^2 - 2$를 계산하고, $k \ge 4$이면 $k - 1 \ge 3 \ge 0$이므로 제곱 비교(근거 ④, 16주차 문제 11)로 $(k-1)^2 \ge 9$이며 $9 - 2 = 7 > 0$임을 적어야 한다($k = 4$는 $(k-1)^2 = 9$로 등호가 되는 경우이므로 한 줄 나눠 적는다 — 예제 2.1의 4단계에서 그렇게 한다). (나) 허용 — 근거 ③, (W3)이다. (다) 허용 — 근거 ④. 인용한 정리의 가정($8 \equiv 1 \pmod 7$)이 실제로 충족되는지만 확인하면 된다. :::