32주차 — 귀납법 연습: 부등식과 나누어떨어짐

내용

32주차 — 귀납법 연습: 부등식과 나누어떨어짐#

이 주의 길잡이

핵심 문장: 부등식 귀납은 2단 구조다 — 귀납 가정이 데려다주는 중간값까지가 절반이고, 거기서 목표까지는 연결 부등식으로 따로 놓는다.

이 주의 위치: 50주 과정의 32주차. 31주차에서 세운 귀납법 서식을 등식이 아닌 명제 — 부등식과 나누어떨어짐 — 에 적용한다.

원서 대응: BoP(Book of Proof) 10장의 부등식\(\cdot\)나누어떨어짐 연습문제군. 원서 없이 읽을 수 있다.

이번 주 목표#

부등식 귀납의 2단 구조(귀납 가정 투입 \(\to\) 연결 부등식)를 백지에 쓰고, 증명 안에서 두 단을 손가락으로 짚을 수 있다.
기초 단계가 1이 아닌 귀납(\(n \ge 4\)부터 등)을 다룬다 — \(2^n \ge n^2\), \(3^n > n^3\), \(n! > 2^n\). 기초의 위치 \(n_0\)을 실험으로 정하고, 연결 부등식이 요구하는 범위와 맞물리는지 확인한다.
나누어떨어짐 귀납의 표준 수(”\(f(k)\)의 배수 항을 강제로 만들고 잔여를 확인한다”)를 익힌다.
베르누이 부등식을 확보한다 — 46주차의 급수(문제 16, \(r^n \to 0\))에서 부품으로 쓴다.

본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

준비 운동 (31주차 복습)#

귀납법 서식의 두 단계 이름을 쓰고, “귀납 가정을 사용한 지점에 표시를 단다”는 규칙이 왜 필요한지 한 문장으로 쓰시오.
\(n < 2^n\)의 귀납 단계를 재현하시오 (31주차 문제 16). 특히 \(2 \cdot 2^k > 2k\) 다음에 무엇을 적었는지 기억해 보자.
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)에서 실험으로 범위만 제안해 두고 증명을 미뤄 둔 명제다.

시도 — 등식 귀납의 절차를 그대로

명제: \(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주차 예제에서는 이 자리에 항등식이 있어서 변형만 하면 도착했지만, 지금은 변형으로 이을 수 없는 두 식이 마주 보고 있다.

확인 1. 멈춘 자리에서 결론이 나오려면 \(2k^2\)과 \((k+1)^2\) 사이에 무엇이 있어야 하는가. 그리고 그것이 저절로 성립하는지 \(k = 1\)을 넣어 확인해 보자.

답

\(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\)의 범위도 따로 확인해야 한다.

이 주 전체의 기준

등식 귀납에서는 귀납 가정을 투입한 뒤 남는 것이 항등식이라 변형만 하면 닫힌다.

부등식 귀납에서는 귀납 가정이 데려다준 중간값과 목표 사이에, 독립적으로

참임을 보여야 하는 부등식이 남는다.

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}\)

확인 2. 빈칸 (1)~(4)를 채우고, 세 줄에 공통으로 나타나는 걸음의 개수를 적어 보자.

답

(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\).

공통으로 나타나는 걸음은 셋이다 — ① 변형, ② 귀납 가정 투입, ③ 남는 부등식.

셋째 걸음의 난이도는 줄마다 다르다(첫 줄과 셋째 줄은 한 줄, 둘째 줄은

차를 계산해야 한다). 그러나 셋째 걸음이 있다는 사실 자체는 세 줄 모두 같다.

이 관찰에 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표에서 한 일을 문장으로 굳혔을 뿐이다.

백지 암기 대상

부등식 귀납의 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\)에서 손으로 증명하는 보통의 부등식 문제다.

표기 — \(n!\)과 그 재귀

\(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\)이 따라 나오지 않는다 — 참인 전제에서 거짓인 결론이 나온 셈이다.

확인 3. 셋째 걸음을 지우면 정확히 무엇이 무너지는가. “\(A \ge B\)이고 \(C \le B\)이면 \(A \ge C\)”와 “\(A \ge B\)이고 \(C \ge B\)이면 \(A \ge C\)” 중 어느 쪽이 참인지와 함께 생각해 보자.

답

앞쪽만 참이다 — 추이성 (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\)을 실험으로 정하는 절차까지 붙인다.

표기 — \(n_0\)

\(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}\)

확인 4. 빈칸 (1)(2)(3)을 채우고, “그 뒤로 계속 성립하는 첫 지점”을 \(n_0\)이라 할 때 \(n_0\)을 정해 보자. \(n = 1, 2\)에서도 성립하는데 \(n_0 = 1\)로 잡으면 안 되는 이유도 한 문장으로 적어 보자.

답

(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\)에서 출발했다. 출발점만 옮기면 그대로 쓸 수 있다.

백지 암기 대상

일반화된 귀납 원리 (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\)이 어긋나지 않는지를 반드시 맞춰 봐야 한다.

확인 5. 기초를 \(n_0 = 4\)로 잡았다. (가) 연결 부등식이 \(k \ge 3\)에서 성립한다면 문제가 되는가. (나) 연결 부등식이 \(k \ge 6\)에서만 성립한다면 어떻게 되는가.

답

(가) 문제없다. 귀납 단계는 \(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)\)을 손에 들었다.

시도 — 가정을 쓸 자리를 찾지 못한 채

“\(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}\)

확인 6. 빈칸 (1)~(4)를 채워 보자. 셋째 줄은 전개부터 해야 한다: \((k+1)^2 + (k+1)\)을 전개해 \(k^2 + k\)를 떼어 내면 무엇이 남는가.

답

(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\)의 배수인지 확인한다.**

이 절차에 이름을 붙인다. 여기에도 새로운 것은 없다 — 재배열과 확인뿐이다.

백지 암기 대상

나누어떨어짐 귀납의 표준 수

목표가 \(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) 결론이 나온다.

② 걸음이 부등식 귀납의 “귀납 가정 투입”에 해당하고, ③ 걸음이 “연결 부등식”에 해당한다. 소재가 달라도 귀납 단계의 뼈대는 같다.

빼고 더하기는 손이 미끄러지기 쉬운 변형이다. 검산 한 줄을 붙이는 습관을 들인다.

확인 7. \(6(6^k - 1) + 5\)를 도로 전개해서 \(6^{k+1} - 1\)이 되는지 확인해 보자.

답

\(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) \]

두 줄이면 끝난다. 앞 절의 귀납 증명은 다섯 줄이었다.

확인 8. 합동 풀이가 더 짧아 보인다. 그렇다면 이번 주에 귀납 절차를 따로 익히는 이유는 무엇인가. 31주차 문제 13이 어떻게 증명되었는지 떠올려 보자.

답

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\)가 충분히 크면”은 네 칸 어디에도 없다.

확인 9. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) “\(2k^2 \ge (k+1)^2\)은 \(k\)가 충분히 크면 당연하므로”

(나) “귀납 가정의 양변에 \(2 > 0\)을 곱하면 부등호가 유지되므로”

(다) “\(8 \equiv 1 \pmod 7\)이므로 \(8^n \equiv 1^n \pmod 7\)이다 (31주차 문제 13)”

답

(가) 불허. “당연”은 목록 밖이고, “충분히 크면”은 범위를 지정하지 않았다.

같은 내용을 근거로 만들려면 차 \(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\))이 실제로

충족되는지만 확인하면 된다.