33주차 · 강의 — 예제 · 연습 · 해설

33주차 · 강의 — 예제 · 연습 · 해설#

예제 — 세 가지 빚을 함께 청산하기#

완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께, 예제 2.3은 설계부터 스스로 한다.

예제 2.1 — 소인수분해의 존재 (빚 청산 1)#

명제. 2 이상의 모든 정수는 소수이거나 소수들의 곱이다.

설계 — 쓰기 전에 정하는 세 가지. 귀납형 증명에서 먼저 정할 것은 무대, 기초, 가정의 크기다. 셋을 표로 옮긴다.

말

서식 번역

무대

\(n \ge 2\)인 정수

기초를 \(n = \underline{\quad(?)\quad}\)에 둔다

가정 (출발점)

과거 전부가 성립

\(2 \le j \le k\)인 모든 \(j\)에서 명제가 참

목표 (도착점)

\(k+1\)도 성립

\(k+1\)이 소수이거나, 소수들의 곱으로 적힌다

확인 8. 무대 칸의 빈칸을 채워 보자. 기초를 \(n = 1\)에 두면 무엇이 어긋나는가.

답

\(n = 2\)다. 명제의 무대가 “\(n \ge 2\)”이므로 1은 주장의 대상이 아니고, 실제로 1은 소수도

아니고 소수들의 곱도 아니다(정의 15.2에서 1은 소수에서 제외된다). 무대 밖의 수를

기초로 삼으면 확인할 수 없는 것을 확인하려다 막힌다.

1단계 — 기초를 확인한다. \(n = 2\): 2의 양의 약수는 1과 2뿐이므로 2는 소수다(정의 15.2). ✓

2단계 — 강한 가정을 선언한다. 필요한 과거의 위치를 지정할 수 없으므로 구간 전체를 가정한다(§1.2).

확인 9. 귀납 단계의 첫 문장을 완성해 보자: “\(k \ge 2\)에 대해,

\(\underline{\quad}\)부터 \(\underline{\quad}\)까지의 모든 정수가 소수이거나

소수들의 곱이라고 가정하자.”

답

“\(2\)부터 \(k\)까지”. 보통 귀납이라면 “\(k\)가 소수이거나 소수들의 곱이라고 가정하자”로

적었을 자리다. 이 한 줄의 차이가 §1.1의 막힘을 푼다.

3단계 — 경우를 나눈다. 손에 있는 정보는 “\(k+1 \ge 3\)인 정수”뿐이다. 2 이상의 정수는 소수이거나 합성수이므로, 이 둘로 나누면 전체가 빠짐없이 덮인다(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④). 정의 15.2는 양의 약수 쪽 말이고 15.3은 분해 쪽 말이라 두 정의만으로는 이분법이 곧바로 나오지 않는다 — 둘이 같은 경계를 긋는다는 것을 15주차 문제 4 해설이 세워 두었다(17주차의 빠짐없음 확인).

확인 10. \(k+1\)이 합성수인 경우, 정의 15.3을 풀면 무엇을 얻는가. \(a, b\)의

범위를 부등식으로도 적어 보자.

“\(k+1 = \underline{\quad}\)인 정수 \(a, b\)가 존재하고, \(\underline{\quad} \le a, b \le \underline{\quad}\)이다.”

답

\(k+1 = ab\)인 정수 \(a, b\) (\(1 < a, b < k+1\))가 존재한다. 정수에서 \(1 < a\)는 \(2 \le a\)와

같고 \(a < k+1\)은 \(a \le k\)와 같으므로 \(2 \le a, b \le k\)이다. 정확한 값은 모르지만

구간은 안다 — 그 구간이 정확히 강한 가정의 범위다. 보통 귀납이 쥔 유일한 참 \(P(k)\)는

여기서 쓸 데가 없다 — \(k+1 = 12\)이면 \(k = 11\)이 분해 어디에도 등장하지 않기 때문이다.

4단계 — 강한 가정을 소비하고 결론을 조립한다. 얻은 구간이 가정 범위와 일치하므로 \(a\)와 \(b\)에 각각 가정을 적용한다. 둘 다 소수이거나 소수들의 곱이면 그 곱도 그렇다.

확인 11. 마지막 문장을 완성해 보자: “따라서 \(k+1 = ab\)는 \(\underline{\qquad}\)이다.

강한 귀납법에 의해 \(\underline{\qquad}\)에서 명제가 성립한다. \(\blacksquare\)”

답

“소수들의 곱” / “모든 \(n \ge 2\)”. \(a\)가 소수 하나이거나 소수들의 곱이고 \(b\)도 그러하므로

두 목록을 이어 붙이면 \(k+1\)의 소수 목록이 된다(소수 하나짜리 곱도 곱으로 센다).

완성본. 방금 만든 네 단계를 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

강한 귀납법으로 증명한다. [기초] \(n = 2\): 2의 양의 약수는 1과 2뿐이므로 2는 소수다(정의 15.2). ✓

시작점은 2다 — 명제의 무대가 \(n \ge 2\)이므로(확인 8).

[귀납] \(k \ge 2\)에 대해, \(2\)부터 \(k\)까지의 모든 정수가 소수이거나 소수들의 곱이라고 가정하자. \(k+1\)을 생각한다.

강한 가정 — 직전 하나가 아니라 구간 전부. 이유는 넷째 줄에서 드러난다.

경우 1: \(k+1\)이 소수. 그 자체로 명제가 성립한다.

2 이상의 정수는 소수이거나 합성수이므로 두 경우가 전체를 덮는다(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④).

경우 2: \(k+1\)이 합성수. 정의 15.3에 의해 \(k+1 = ab\)인 정수 \(a, b\) (\(1 < a, b < k+1\))가 존재한다. 곧 \(2 \le a \le k\)이고 \(2 \le b \le k\)이다.

정의 풀어쓰기(근거 ①). 범위는 알지만 정확한 값은 모른다 — 이것이 다음 줄의 조건이다.

\(2 \le a \le k\)이고 \(2 \le b \le k\)이므로, 강한 귀납 가정에 의해 \(a\)와 \(b\)는 각각 소수이거나 소수들의 곱이다.

어느 과거인지 모르는 자리를 인용하는 순간 — 강한 귀납법이 필요한 이유가 이 한 줄이다.

따라서 \(k+1 = ab\)는 소수들의 곱이다. 강한 귀납법에 의해 모든 \(n \ge 2\)에서 명제가 성립한다. \(\blacksquare\)

두 목록을 이어 붙이면 소수들의 곱이 된다. 결론 선언으로 마무리.

대입 시뮬레이션. \(k + 1 = 24\)는 합성수이므로 \(24 = 4 \times 6\)으로 쪼개지고, 강한 가정에 의해 \(4 = 2 \times 2\), \(6 = 2 \times 3\)이 각각 소수들의 곱이므로 \(24 = 2 \cdot 2 \cdot 2 \cdot 3\)이다. 소비된 것은 \(P(4)\)와 \(P(6)\)뿐이고, 보통 귀납이 주는 유일한 참 \(P(23)\)은 한 줄에서도 쓰이지 않는다.

따름정리 (빚 청산 1의 회수분)

2 이상의 모든 정수는 소수인 약수를 가진다.

위 분해에 등장하는 소수 아무거나 하나가 그 약수다(유도는 문제 6). 이 따름정리가 21주차 소수 무한 증명이 첫 줄에서 빌려 쓴 사실이며, 이제 그 증명이 자립한다.

예제 2.2 — 나눗셈 정리의 존재성 (빚 청산 2)#

명제. 정수 \(a \ge 0\)과 자연수 \(n\)에 대해, \(a = nq + r\)이고 \(0 \le r < n\)인 정수 \(q, r\)이 존재한다.

이번에는 설계만 함께 한다. 최소원리를 쓰려면 어떤 집합에 적용할지부터 정해야 한다.

확인 12. “나머지”란 말로 하면 “\(a\)에서 \(n\)을 뺄 만큼 뺀 잔여”다. 그 잔여들을

모은 집합을 \(q\)를 써서 적고, 그 집합이 공집합이 아님을 보이려면 \(q\)에 무엇을

넣으면 되는지도 적어 보자.

\(S = \{\,\underline{\qquad} : q \in \mathbb{Z},\ \underline{\qquad}\,\}\)

답

\(S = \{a - nq : q \in \mathbb{Z},\ a - nq \ge 0\}\). 두 조각이 모두 필요하다 — 앞쪽은

잔여의 꼴이고, 뒤쪽 조건은 무대를 “음이 아닌 정수”로 제한한다(이 제한이 없으면 \(q\)를

키우는 만큼 값이 작아져 최소원소가 없다). 비공 확인은 \(q = 0\): \(a \ge 0\)이므로 \(a \in S\)다.

완성본.

증명의 한 줄

왜 이 줄을 쓰는가?

집합 \(S = \{a - nq : q \in \mathbb{Z},\ a - nq \ge 0\}\)을 생각하자.

최소원리를 적용할 대상을 먼저 만든다. 나머지 후보들의 집합이다.

\(q = 0\)일 때 \(a - 0 = a \ge 0\)이므로 \(a \in S\)이다 — \(S\)는 공집합이 아닌, 음이 아닌 정수들의 집합이다.

최소원리의 첫째 조각(“공집합이 아닌”)을 실제로 확인한다. 빠뜨리면 인용 자격이 없다.

최소원리에 의해 \(S\)는 최소원소를 가진다. 그것을 \(r = a - nq_0\)이라 하자 (\(q_0 \in \mathbb{Z}\), \(r \ge 0\)).

최소원리 인용. \(r \in S\)이므로 음이 아니다 — 목표의 왼쪽 부등식 \(0 \le r\)이 여기서 확보된다.

\(r < n\)을 귀류로 보인다. 만약 \(r \ge n\)이면 \(r - n = a - n(q_0 + 1) \ge 0\)이다.

남은 것은 오른쪽 부등식뿐이다. \(r - n\)을 \(S\)의 꼴로 다시 적는 것이 관건 — \(q\) 자리에 \(q_0 + 1\)이 들어간다(근거 ③).

곧 \(r - n \in S\)인데 \(n \ge 1\)이므로 \(r - n < r\)이다. 이는 \(r\)의 최소성과 모순이다.

최소원소보다 작은 원소를 실제로 만들어 충돌시킨다 — §1.6의 첫째 갈래(뒤의 ④-a) 그대로.

따라서 \(0 \le r < n\)이고 \(a = nq_0 + r\)이다. \(\blacksquare\)

두 부등식과 등식이 모두 확보됐으므로 존재가 증명됐다.

확장 — \(a < 0\)인 경우. 위 증명에서 \(a \ge 0\)을 쓴 곳은 단 하나, \(S \neq \varnothing\)을 확인한 줄(\(q = 0\)에서 \(a \in S\))이다. 그 한 줄만 다시 세우면 나머지는 글자 그대로 같다. \(a < 0\)이면 \(q = a\)로 둔다. \(n \ge 1\)이므로 \(1 - n \le 0\)이고 \(a < 0\)이므로, \(a(1 - n)\)은 0 이하인 두 수의 곱이어서 0 이상이다(근거 ③). 곧

\[ a - na = a(1 - n) \ge 0 \]

이므로 \(a - na \in S\)이고 \(S \neq \varnothing\)이다. 이후 최소원소를 잡고 \(r < n\)을 보이는 논증은 위와 한 줄도 다르지 않다. 따라서 **모든 정수 \(a\)와 자연수 \(n\)**에 대해 \(a = nq + r\), \(0 \le r < n\)인 정수 \(q, r\)이 존재한다 — 17주차가 인정하고 쓴 진술이 정확히 이 범위였다.

복기. “나머지”의 정체가 여기서 드러난다 — \(a\)에서 \(n\)을 뺄 만큼 뺀 잔여 중 가장 작은 음 아닌 것이다. 유일성은 문제 10에서 따로 증명한다(존재와 유일은 별개 의무 — 26주차). 확장 단계를 따로 붙인 이유도 같은 자리에 있다 — 무대를 넓히려면 넓힌 만큼의 증명이 필요하고, “같은 논법이 선다”는 한 줄은 증명이 아니다.

따름정리 (1주차 문제 16의 빚 청산)

모든 정수는 짝수이거나 홀수이다.

나눗셈 정리를 \(n = 2\)에 적용하면 \(a = 2q + r\), \(0 \le r < 2\)인 정수 \(q, r\)이 존재한다. \(r\)는 \(0 \le r < 2\)인 정수이므로 \(r = 0\) 또는 \(r = 1\)이다(그 사이에 정수가 없다는 것이 보조 명제 33.A다). 각각 \(a = 2q\)(짝수)와 \(a = 2q + 1\)(홀수)이다. 확장 단계가 붙었으므로 이 따름정리의 무대도 모든 정수다. 1주차 문제 16, 9주차 예제 2.3, 11주차 문제 2, 17주차의 경우 나누기가 전부 이 한 줄에 기대고 있었다.

예제 2.3 — 기약분수의 존재 (빚 청산 3)#

명제. 모든 양의 유리수는 기약분수로 나타낼 수 있다.

이번에는 설계부터 스스로 해 보자.

확인 13. 최소원리를 어느 집합에 적용해야 하는가. 그 집합이 공집합이 아님은

무엇이 보장하는가.

답

\(S = \{b \in \mathbb{N} : r = \frac{a}{b}\)인 \(a \in \mathbb{N}\)가 존재\(\}\) — 같은 유리수

\(r\)을 나타내는 표현들의 분모를 모은 집합이다. 비공의 근거는 유리수의 정의(정의 15.1)이되

한 걸음이 더 필요하다. 정의 15.1이 주는 것은 \(r = \frac{a}{b}\)인 정수 \(a, b\) (\(b \neq 0\))

이지 자연수 \(a, b\)가 아니기 때문이다. \(r > 0\)이므로 \(a \neq 0\)이고 \(a\)와 \(b\)는 같은 부호이며,

둘 다 음수이면 \((a, b)\)를 \((-a, -b)\)로 바꿔도 값이 같으므로 처음부터 \(a, b \in \mathbb{N}\)인

표현을 잡을 수 있다. 그 \(b\)가 \(S\)의 원소다. 최소 분모를 잡으면 “더는 약분할 수 없다”가

따라 나온다.

증명. \(r\)를 양의 유리수라 하자. 집합

\[ S = \Big\{ b \in \mathbb{N} : r = \tfrac{a}{b} \text{인 } a \in \mathbb{N} \text{가 존재} \Big\} \]

를 생각하자. 정의 15.1에 의해 \(r = \frac{a}{b}\)인 정수 \(a, b\) (\(b \neq 0\))가 존재한다. \(r > 0\)이므로 \(a \neq 0\)이고 \(a\)와 \(b\)는 같은 부호이며, 둘 다 음수이면 \((a, b)\)를 \((-a, -b)\)로 바꿔도 값이 같으므로 처음부터 \(a, b \in \mathbb{N}\)인 표현을 잡을 수 있다. 그 \(b\)가 \(S\)의 원소이므로 \(S \neq \varnothing\)이다. 최소원리에 의해 \(S\)는 최소원소 \(b_0\)을 가지며, \(r = \frac{a_0}{b_0}\)인 자연수 \(a_0\)을 하나 잡는다.

이 표현이 기약임을 귀류로 보인다. \(a_0\)과 \(b_0\)이 \(1\)보다 큰 공통 약수 \(d\)를 가진다고 가정하면, \(a_0 = d a_1\), \(b_0 = d b_1\)인 자연수 \(a_1, b_1\)이 존재하고

\[ r = \frac{a_0}{b_0} = \frac{d a_1}{d b_1} = \frac{a_1}{b_1} \]

이다. 곧 \(b_1 \in S\)이다. 그런데 \(d > 1\)이므로 \(b_1 = \frac{b_0}{d} < b_0\)이고, 이는 \(b_0\)의 최소성과 모순이다. 따라서 \(a_0\)과 \(b_0\)의 공통 약수는 \(\pm 1\)뿐이고, \(\frac{a_0}{b_0}\)은 기약분수다(정의 21.2). \(\blacksquare\)

확장 — \(r \le 0\)인 경우. 21주차가 인정하고 쓴 것은 “모든 유리수는 기약분수로 나타낼 수 있다”이므로, 0과 음의 유리수까지 덮어야 회수가 끝난다. \(r = 0\)이면 \(\frac{0}{1}\)이 기약이다 — 1의 약수는 \(\pm 1\)뿐이므로(22주차 보조 명제 22.A) 0과 1의 공통 약수도 \(\pm 1\)뿐이다. \(r < 0\)이면 \(-r\)가 양의 유리수이므로 위 증명이 기약 표현 \(-r = \frac{a_0}{b_0}\)을 주고, \(r = \frac{-a_0}{b_0}\)이다. \(d \mid -a_0\)과 \(d \mid a_0\)은 같은 조건이므로(\(-a_0 = dc\)이면 \(a_0 = d(-c)\), 근거 ①) 공통 약수의 집합은 분자의 부호에 무관하고, 따라서 \(\frac{-a_0}{b_0}\)도 기약이다(정의 21.2). 곧 모든 유리수에서 성립한다.

복기. 21주차가 직관으로 넘긴 문장 — “약분을 반복하면 언젠가 끝난다” — 의 엄밀한 정체가 이것이다. 약분할 때마다 분모가 작아지는데 자연수는 무한히 작아질 수 없다(문제 18에서 일반화).

관찰 — 최소원리 증명의 같은 뼈대#

예제 2.2와 2.3은 소재가 전혀 다르지만 걸음이 같다. 대응표의 빈칸을 채워 보자.

단계

예제 2.2 (나눗셈 정리)

예제 2.3 (기약분수)

① 후보들의 집합 \(S\)를 만든다

잔여 \(a - nq \ge 0\)의 집합

\(\underline{\quad(1)\quad}\)

② \(S \neq \varnothing\)을 확인한다

\(q = 0\)에서 \(a \in S\)

\(\underline{\quad(2)\quad}\)

③ 최소원소를 잡는다

나머지 \(r\)

최소 분모 \(b_0\)

④ 더 작은 원소를 만들어 최소성과 충돌시킨다

\(r - n \in S\), \(r - n < r\)

\(\underline{\quad(3)\quad}\)

확인 14. 빈칸 (1)(2)(3)을 채우고, ④단계에서 두 증명이 공통으로 하는 일을

한 문장으로 적어 보자.

답

(1) \(r\)의 분수 표현들의 분모 집합. (2) 유리수의 정의가 정수 표현 하나를 보장하고,

\(r > 0\)이므로 부호를 맞춰 자연수 표현으로 고칠 수 있으니 그 분모가 \(S\)의 원소.

(3) 공통 약수 \(d > 1\)로 약분해 만든 \(b_1 \in S\), \(b_1 < b_0\). ④에서 공통으로

하는 일: 최소라고 잡은 것보다 작은 원소를 실제로 만들어 제시한다.

다만 이 문장은 두 예제에 대한 관찰이다 — 최소 반례법(문제 11, 14)은 ④를 다른 방식으로

한다. 아래 서식의 ④-a와 ④-b가 그 두 갈래다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

최소원리 4단 서식

① 후보들의 집합 \(S\)를 정의한다 \(\to\) ② \(S \neq \varnothing\)을 원소 하나로 확인한다

\(\to\) ③ 최소원리로 최소원소 \(m\)을 잡는다 \(\to\) ④ 모순을 만든다. ④는 두 갈래다:

(④-a) \(m\)보다 작은 원소를 실제로 만들어 최소성과 충돌시킨다(예제 2.2, 2.3, 문제 13).

(④-b) 최소성이 주는 “\(m\)보다 작은 곳은 전부 참”을 써서 \(m\)에서도 명제가 참임을 보이고

**\(m \in S\)**와 충돌시킨다(최소 반례법 — 문제 11, 14).

최소 반례법(§1.6)은 \(S\)를 “반례들의 집합”으로 잡고 ④-b로 닫는 경우다. 두 갈래는 충돌 상대가 다르다 — ④-a는 최소성과, ④-b는 \(m\)의 소속과 부딪친다. 문제 11을 ④-a로 쓰려 하면 \(S\)의 더 작은 원소를 만들 길이 없어 막히므로, 어느 갈래인지를 먼저 정하고 시작한다. 예제 2.1의 강한 귀납법은 아예 다른 뼈대를 쓴다 — 기초 \(\to\) 강한 가정 선언 \(\to\) 경우 나누기 \(\to\) 위치를 모르는 과거 인용 \(\to\) 조립.

빈칸 사다리 — 지지대를 하나씩 빼며#

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 수식 빈칸#

명제. 모든 자연수 \(n\)은 \(n = 2^a m\) (\(a \ge 0\)은 정수, \(m\)은 홀수) 꼴로 나타낼 수 있다.

증명. 강한 귀납법으로 증명한다. [기초] \(n = 1\): \(1 = 2^0 \cdot 1\)이고 1은 홀수다. ✓

[귀납] 1부터 \(k\)까지 성립한다고 가정하자. \(k+1\)에 대해:

경우 1: \(k+1\)이 홀수. \(k + 1 = 2^{\underline{\quad(1)\quad}} \cdot (k+1)\) — 완료.

경우 2: \(k+1\)이 짝수. \(k+1 = 2j\)인 자연수 \(j\)가 존재하고, \(j \le k\)이므로 \(\underline{\quad(2)\quad}\) 가정에 의해 \(j = 2^a m\) (\(m\)은 홀수) 꼴이다. 그러면 \(k + 1 = 2j = 2^{\underline{\quad(3)\quad}} m\) — 완료. \(\blacksquare\)

(경우 2에서 \(j\)는 대개 \(k\)가 아니라 약 절반 지점이다 — \(k = 1\)일 때만 \(j = k\)이고, 그 밖에는 직전 가정으로 닿지 않는 과거다.)

훈련 2 ●●○ — 수식과 근거를 함께#

이번에는 최소 반례법의 서식 낱말과 근거 문장도 빈칸이다.

명제. 모든 자연수 \(n\)에 대해 \(n^3 - n\)은 3의 배수이다.

증명. 모순을 위해 명제가 거짓인 자연수가 있다고 가정하자. 반례들의 집합은 \(\underline{\quad(1)\quad}\)이 아니므로 \(\underline{\quad(2)\quad}\)에 의해 최소원소 \(m\)이 존재한다.

\(n = 1\)일 때 \(1^3 - 1 = 0 = 3 \cdot 0\)이므로 명제가 성립한다. 따라서 \(m \ge \underline{\quad(3)\quad}\)이고 \(m - 1\)은 자연수다. \(m\)의 \(\underline{\quad(4)\quad}\)에 의해 \(m-1\)은 반례가 아니므로 \((m-1)^3 - (m-1) = 3s\)인 정수 \(s\)가 존재한다. 그러면

\[ m^3 - m = \big[(m-1)^3 - (m-1)\big] + \underline{\quad(5)\quad} = 3s + 3(m^2 - m) = 3\big(\underline{\quad(6)\quad}\big) \]

이고, \(\underline{\quad(7)\quad}\)이므로 괄호 안은 정수다. 따라서 \(m\)에서도 명제가 성립하여 \(m\)이 반례라는 것과 모순이다. 그러므로 반례는 존재하지 않는다. \(\blacksquare\)

훈련 3 ●●● — 뼈대만 남기고#

최소원리 4단 서식의 각 칸을 통째로 채운다. 예제 2.1의 따름정리를 분해 없이 최소원리만으로 다시 증명하는 훈련이다.

명제. 2 이상의 모든 정수 \(n\)은 소수인 약수를 가진다.

증명의 뼈대.

  • ① 후보들의 집합: \(S = \underline{\quad(1)\quad}\)

  • ② 비공 확인: \(\underline{\quad(2)\quad}\)

  • ③ 최소원소 잡기: \(\underline{\quad(3)\quad}\)

  • ④ 그 최소원소가 소수임을 귀류로 보이기: \(\underline{\quad(4)\quad}\)

(④에서 쓸 부품은 2주차 예제 2.1의 추이성이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 귀납형 문제는 반드시 “무대 / 기초 / 가정의 크기”를 먼저 적고 시작한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “강한 귀납법으로 하면 된다(맞음)”는 0점이고,

“\(a, b\)의 위치를 지정할 수 없으므로 구간 전체를 가정한다”가 만점이다.

최소원리를 인용한 줄에는 \(S \neq \varnothing\)의 확인이, 보폭 \(d\)짜리 강한 귀납에는

기초 \(d\)개가 반드시 함께 있어야 한다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. [백지] 강한 귀납법의 원리를 쓰고, 보통 귀납과의 차이(가정의 크기)와 “언제 필요한가”의 신호 두 가지(분해형\(\cdot\)고정 보폭)를 쓰시오.

힌트

채점 항목이 셋이다 — 기초\(\cdot\)귀납 두 조각의 진술, 차이 한 문장, 신호 두 개.

신호는 §1.4의 표에서 왼쪽 열 두 낱말과 각각의 생김새를 함께 적는다.

2. [백지] 최소원리를 진술하고, 실수 구간 \((0,1)\)이 반례가 되는 이유(22주차 문제 10)를 한 줄로 덧붙이시오.

힌트

진술에는 조각이 셋 있다(§1.5의 해부 표). 반례 쪽은 후보 \(m\)을 잡은 뒤

더 작은 원소를 실제로 만들어 보이면 한 줄로 끝난다.

3. 다음 각 상황에 알맞은 도구(보통 귀납 / 강한 귀납 / 최소원리)를 고르고 이유를 한 줄씩 쓰시오. (a) \(\sum_{i=1}^n i = \frac{n(n+1)}{2}\) — 합의 마지막 항 분리 (b) “모든 \(n \ge 2\)는 소수들의 곱” — \(k+1 = ab\) 분해 (c) “반례가 있다면 가장 작은 반례를 잡아 모순” — 논법 자체 (d) \(F_{k+1}\)의 성질이 \(F_k\)와 \(F_{k-1}\) 둘에서 오는 경우

힌트

각 항목에서 물을 것은 하나다 — “\(k+1\)의 성질이 어느 자리에서 오는가”.

직전 하나면 보통 귀납, 위치를 모르거나 두 칸 이상 뒤면 강한 귀납이다.

4. 예제 2.1(소인수분해 존재)을 백지에 재현하시오.

힌트

여섯 줄이다: 기초 \(\to\) 강한 가정 선언 \(\to\) 경우 1(소수) \(\to\) 경우 2의 정의 풀기 \(\to\)

강한 가정 소비 \(\to\) 조립. 가장 자주 비는 곳은 “\(2 \le a, b \le k\)”의 부등식이다.

5. 예제 2.3(기약분수 존재)을 백지에 재현하시오.

힌트

최소원리 4단 서식의 칸을 차례로 채운다. ②(비공 확인)와 ④(더 작은 분모 제작)가

빠지기 쉽다 — 특히 \(b_1 < b_0\)의 근거로 \(d > 1\)을 명시했는지 확인한다.

6. “2 이상의 모든 정수는 소수인 약수를 가진다”를 예제 2.1의 따름정리로 유도하시오 (세 줄 이내). 이 사실이 21주차 어느 증명의 부품이었는지도 쓰시오.

힌트

예제 2.1이 주는 두 경우를 그대로 받는다. 소수인 경우에는 자기 자신이 답이고,

곱인 경우에는 그 곱에 등장하는 소수 하나를 꺼내 정의 2.1로 약수임을 확인한다.

표준 ●●○#

7. 빈칸 훈련(\(n = 2^a m\))을 백지에서 완성하시오.

8. (우표 문제, 강귀납 버전) \(n \ge 8\)인 모든 정수는 \(3a + 5b\) (\(a, b \ge 0\)) 꼴임을 강한 귀납법으로 증명하시오 (기초 \(n = 8, 9, 10\) 세 개를 확인하고, \(k + 1 \ge 11\)에서 \(P(k - 2)\)를 사용한다). 32주차 문제 15(교체 논법)와 어느 쪽이 깔끔한지 한 줄 논평하시오.

힌트

보폭이 3이므로 기초가 세 개다(§1.4). 귀납 단계에서 확인할 것은 하나 —

\(k+1-3\)이 가정 범위(\(8\) 이상)에 들어오는가. \(k+1 \ge 11\)이 정확히 그것을 준다.

9. 예제 2.2(나눗셈 정리 존재성)를 백지에 재현하시오.

10. (나눗셈 정리의 유일성) \(a = nq + r = nq' + r'\)이고 \(0 \le r, r' < n\)이면 \(q = q'\)이고 \(r = r'\)임을 증명하시오. (힌트: \(r - r' = n(q' - q)\)이고 \(|r - r'| < n\) — 25주차 예제 2.2의 보조정리)

힌트

유일성의 표준 서식(26주차)은 “두 개를 잡고 같음을 보인다”이다. 두 표현을 하나의

등식에 놓고 \(r\) 쪽과 \(q\) 쪽을 분리하면 “\(n\)의 배수인데 절댓값이 \(n\) 미만”이 된다.

11. (최소 반례법 재증명) \(1 + 2 + \cdots + n = \frac{n(n+1)}{2}\)을 최소 반례법으로 다시 증명하시오. (최소 반례 \(m\)을 잡고: \(m = 1\)인가? \(m - 1\)은 반례가 아님을 이용해 모순)

힌트

§1.6의 서식을 그대로 따른다. \(m = 1\)을 배제하는 근거는 \(n = 1\)에서의 직접

확인이고, \(m-1\)에서 공식이 성립한다는 근거는 \(m\)의 최소성이다.

12. \(n \ge 12\)인 모든 정수는 \(4a + 5b\) (\(a, b \ge 0\)) 꼴임을 강한 귀납법으로 증명하시오 (기초 4개: \(12, 13, 14, 15\)).

13. (√2 무리수 — 최소원리 버전) 다음 하강 논법을 완성하시오: \(\sqrt2 = \frac{a}{b}\)인 자연수 표현이 존재한다고 가정하고, 분모가 최소인 표현 \(\frac{a_0}{b_0}\)을 잡는다. (a) \(1 < \frac{a_0}{b_0} < 2\)에서 \(b_0 < a_0 < 2b_0\)임을 확인하시오. (b) \(a_1 = 2b_0 - a_0\), \(b_1 = a_0 - b_0\)이 자연수이고 \(\frac{a_1}{b_1}\)도 \(\sqrt2\)와 같음을 계산으로 보이시오 (\(a_1^2 = 2b_1^2\) 확인). (c) \(b_1 < b_0\)으로 최소성과 모순임을 선언하시오.

이 문제가 쓰는 도구 — 최소 분모 하강

21주차의 √2 증명은 “기약분수 표현을 잡는다”로 시작했다. 이번에는 기약을 요구하지

않고 분모가 최소인 표현을 잡는다 — 예제 2.3의 그 집합에 최소원리를 적용하는

것이며, 두 출발점이 같은 장치임을 확인하는 문제다. 하강으로 모순을 만드는 이

논법을 무한 강하법(infinite descent)이라 부르고, 정당성은 문제 18에서 증명한다.

힌트

(b)가 중심이다. \(a_1^2\)과 \(2b_1^2\)을 전개한 뒤 \(a_0^2 = 2b_0^2\)을 대입해 비교한다.

\(a_1, b_1\)이 자연수라는 확인을 빠뜨리지 않는다 — (a)가 그 준비다.

14. (최소원리 \(\Rightarrow\) 귀납법) \(P(1)\)이 참이고 모든 \(k\)에서 \(P(k) \Rightarrow P(k+1)\)인데도 어떤 자연수에서 \(P\)가 거짓이라고 가정하자. 최소원리로 모순을 이끌어내시오. (힌트: 반례 집합의 최소원소 \(m\) — \(m = 1\)일 수 있는가? \(m - 1\)은?)

힌트

증명할 대상이 명제가 아니라 원리라는 점만 다르고 안쪽은 최소 반례법 그대로다.

재료는 기초(\(P(1)\) 참)와 전달 장치 둘 — 각각의 소비 지점을 표시하며 쓴다.

도전 ●●●#

이 문제군이 인정하고 쓰는 사실 — 유한 집합의 최대원소

문제 15는 “\(2^j \le k+1\)인 최대의 \(j\)”를 잡는다. 그런 \(j\)가 존재하는 이유는 후보가

유한하고(2의 거듭제곱은 곧 \(k+1\)을 넘어선다) 비어 있지 않기 때문이다. “공집합이

아닌 유한한 음이 아닌 정수 집합에는 최대원소가 있다”는 최소원리의 짝이다 —

후보 집합이 \(j = 0\)을 담으므로(\(2^0 = 1 \le k+1\)) 자연수 판으로는 덮이지 않고,

최소원리 진술이 음이 아닌 정수까지 덮는 것과 짝을 맞춰 읽어야 한다.

이 교재에서는 증명 없이 인정한 채로 둔다 — 증명에는 유한 집합의 크기에 대한 귀납이

필요하고, 그것은 이 과정에서 다루지 않는다. 끝까지 미증명으로 남는 항목이다.

15. (이진 표현의 존재) 모든 자연수는 서로 다른 2의 거듭제곱들의 합으로 나타낼 수 있음을 강한 귀납법으로 증명하시오. (힌트: \(k+1\) 이하인 최대의 \(2^j\)를 떼어내고, 잔여 \(r = k+1 - 2^j\)에 대해 ① \(r \le k\) ② \(r < 2^j\) (아니면 \(2^{j+1} \le k+1\)이 되어 최대성 모순)을 확인 — ②가 “서로 다름”을 보장한다)

힌트

확인할 것이 셋이다: \(r\)이 자연수인가, \(r \le k\)인가, \(r < 2^j\)인가. 셋째는 귀류로

따로 증명한다 — \(r \ge 2^j\)이면 \(k+1\)이 얼마 이상이 되는지 계산해 본다.

16. (서술) 소인수분해의 유일성(순서를 빼면 한 가지)은 존재성보다 훨씬 어렵다. 그 증명에 필요한 핵심 보조정리가 “유클리드 보조정리: \(p\)가 소수이고 \(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)”이다. (a) 이 보조정리가 소수가 아닌 수에서는 거짓임을 반례로 보이시오 (2주차 문제 15). (b) 유일성이 왜 자명하지 않은지 — “\(6 = 2 \times 3\) 말고 다른 소수 조합이 없다는 걸 무엇이 막아 주는가?” — 를 두 문장 이내로 쓰시오 (증명은 정수론 과목의 몫).

이 문제가 인정하고 쓰는 사실 — 유클리드 보조정리

\(p\)가 소수이고 \(p \mid ab\)이면 \(p \mid a\) 또는 \(p \mid b\)이다. 이 교재에서는 증명

없이 인정한 채로 둔다 — 증명에는 베주 항등식이나 유클리드 호제법이 필요하고,

그것은 정수론 과목의 출발점이다. 이 항목은 50주차의 “남겨 둔 빚”에 그대로 남으며,

38주차 문제 15가 이 사실 위에 선다. (a)는 인정 범위를 재는 문제다.

힌트

(a) 조건 “소수”가 하는 일을 재는 문제다. 소수가 아닌 \(p\)는 \(p = uv\) (\(1 < u, v < p\))로

쪼개지므로, \(u\)와 \(v\)를 \(a\) 쪽과 \(b\) 쪽에 하나씩 나눠 넣으면 \(p \mid ab\)는 살아 있는데

\(p \nmid a\), \(p \nmid b\)가 된다(2주차 문제 15). 가장 작은 \(p\)부터 시험한다.

(b) 축은 “존재와 유일은 별개 의무”(26주차)다. 존재성 증명이 실제로 무엇을 했고

유일성은 그중 무엇을 하지 않았는지를 한 문장씩 적는다.

17. (진단 — 기초 부족) 수열을 \(c_1 = 1\), \(c_2 = 4\), \(c_n = c_{n-2} + 2\) (\(n \ge 3\))로 정의하자. 다음 ‘증명’의 결함을 찾고, 실제 \(c_2, c_4\) 값으로 반박하시오.

“명제: 모든 \(n\)에 대해 \(c_n = n\)이다. 증명: 강한 귀납법. [기초] \(c_1 = 1\) ✓. [귀납] \(1 \sim k\)에서 성립 가정. \(c_{k+1} = c_{k-1} + 2 = (k-1) + 2 = k+1\) ✓. \(\blacksquare\)”

힌트

정의대로 \(c_2, c_3, c_4\)를 직접 계산해 본다. 결론이 거짓인데 계산이 틀리지 않았다면

오류는 설정에 있다 — 이 증명이 참조하는 과거는 몇 칸 뒤인가(§1.4).

18. (무한 하강 금지) “자연수의 순감소 무한 수열(\(a_1 > a_2 > a_3 > \cdots\), 모든 \(a_i \in \mathbb{N}\))은 존재하지 않는다”를 최소원리로 증명하시오. 그리고 문제 13(√2 하강)이 이 원리의 사례임을 한 문장으로 연결하시오.

힌트

최소원리는 수열이 아니라 집합에 적용된다. 첫 줄에서 할 일은 수열에서 집합을

만드는 것이다 — 항들의 값을 모두 모으면 자연수의 부분집합이 된다.

19. (자기 설계 — 우표 변형) 4원과 7원 우표로 만들 수 있는 금액을 조사하시오: (a) 17원은 불가능함을 전수 조사로 보이시오. (b) \(n \ge 18\)인 모든 정수는 가능함을 강한 귀납법(기초 \(18, 19, 20, 21\))으로 증명하시오.

힌트

(a)의 전수 조사는 \(b\)(7원의 장수)로 나눈다. \(7b \le 17\)이므로 후보가 유한하고,

각각에서 남은 금액이 4의 배수인지만 확인하면 끝난다. (b)는 보폭 4 — 문제 12와 같다.

20. (서술) 귀납\(\cdot\)강한 귀납\(\cdot\)최소원리의 관계를 정리하시오: (a) 셋이 “한 가족”이라는 말의 뜻 (문제 14 + 최소 반례법의 구조를 근거로). (b) 실전에서 셋 중 무엇을 먼저 꺼낼지 자신의 기준을 세 줄 이내로.

힌트

(a)의 재료는 둘이다 — 문제 14가 “최소원리 \(\Rightarrow\) 귀납법” 한 방향을 세우고,

문제 11이 같은 명제를 귀납과 최소 반례법 두 문법으로 증명해 뼈대가 겹침을 보인다.

강한 귀납이 보통 귀납을 포함한다는 §1.4의 한 줄까지 얹으면 세 꼭짓점이 이어진다.

(b)는 정답이 하나가 아니다. 다만 근거가 §1.4의 신호 표(분해형\(\cdot\)고정 보폭)와

§1.6의 쓰임 표(최소 반례\(\cdot\)최소 잔여\(\cdot\)최소 후보)에 각각 닿아 있어야 한다.

백지 재현 — 복습 프로토콜#

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 강한 귀납법의 원리\(\cdot\)최소원리\(\cdot\)4단 서식만 펴 놓고 예제 2.1과 2.2를 처음부터 끝까지 적는다. 본문의 다른 부분은 보지 않는다.

2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다:

  • 강한 귀납법의 원리를 진술하고, 보통 귀납과의 차이를 조각 하나로 지목했다.

  • “분해형\(\cdot\)고정 보폭” 두 신호와 “보폭 \(d\)이면 기초 \(d\)개” 규칙을 썼다.

  • 최소원리를 세 조각(공집합이 아닌 / 자연수의 부분집합 / 최소원소 존재) 그대로 쓰고, “최소”라는 낱말이 하는 일을 설명했다.

  • 예제 2.1(소인수분해)\(\cdot\)2.2(나눗셈 정리)\(\cdot\)2.3(기약분수)을 재현했다 — 3대 빚 청산.

  • 최소원리 4단 서식의 ②(비공 확인)를 빠뜨리지 않았고, ④를 두 갈래로 구분해 썼다 — ④-a 최소성과 충돌(더 작은 원소 제작) / ④-b 소속과 충돌(최소 반례법).

  • 귀납 \(\Longleftrightarrow\) 최소원리 동치의 한 방향(문제 14)을 재현했다.

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점

처방

보통 귀납과 강한 귀납 중 무엇을 쓸지 모르겠다

§1.4 신호 표 — \(k+1\)의 성질이 어느 자리에서 오는지 먼저 적는다

기초를 몇 개 둘지 모르겠다

§1.4 보폭 규칙 + 문제 17의 진단

최소원리를 어느 집합에 쓸지 모르겠다

§1.6 쓰임 표와 §2 관찰의 대응표 — 후보를 모으는 것이 ①단계

최소원소를 잡은 다음이 나오지 않는다

§1.6과 §2의 4단 서식 — 어느 갈래인지부터 정한다. ④-a는 더 작은 원소를 만들고, ④-b는 “\(m\)보다 작은 곳은 전부 참”을 쓴다

반례 집합이 비지 않음을 왜 확인하는지 모르겠다

§1.5 조각 삭제 실험 1

강한 가정을 선언만 하고 쓰지 못했다

예제 2.1의 4단계 — 가정 범위와 얻은 구간을 대조한다

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) \(0\) (2) 강한 귀납 (또는 강한 귀납법의) (3) \(a + 1\)

※ (3)에서 \(2 \cdot 2^a = 2^{a+1}\)이고 \(m\)은 그대로 홀수로 남는다. (2)가 핵심 지점이다: \(j\)의 위치는 \(k+1\)에 따라 달라지므로 직전 가정으로는 닿지 않는다.

빈칸 사다리 — 훈련 2#

(1) 공집합 (2) 최소원리 (3) \(2\) (4) 최소성 (5) \(3(m^2 - m)\) (6) \(s + m^2 - m\) (7) 정수의 합\(\cdot\)차\(\cdot\)곱은 정수 (근거 ②)

※ (5)의 계산: \((m-1)^3 - (m-1) = m^3 - 3m^2 + 2m\)이므로 차는 \(3m^2 - 3m\)이다. \(m-1\)을 쓸 수 있는 근거가 (4) 최소성이라는 점을 반드시 표시한다.

빈칸 사다리 — 훈련 3#

(1) \(S = \{d \in \mathbb{N} : d > 1\)이고 \(d \mid n\}\) (2) \(n \mid n\)이고 \(n > 1\)이므로 \(n \in S\) — \(S\)는 공집합이 아니다. (3) 최소원리에 의해 \(S\)는 최소원소 \(p\)를 가진다. \(p > 1\)이고 \(p \mid n\)이다. (4) \(p\)가 소수가 아니라고 가정하면 \(p\)는 합성수이고(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④), 정의 15.3에 의해 \(p = ab\)인 정수 \(a, b\) (\(1 < a, b < p\))가 존재한다. \(a \mid p\)이고 \(p \mid n\)이므로 추이성 (2주차 예제 2.1)에 의해 \(a \mid n\)이다. \(a > 1\)이므로 \(a \in S\)인데 \(a < p\) — \(p\)의 최소성과 모순이다. 따라서 \(p\)는 소수이고, \(n\)은 소수인 약수 \(p\)를 가진다. \(\blacksquare\)

※ 문제 6은 같은 결론을 예제 2.1의 분해에서 꺼냈고, 이 훈련은 분해 없이 도달했다. 얻은 소수도 다르다 — 여기의 \(p\)는 \(n\)의 가장 작은 1보다 큰 약수다.

문제 1#

접근. 채점 항목이 셋이다: ① 원리의 두 조각을 정확히 진술, ② 보통 귀납과의 차이를 “가정의 크기”라는 조각 하나로 지목, ③ 신호 두 가지를 생김새와 함께 제시.

풀이. (원리) \(P(1)\)이 참이고(필요하면 \(P(1), \dots, P(n_0)\) 여러 개), 모든 \(k\)에 대해 “\(P(1), P(2), \dots, P(k)\)가 전부 참이면 \(P(k+1)\)도 참”이면, 모든 자연수 \(n\)에서 \(P(n)\)이 참이다. (차이) 보통 귀납의 가정은 직전 하나 \(P(k)\)이고, 강한 귀납의 가정은 \(P(1)\)부터 \(P(k)\)까지 전부다. 다른 조각은 하나도 바뀌지 않는다 — 기초도, 결론도 같다. (신호 1: 분해형) \(k+1 = ab\)처럼 쪼개지는데 \(a, b\)가 구간 어디에 있는지 미리 지정할 수 없는 경우. 예제 2.1과 훈련 1(\(n = 2^a m\))이 여기 속한다. (신호 2: 고정 보폭) \(k+1\)의 성질이 \(k-1\)이나 \(k-2\)처럼 정해진 칸수 뒤에서 오는 경우. 문제 8(보폭 3), 문제 12(보폭 4)가 여기 속하며, 보폭이 \(d\)이면 기초를 \(d\)개 확인해야 한다.

문제 2#

접근. 진술은 세 조각(공집합이 아닌 / 자연수의 부분집합 / 최소원소를 가진다)을 빠짐없이 적는 것이 채점 기준이다. 반례 쪽은 어떤 후보를 잡아도 더 작은 원소를 만들 수 있음을 보여야 한다.

풀이. (진술) 공집합이 아닌 자연수의 부분집합은 반드시 최소원소를 가진다(음이 아닌 정수의 부분집합에 대해서도 같다). \(S\)의 최소원소란 \(m \in S\)이면서 모든 \(x \in S\)에 대해 \(m \le x\)인 \(m\)이다. (반례) 실수에서는 거짓이다. 구간 \((0,1)\)은 비어 있지 않지만, 어떤 후보 \(m \in (0,1)\)에 대해서도 \(\frac{m}{2}\)이 다시 \((0,1)\)의 원소이면서 \(m\)보다 작으므로 \(m\)은 최소가 될 수 없다(22주차 문제 10). 최소원리를 인용할 때 무대가 자연수인지 먼저 확인하는 이유다.

문제 3#

접근. 각 항목에서 물을 것은 하나다 — “\(k+1\)의 성질이 어느 자리에서 오는가”. 직전 하나면 보통 귀납, 위치를 지정할 수 없거나 정해진 칸수 뒤면 강한 귀납이다.

풀이. (a) 보통 귀납. \(\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1)\)로 마지막 항만 떼어 내면 필요한 과거는 직전 하나 \(P(k)\)뿐이다. (b) 강한 귀납. 분해형 신호다. \(k+1 = ab\)에서 \(a, b\)는 \(2\) 이상 \(k\) 이하의 어딘가지만 위치를 지정할 수 없으므로 구간 전체를 가정해야 한다. (c) 최소원리. 도구 선택이 아니라 논법의 이름 자체다 — “가장 작은 반례가 존재한다”를 보장하는 것이 최소원리이고, 그 위에 선 서식이 최소 반례법이다(§1.6). (d) 강한 귀납. 고정 보폭 2다. \(F_{k+1}\)이 \(F_k\)와 \(F_{k-1}\) 둘을 쓰므로 가정에 \(P(k-1)\)이 들어 있어야 하고, 보폭이 2이므로 기초도 두 개(\(F_1, F_2\))다.

문제 4#

접근. 뼈대는 기초 \(\to\) 강한 가정 선언 \(\to\) 경우 나누기 \(\to\) 정의 풀기 \(\to\) 강한 가정 소비 \(\to\) 조립이다. 자주 비는 곳은 둘이다: 경우 나누기가 전체를 덮는다는 근거와, \(1 < a, b < k+1\)을 \(2 \le a, b \le k\)로 바꾸는 줄이다.

풀이. 강한 귀납법으로 증명한다. [기초] \(n = 2\): 2의 양의 약수는 1과 2뿐이므로 2는 소수다(정의 15.2). ✓ [귀납] \(k \ge 2\)에 대해, \(2\)부터 \(k\)까지의 모든 정수가 소수이거나 소수들의 곱이라고 가정하자. \(k+1 \ge 3\)이므로 \(k+1\)은 소수이거나 합성수다(정의 15.2, 15.3과 15주차 문제 4의 다리 — 근거 ④). 경우 1: \(k+1\)이 소수. 그 자체로 명제가 성립한다. 경우 2: \(k+1\)이 합성수. 정의 15.3에 의해 \(k+1 = ab\)인 정수 \(a, b\) (\(1 < a, b < k+1\))가 존재한다. 정수에서 \(1 < a\)는 \(2 \le a\)와 같고 \(a < k+1\)은 \(a \le k\)와 같으므로 \(2 \le a \le k\), 마찬가지로 \(2 \le b \le k\)이다. 따라서 강한 귀납 가정을 \(a\)와 \(b\)에 각각 적용할 수 있고, 둘은 각각 소수이거나 소수들의 곱이므로 두 목록을 이어 붙이면 \(k+1 = ab\)는 소수들의 곱이다. 강한 귀납법에 의해 \(n \ge 2\)인 모든 정수에서 성립한다. \(\blacksquare\)

문제 5#

접근. 최소원리 4단 서식대로 ① 분모들의 집합 \(\to\) ② 유리수의 정의로 비공 확인 \(\to\) ③ 최소 분모 \(b_0\) \(\to\) ④-a 약분해 더 작은 분모를 만들어 모순. ②에서 한 걸음이 자주 빠진다 — 정의 15.1이 주는 것은 정수 표현이므로 부호를 맞춰 자연수 표현으로 고치는 줄이 있어야 \(b\)가 \(S\)의 원소가 된다. ④에서는 \(b_1 < b_0\)의 근거가 \(d > 1\)이라는 점을 명시해야 한다.

풀이. \(r\)를 양의 유리수라 하자. 집합 \(S = \{b \in \mathbb{N} : r = \frac{a}{b}\)인 \(a \in \mathbb{N}\)가 존재\(\}\)를 생각하자. 정의 15.1에 의해 \(r = \frac{a}{b}\)인 정수 \(a, b\) (\(b \neq 0\))가 존재한다. \(r > 0\)이므로 \(a \neq 0\)이고 \(a\)와 \(b\)는 같은 부호이며, 둘 다 음수이면 \((a, b)\)를 \((-a, -b)\)로 바꿔도 값이 같으므로 처음부터 \(a, b \in \mathbb{N}\)인 표현을 잡을 수 있다. 그 \(b\)가 \(S\)의 원소이므로 \(S \neq \varnothing\)이다. 최소원리에 의해 \(S\)는 최소원소 \(b_0\)을 가지며, \(r = \frac{a_0}{b_0}\)인 자연수 \(a_0\)을 하나 잡는다. 이 표현이 기약임을 귀류로 보인다. \(a_0\)과 \(b_0\)이 \(1\)보다 큰 공통 약수 \(d\)를 가진다고 가정하면 \(a_0 = d a_1\), \(b_0 = d b_1\)인 자연수 \(a_1, b_1\)이 존재하고 \(r = \frac{d a_1}{d b_1} = \frac{a_1}{b_1}\)이므로 \(b_1 \in S\)인데, \(d > 1\)이므로 \(b_1 = \frac{b_0}{d} < b_0\) — \(b_0\)의 최소성과 모순이다. 따라서 공통 약수는 \(\pm 1\)뿐이고 \(\frac{a_0}{b_0}\)은 기약분수다. \(\blacksquare\)

복기. 여기까지가 양의 유리수다. 21주차가 인정하고 쓴 것은 모든 유리수에 대한 진술이므로 \(r = 0\)(\(\frac{0}{1}\)이 기약)과 \(r < 0\)(\(-r\)의 기약 표현에 음부호를 옮긴다)의 확장 두 줄까지 적어야 회수가 끝난다 — 예제 2.3의 확장 단락과 같다.

문제 6#

접근. 예제 2.1이 주는 두 경우 각각에서 소수 하나를 지목하고 그것이 약수임을 정의 2.1로 확인한다. “소수들의 곱이면 그 소수가 약수다”를 넘기지 말고 등식으로 적는다.

풀이. \(n \ge 2\)인 정수라 하자. 예제 2.1에 의해 \(n\)은 소수이거나 소수들의 곱이다. \(n\)이 소수이면 \(n = n \times 1\)이므로 \(n \mid n\)이고, \(n\) 자신이 소수인 약수다. \(n\)이 소수들의 곱이면 \(n = p_1 p_2 \cdots p_t\) (\(t \ge 1\), 각 \(p_i\)는 소수)로 쓸 수 있고, \(n = p_1 \cdot (p_2 \cdots p_t)\)이며 \(p_2 \cdots p_t\)는 정수이므로 정의 2.1에 의해 \(p_1 \mid n\)이다. 따라서 어느 경우든 \(n\)은 소수인 약수를 가진다. \(\blacksquare\)

소비처. 21주차 예제 2.3(소수는 무한히 많다)이 이 사실을 첫 걸음으로 쓴다 — 유한한 소수 목록에서 \(N = p_1 p_2 \cdots p_t + 1\)을 만든 뒤 “\(N \ge 2\)는 소수인 약수 \(p\)를 가진다”로 시작한다. 이제 그 한 줄이 근거 ④가 되었으므로 그 증명이 자립한다.

문제 7#

접근. 빈칸을 채우는 것이 아니라 백지에서 전체를 쓴다. 검사할 것은 둘이다 — 경우 나누기가 전체를 덮는가, 경우 2에서 \(j \le k\)를 명시했는가(강한 가정을 쓸 자격).

풀이. 강한 귀납법으로 증명한다. [기초] \(n = 1\): \(1 = 2^0 \cdot 1\)이고 \(1\)은 홀수다. ✓ [귀납] 1부터 \(k\)까지의 모든 자연수에서 성립한다고 가정하자. 모든 정수는 짝수이거나 홀수이므로(나눗셈 정리 — 예제 2.2와 문제 10) 두 경우로 나눈다. 경우 1: \(k+1\)이 홀수. \(k+1 = 2^0 \cdot (k+1)\)이고 지수 \(0 \ge 0\)은 정수, \(k+1\)은 홀수이므로 꼴이 완성된다. 경우 2: \(k+1\)이 짝수. 정의 1.1에 의해 \(k+1 = 2j\)인 정수 \(j\)가 존재하고, \(k+1 \ge 2\)이므로 \(j \ge 1\)인 자연수이며, \(k \ge 1\)에서 \(k + 1 \le 2k\)이므로 \(j = \frac{k+1}{2} \le k\)이다. 따라서 강한 귀납 가정에 의해 \(j = 2^a m\) (\(a \ge 0\)은 정수, \(m\)은 홀수)이고, \(k+1 = 2j = 2^{a+1} m\)이다. 강한 귀납법에 의해 모든 자연수에서 성립한다. \(\blacksquare\)

검산. \(n = 40\): \(40 = 2 \cdot 20 = 2^2 \cdot 10 = 2^3 \cdot 5\)이고 5는 홀수다 ✓. 증명이 하는 일이 이 반복이며, “반복이 끝난다”를 보장하는 것이 강한 귀납 가정이다.

문제 8#

접근. 보폭이 3이므로 기초가 세 개다. 확인할 것은 하나 — \(k+1\)에서 3을 뺀 \(k-2\)가 가정 범위에 들어오는가. \(k+1 \ge 11\)이 정확히 \(k - 2 \ge 8\)을 주고, 남은 일은 3을 한 장 더 얹는 것뿐이다.

풀이. 강한 귀납법으로 증명한다. [기초] \(8 = 3 + 5\), \(9 = 3 \cdot 3\), \(10 = 5 \cdot 2\) ✓✓✓ (각각 \(a, b \ge 0\)). [귀납] \(k \ge 10\)에 대해, \(8\)부터 \(k\)까지의 모든 정수가 \(3a + 5b\) 꼴이라고 가정하자. \(k+1 \ge 11\)이므로 \(k + 1 - 3 = k - 2 \ge 8\)이고 \(k - 2 \le k\)이므로 \(k-2\)는 가정 범위 안에 있다. 강한 귀납 가정에 의해 \(k - 2 = 3a + 5b\)인 음이 아닌 정수 \(a, b\)가 존재한다. 그러면

\[ k + 1 = (k-2) + 3 = 3a + 5b + 3 = 3(a+1) + 5b \]

이고 \(a + 1 \ge 0\), \(b \ge 0\)이다. 강한 귀납법에 의해 \(n \ge 8\)인 모든 정수에서 성립한다. \(\blacksquare\)

논평 (예시). 강한 귀납 버전은 “3을 한 장 얹는다”는 한 수로 끝나 경우 나누기가 없다 — 32주차 문제 15의 교체 논법보다 짧다. 대신 기초를 세 개 확인해야 한다. 보폭 \(d\)짜리 강한 귀납에는 기초가 \(d\)개 — 잊으면 문제 17의 참사가 재연된다.

문제 9#

접근. 4단 서식으로 재현한다. ① 잔여들의 집합 \(\to\) ② \(q = 0\)으로 비공 확인 \(\to\) ③ 최소원소를 \(r\)로 명명 \(\to\) ④ \(r \ge n\)을 가정해 \(r - n \in S\)로 모순. \(r \ge 0\)은 ③에서, \(r < n\)은 ④에서 나온다.

풀이. 집합 \(S = \{a - nq : q \in \mathbb{Z},\ a - nq \ge 0\}\)을 생각하자. \(q = 0\)일 때 \(a - n \cdot 0 = a\)이고 가정에 의해 \(a \ge 0\)이므로 \(a \in S\)이고, 따라서 \(S\)는 공집합이 아닌 음이 아닌 정수들의 집합이다. 최소원리에 의해 \(S\)는 최소원소를 가지며, 그것을 \(r = a - nq_0\) (\(q_0 \in \mathbb{Z}\))이라 하자. \(r \in S\)이므로 \(r \ge 0\)이다. \(r < n\)을 귀류로 보인다. 만약 \(r \ge n\)이면

\[ r - n = (a - nq_0) - n = a - n(q_0 + 1) \ge 0 \]

이므로 \(r - n \in S\)이다. 그런데 \(n \ge 1\)이므로 \(r - n < r\)이고, 이는 \(r\)가 \(S\)의 최소원소라는 것과 모순이다. 따라서 \(r < n\)이다. 그러므로 \(q = q_0\), \(r = a - nq_0\)으로 두면 \(a = nq + r\)이고 \(0 \le r < n\)이다. \(\blacksquare\)

확장까지 재현한다. \(a \ge 0\)은 \(S \neq \varnothing\)을 확인한 줄에서만 쓰였으므로, \(a < 0\)일 때 \(q = a\)로 두면 \(n \ge 1\)에서 \(1 - n \le 0\)이고 \(a < 0\)이므로 \(a - na = a(1-n) \ge 0\), 곧 \(a - na \in S\)이다. 이후는 위와 같다. 이 두 줄이 있어야 “모든 정수 \(a\)”라는 17주차의 인정 범위가 실제로 회수된다.

문제 10#

접근. 두 표현을 하나의 등식에 놓고 분리하면 \(r - r' = n(q' - q)\), 곧 \(n \mid (r - r')\)이다. 한편 두 나머지가 \([0, n)\) 안이므로 차의 절댓값은 \(n\) 미만이다 — “배수인데 크기가 모자란다”는 상황에서 결론은 0뿐이다.

풀이. \(a = nq + r = nq' + r'\)이고 \(0 \le r, r' < n\)이라 하자. 두 표현을 같게 놓으면 \(nq + r = nq' + r'\)이고, 정리하면

\[ r - r' = n(q' - q) \]

이다. \(q' - q\)는 정수이므로 정의 2.1에 의해 \(n \mid (r - r')\)이다. 한편 \(0 \le r < n\)이고 \(0 \le r' < n\)이므로 \(-n < r - r' < n\), 곧 \(|r - r'| < n\)이다. “자연수 \(n\)과 정수 \(m\)에 대해 \(n \mid m\)이고 \(|m| < n\)이면 \(m = 0\)”이라는 보조정리 (25주차 예제 2.2)에 의해 \(r - r' = 0\), 즉 \(r = r'\)이다. 이를 위 등식에 대입하면 \(n(q' - q) = 0\)이고 \(n \ge 1 \neq 0\)이므로 \(q' - q = 0\), 즉 \(q = q'\)이다. \(\blacksquare\)

문제 11#

접근. §1.6의 서식을 그대로 따른다. 최소 반례 \(m\)을 잡고 \(n = 1\)의 직접 확인으로 \(m \ge 2\)를 얻으면, \(m - 1\)은 최소성에 의해 반례가 아니다. 남은 것은 양변에 \(m\)을 더하는 한 걸음이다.

풀이. 모순을 위해 공식이 성립하지 않는 자연수가 있다고 가정하자. 반례들의 집합 \(S = \{n \in \mathbb{N} : 1 + 2 + \cdots + n \neq \frac{n(n+1)}{2}\}\)은 공집합이 아니므로, 최소원리에 의해 최소원소 \(m\)이 존재한다. \(n = 1\)일 때 좌변은 \(1\), 우변은 \(\frac{1 \cdot 2}{2} = 1\)로 공식이 성립하므로 \(1 \notin S\)이고, 따라서 \(m \ge 2\)이다. 그러면 \(m - 1\)은 자연수이고 \(m - 1 < m\)이므로 \(m\)의 최소성에 의해 \(m - 1 \notin S\)이다. 곧

\[ 1 + 2 + \cdots + (m-1) = \frac{(m-1)m}{2} \]

이다. 양변에 \(m\)을 더하면

\[ 1 + 2 + \cdots + m = \frac{(m-1)m}{2} + m = \frac{(m-1)m + 2m}{2} = \frac{m(m+1)}{2} \]

이므로 \(m\)에서도 공식이 성립한다. 이는 \(m \in S\)라는 것과 모순이다. 따라서 \(S = \varnothing\)이고, 모든 자연수에서 공식이 성립한다. \(\blacksquare\)

복기. 31주차의 귀납 증명과 나란히 놓아 보면 자리만 바뀌었다 — 기초 확인이 “\(m \ge 2\)”를 만드는 데 쓰이고 귀납 단계가 “\(m-1 \to m\)”으로 방향을 바꿨을 뿐 계산은 같다(문제 20(a)의 근거). 이 증명의 ④는 ④-b 갈래다 — \(S\)의 더 작은 원소를 만든 것이 아니라, 최소성이 준 “\(m-1\)은 반례가 아니다”로 \(m\)도 반례가 아님을 보여 \(m \in S\)와 충돌시켰다. 예제 2.2\(\cdot\)2.3의 ④-a와 충돌 상대가 다르다(§2의 4단 서식).

문제 12#

접근. 문제 8과 같은 구조이고 숫자만 다르다. 보폭이 4이므로 기초가 네 개이고, 확인할 것은 \(k + 1 - 4 \ge 12\)인가이다 — \(k \ge 15\)에서 \(k - 3 \ge 12\)가 나온다.

풀이. 강한 귀납법으로 증명한다. [기초] \(12 = 4 \cdot 3\), \(13 = 4 \cdot 2 + 5\), \(14 = 4 + 5 \cdot 2\), \(15 = 5 \cdot 3\) ✓✓✓✓ (각각 \(a, b \ge 0\)). [귀납] \(k \ge 15\)에 대해, \(12\)부터 \(k\)까지의 모든 정수가 \(4a + 5b\) 꼴이라고 가정하자. \(k + 1 \ge 16\)이므로 \(k + 1 - 4 = k - 3 \ge 12\)이고 \(k - 3 \le k\)이므로 가정 범위 안에 있다. 강한 귀납 가정에 의해 \(k - 3 = 4a + 5b\)인 음이 아닌 정수 \(a, b\)가 존재하고, \(k + 1 = (k - 3) + 4 = 4(a+1) + 5b\)이다. 강한 귀납법에 의해 \(n \ge 12\)인 모든 정수에서 성립한다. \(\blacksquare\)

문제 13#

접근. (a)는 \(1 < \sqrt2 < 2\)의 각 변에 \(b_0 > 0\)을 곱하는 조작이다. (b)가 중심이다 — \(a_1^2\)과 \(2b_1^2\)을 전개한 뒤 \(a_0^2 = 2b_0^2\)을 대입해 비교한다. (c)는 (a)의 \(a_0 < 2b_0\)이 그대로 쓰인다.

풀이. (a) \(\sqrt2 = \frac{a_0}{b_0}\)이고 \(1^2 < 2 < 2^2\)이므로 \(1 < \sqrt2 < 2\)이다 (16주차의 제곱 비교). 곧 \(1 < \frac{a_0}{b_0} < 2\)이고, 각 변에 \(b_0 > 0\)을 곱하면 \(b_0 < a_0 < 2b_0\)이다. (b) (a)에서 \(a_0 - b_0 > 0\)이고 \(2b_0 - a_0 > 0\)이므로 \(a_1 = 2b_0 - a_0\)과 \(b_1 = a_0 - b_0\)은 모두 자연수다(정수의 차는 정수, 근거 ②). 가정의 양변을 제곱하면 \(a_0^2 = 2b_0^2\)이다. 이제 두 값을 각각 전개한다.

\[ a_1^2 = (2b_0 - a_0)^2 = 4b_0^2 - 4a_0b_0 + a_0^2 = 4b_0^2 - 4a_0b_0 + 2b_0^2 = 6b_0^2 - 4a_0b_0 \]
\[ 2b_1^2 = 2(a_0 - b_0)^2 = 2a_0^2 - 4a_0b_0 + 2b_0^2 = 4b_0^2 - 4a_0b_0 + 2b_0^2 = 6b_0^2 - 4a_0b_0 \]

(둘 다 마지막에서 두 번째 등호에서 \(a_0^2 = 2b_0^2\)을 대입했다.) 두 값이 같으므로 \(a_1^2 = 2b_1^2\)이고, \(b_1 > 0\)이므로 \(\left(\frac{a_1}{b_1}\right)^2 = 2\)이며 \(\frac{a_1}{b_1} > 0\)이다. 따라서 \(\frac{a_1}{b_1} = \sqrt2\)이다. (c) (a)에서 \(a_0 < 2b_0\)이므로 \(b_1 = a_0 - b_0 < 2b_0 - b_0 = b_0\)이다. 곧 \(\frac{a_1}{b_1}\)은 \(\sqrt2\)의 분수 표현이면서 분모가 \(b_0\)보다 작다 — \(b_0\)이 최소 분모라는 것과 모순이다. 따라서 \(\sqrt2\)의 자연수 분수 표현은 존재하지 않고, \(\sqrt2\)는 무리수다. \(\blacksquare\)

문제 14#

접근. 증명 대상이 명제가 아니라 원리라는 점만 다르고 안쪽은 최소 반례법 그대로다. 재료는 둘 — 기초는 \(m \neq 1\)을 만드는 데, 전달 장치는 \(m-1\)에서 \(m\)으로 넘어가는 데 쓰인다.

풀이. \(P(1)\)이 참이고 모든 \(k\)에서 \(P(k) \Rightarrow P(k+1)\)이 성립한다고 하자. 모순을 위해 \(P\)가 거짓인 자연수가 있다고 가정하면 반례들의 집합 \(S = \{n \in \mathbb{N} : P(n)\)이 거짓\(\}\)은 공집합이 아니고, 최소원리에 의해 최소원소 \(m\)을 가진다. \(P(1)\)이 참이므로 \(1 \notin S\), 곧 \(m \ge 2\)이다. 그러면 \(m - 1\)은 자연수이고 \(m - 1 < m\)이므로 \(m\)의 최소성에 의해 \(m - 1 \notin S\), 곧 \(P(m-1)\)이 참이다. 전달 장치를 \(k = m - 1\)에 적용하면 \(P(m)\)이 참인데 이는 \(m \in S\)와 모순이다. 따라서 \(S = \varnothing\)이고 모든 자연수 \(n\)에서 \(P(n)\)이 참이다 — 이것이 귀납법의 결론이다. \(\blacksquare\)

문제 15#

접근. 분해형 강한 귀납이다. 최대의 \(2^j\)를 떼어내고 잔여 \(r = k+1-2^j\)에 강한 가정을 적용한다. 확인할 것이 셋 — \(r\)이 자연수인가, \(r \le k\)인가, \(r < 2^j\)인가. 셋째가 “서로 다름”을 만드는 조각이다.

풀이. 강한 귀납법으로 증명한다. [기초] \(n = 1 = 2^0\) — 한 항짜리 합이다. ✓ [귀납] \(1\)부터 \(k\)까지 성립한다고 가정하자. \(k+1\)에 대해, \(2^j \le k+1\)인 최대의 \(j\)를 잡는다 (\(2^0 = 1 \le k+1\)이므로 그런 \(j\)가 존재하고, 후보는 유한한 음이 아닌 정수의 집합이므로 최대가 있다 — 도전 문제군 앞의 상자). 경우 1: \(2^j = k+1\). 그 자체로 한 항짜리 합이므로 완료된다. 경우 2: \(2^j < k+1\). \(r = k+1-2^j\)라 하면 \(1 \le r \le k+1-1 = k\)이므로 강한 귀납 가정에 의해 \(r\)는 서로 다른 2의 거듭제곱들의 합이다. 또한 \(r < 2^j\)이다 — 만약 \(r \ge 2^j\)이면 \(k+1 = 2^j + r \ge 2^{j+1}\)이 되어 \(j\)의 최대성과 모순이기 때문이다. 따라서 \(r\)의 표현에 등장하는 거듭제곱들은 전부 \(2^j\)보다 작고, 거기에 \(2^j\)를 보태도 서로 다름이 유지된다. 곧 \(k+1 = 2^j + r\)은 서로 다른 2의 거듭제곱들의 합이며, 강한 귀납법에 의해 모든 자연수에서 성립한다. \(\blacksquare\)

문제 16#

접근. (a)는 조건 “소수”의 하중을 재는 문제다. 소수가 아닌 \(p\)를 두 인수로 쪼개 \(a\)와 \(b\)에 하나씩 배정하면 결론이 무너진다(2주차 문제 15). (b)는 존재와 유일의 차이를 서술로 정리하는 문제다.

풀이. (a) \(p = 6\)으로 잡는다(\(6 = 2 \times 3\)이므로 소수가 아니다). \(a = 4\), \(b = 9\)라 하면 \(ab = 36 = 6 \times 6\)이므로 \(6 \mid 36\)이다. 그러나 \(4 = 6c\)인 정수 \(c\)도, \(9 = 6c\)인 정수 \(c\)도 없으므로 \(6 \nmid 4\)이고 \(6 \nmid 9\)이다. 곧 가정은 참인데 결론이 거짓이므로, 이 반례가 소수 조건이 본질적임을 보인다. (b) (예시 답안) 존재성은 “쪼개질 때까지 쪼갠다”로 도달하지만, 유일성은 “서로 다르게 쪼갠 두 결과가 반드시 일치한다”는 전혀 다른 주장이다. 한쪽 분해의 소수 \(p\)가 다른 쪽 분해의 곱을 나누므로, 유클리드 보조정리가 있어야 \(p\)가 그 곱의 어느 인수 하나를 나눈다고 결론할 수 있고 그 인수도 소수이므로 \(p\)와 같아진다. 이 장치가 없으면 겹치지 않는 두 분해의 공존을 배제할 방법이 없다.

문제 17#

접근. 결론부터 의심한다. 정의대로 계산하면 \(c_2 = 4 \neq 2\)에서 곧바로 반박된다. 제시된 증명의 계산은 한 줄도 틀리지 않았으므로 오류는 설정에 있다 — 참조하는 과거가 몇 칸 뒤인지 센다.

풀이. 결함. 점화식이 두 칸 전(\(c_{n-2}\))을 참조하므로 보폭이 2이고, 기초는 \(n = 1\)과 \(n = 2\) 두 개가 필요한데 제시된 증명은 \(c_1\) 하나만 확인했다. 또 귀납 단계의 등식 \(c_{k+1} = c_{k-1} + 2\)는 점화식의 정의상 \(k + 1 \ge 3\)에서만 뜻이 있으므로 \(P(2)\)를 만들어 내지 못한다. 곧 \(P(2)\)가 기초에서도 귀납에서도 확보되지 않아, 전달 장치는 짝수 번째 항 전체를 하나도 세우지 못한다. 반박. 정의대로 계산하면 \(c_2 = 4 \neq 2\)이고 \(c_4 = c_2 + 2 = 6 \neq 4\)이므로 명제는 거짓이다. 실제로 홀수 항은 \(c_{2m+1} = 2m+1\)로 참이지만 짝수 항은 \(c_{2m} = 2m + 2\)로 항상 2만큼 크다 — 명제가 절반에서만 성립한다.

문제 18#

접근. 최소원리는 수열이 아니라 집합에 적용된다. 항들의 값을 모두 모으면 공집합이 아닌 자연수의 부분집합이 되고, 그 최소원소에 이름을 붙이면 다음 항이 곧 모순이다.

풀이. 모순을 위해 그런 수열 \(a_1 > a_2 > a_3 > \cdots\) (모든 \(a_i \in \mathbb{N}\))가 존재한다고 가정하자. 값들의 집합 \(S = \{a_i : i \in \mathbb{N}\}\)을 생각하면 \(a_1 \in S\)이므로 \(S\)는 공집합이 아닌 자연수의 부분집합이다. 최소원리에 의해 \(S\)는 최소원소를 가지며, 그것은 어떤 항의 값이므로 \(a_m\)이라 쓸 수 있다. 그런데 수열이 순감소이므로 \(a_{m+1} < a_m\)이고 \(a_{m+1} \in S\)이다. 이는 \(a_m\)이 \(S\)의 최소원소라는 것과 모순이다. 따라서 그런 수열은 존재하지 않는다. \(\blacksquare\)

연결. 문제 13의 하강은 같은 조작을 반복해 \(b_0 > b_1 > b_2 > \cdots\)라는 순감소 무한 수열을 만들어 내므로 이 원리에 의해 애초에 불가능하다 — 최소원리를 수열의 언어로 바꿔 쓴 무한 강하법이다.

문제 19#

접근. (a)는 후보가 유한함을 먼저 보인다 — \(7b \le 17\)이므로 \(b \in \{0, 1, 2\}\)뿐이고, 각각에서 남은 금액이 4의 배수인지 확인한다. (b)는 보폭 4이고 구조는 문제 12와 같다.

풀이. (a) \(17 = 4a + 7b\)인 음이 아닌 정수 \(a, b\)가 있다고 하자. \(7b \le 17\)이므로 \(b \le 2\), 곧 \(b \in \{0, 1, 2\}\)다. \(b = 0\)이면 \(4a = 17\)인데 \(17 = 4 \cdot 4 + 1\)로 4의 배수가 아니다. \(b = 1\)이면 \(4a = 10\)인데 \(10 = 4 \cdot 2 + 2\)로 4의 배수가 아니다. \(b = 2\)이면 \(4a = 3\)인데 \(3\)은 4의 배수가 아니다. 세 경우가 후보 전부를 덮고 어느 경우에도 해가 없으므로 17원은 만들 수 없다. \(\blacksquare\) (b) 강한 귀납법으로 증명한다. [기초] \(18 = 4 + 7 \cdot 2\), \(19 = 4 \cdot 3 + 7\), \(20 = 4 \cdot 5\), \(21 = 7 \cdot 3\) ✓✓✓✓. [귀납] \(k \ge 21\)에 대해, \(18\)부터 \(k\)까지의 모든 정수가 \(4a + 7b\) 꼴이라고 가정하자. \(k+1 \ge 22\)이므로 \(k + 1 - 4 = k - 3 \ge 18\)이고 \(k - 3 \le k\)이므로 가정 범위 안에 있다. 강한 귀납 가정에 의해 \(k - 3 = 4a + 7b\)이고, \(k + 1 = (k-3) + 4 = 4(a+1) + 7b\)이다. 강한 귀납법에 의해 \(n \ge 18\)인 모든 정수에서 성립한다. \(\blacksquare\)

복기. (a)와 (b)를 합치면 17이 마지막 불가능 금액이다. 서로소인 \(m, n\) 우표에 대해 그 값은 \(mn - m - n\)이며(정수론의 프로베니우스 수), 여기서는 \(4 \cdot 7 - 4 - 7 = 17\)로 일치한다.

문제 20#

접근. (a)는 문제 14(최소원리에서 귀납법이 나온다)와 문제 11(같은 명제가 두 문법으로 증명된다)을 근거로 든다. (b)는 정답이 하나가 아니지만 근거가 §1.4의 신호와 §1.6의 쓰임 표에 닿아 있어야 한다.

풀이. (예시 답안) (a) 최소원리에서 귀납법이 유도되고(문제 14), 귀납법으로 증명되는 것은 최소 반례법 으로도 증명된다(문제 11에서 두 뼈대가 그대로 겹쳤다). 강한 귀납법은 보통 귀납의 가정을 넓힌 것이므로 셋은 서로를 유도한다. 곧 셋은 자연수의 같은 성질 — 1에서 시작해 한 칸씩 세어 나가고 무한히 작아지는 하강은 없다 — 을 세 가지 문법으로 적은 것이다. (b) (예시) ① 명제가 \(n\)에 대한 등식\(\cdot\)부등식이고 \(k+1\)의 식에서 \(k\)의 식이 바로 보이면 보통 귀납을 꺼낸다. ② \(k+1\)이 곱으로 쪼개지거나 성질이 몇 칸 뒤에서 오면 강한 귀납을 꺼내고 보폭만큼 기초를 확인한다. ③ “~은 존재하지 않는다”, “모든 표현은 ~”처럼 반례나 후보 집합을 상정하기 좋은 꼴이면 최소원리를 먼저 스케치한다.

다음 주 예고: 점화식으로 정의된 수열을 다룬다. 피보나치 수열을 무대로 “추측하고 귀납으로 확정하는” 실전 순환을 익히고, 두 칸 보폭 귀납(기초 두 개)을 반복 훈련한다. \(F_1^2 + \cdots + F_n^2 = F_n F_{n+1}\) 같은 항등식이 증명 대상이 되며, 이번 주 §1.4의 보폭 규칙과 문제 17의 진단이 그대로 재사용된다.