C8주차 — 귀납법: 일반 원리와 최소 반례

이 주의 길잡이

핵심 문장: 귀납의 세 형태는 가정의 폭과 논법의 방향만 다르다 — 약한 귀납은 직전 하나를 가정하고, 강한 귀납은 지금까지 전부를 가정하며, 최소 반례법은 같은 계산을 귀류 쪽에서 적는다. 셋 다 자연수의 최소원리 하나에서 나온다.

이 주의 위치: 2학기 20주 과정의 C8주차. C7주차에서 세운 귀류와 최소원리가 여기서 결합해 최소 반례법이라는 정식 기법이 된다. C7주차 문제 17에서 최소 해를 잡아 더 작은 해를 만들어 낸 그 동작이 이번 주에 무한강하라는 이름을 얻는다. 1권 31~33주차와 S14주차가 여기서 한 장으로 다시 조직된다.

원서 대응: Chartrand 6장 (Mathematical Induction). 1일차에 이 장을 통독한 상태로 이 교안에 온다.

이번 주 목표

1. 약한 귀납의 2단 구조를 절차로 다시 적고, “귀납 단계 = 조건문 증명”(S14주차)을 걸음 삭제 실험으로 재확인한다.

2. 강한 귀납을 “의존의 폭”이라는 기준으로 판정해 소인수분해\(\cdot\)점화식\(\cdot\)도약 무대에서 운용한다.

3. 최소 반례법을 5단 서식으로 세운다 — C7주차의 귀류와 1권 33주차의 최소원리가 결합한 기법이다.

4. 세 형태가 최소원리의 세 표현임을 확인하고, 명제를 보고 형태를 고르는 세 물음을 세운다.

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

표기 — § 와 난이도 표시

§는 “절”이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다.

다른 주차를 가리킬 때는 “S14주차 §1.4”처럼 주차를 앞에 적는다.

연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서

3으로 갈수록 지지대가 줄어든다.

준비 운동 (C7주차 복습)

지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다.

1. 반례 답안의 4단 서식(부정 전개 \(\to\) 증인 제시 \(\to\) 자격 검증 \(\to\) 사건 검증)을 쓰시오 (C7주차).

2. 귀류 답안의 4단 서식과 모순의 3대 산지를 쓰시오 (C7주차).

3. 최소원리(정렬성)를 진술하시오 (1권 33주차).

이어서 진단 문제 하나를 풀어 보자. 풀지 못해도 된다 — 이번 주가 무엇을 메우는지 가늠하기 위한 기록이다.

1. (진단) “2 이상의 모든 정수는 소수이거나 소수들의 곱이다”를 귀납법으로 증명해 보자.

답을 노트에 적어 둔다. §5의 백지 재현 뒤에 이 기록을 다시 본다.

자주 나오는 세 가지 답

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 자연스러운 출발점이고, 셋 다 이번 주에 메울 정확한 간격이 있다.

• 유형 1 — 분해까지 갔으나 가정을 넓히지 않았다. “기저는 \(n = 2\). 귀납 가정으로

\(P(n)\) 을 놓고, \(n+1\) 이 합성수이면 \(n+1 = ab\) 로 쪼갠 뒤 가정에 의해 \(a\) 와 \(b\) 가 소수들의 곱이라 하자” — 이렇게 적는 경우가 많다. 분해는 정확히 옳은 동작이고 이 명제의 유일한 관절이다. 간격은 한 줄 뒤에 있다. 가정한 것은 \(P(n)\) 하나인데 쓴 것은 \(P(a)\) 와 \(P(b)\) 다. \(a\) 가 하필 \(n\) 이라는 보장은 어디에도 없다(§1.1).

• 유형 2 — 결론을 이미 아는 사실로 인정했다. “소인수분해는 늘 되니까”로 넘어간

경우다. 결론이 참이라는 판단은 옳다. 간격은 그 참을 지금 증명하는 중이라는 것이다. 증명 대상과 같은 문장을 근거로 인용하면 순환이 된다(문제 10이 같은 병을 다룬다).

• 유형 3 — 백지. 기저와 귀납 단계의 서식은 아는데 \(n+1\) 을 무엇으로 쪼갤지

정하지 못했다. 쪼갤 것을 정하는 기준 자체가 규칙으로 있고, §1.3이 그 기준을 “의존의 폭”이라는 이름으로 제시한다.

개념 — 귀납의 세 형태

1 약한 귀납만으로 밀어붙이면 어디서 막히는가

새 형태를 꺼내기 전에, 지금 가진 것 — 1권 31주차와 S14주차의 약한 귀납 — 만으로 두 명제를 실제로 밀어붙여 본다.

시도 1 — 준비 운동 4번을 약한 귀납으로

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

“(기저) \(n = 2\) 는 소수다.

(귀납 단계) \(P(n)\) 을 가정하자 — \(n\) 은 소수이거나 소수들의 곱이다.

\(n+1\) 이 소수이면 그것으로 끝이다. \(n+1\) 이 합성수이면 \(n+1 = ab\) 이면서

\(2 \le a \le n\), \(2 \le b \le n\) 인 정수 \(a, b\) 가 존재한다.

이제 \(a\) 가 소수들의 곱임을 말해야 하는데 … “

여기서 멈춘다. 손에 있는 것은 \(P(n)\) 하나인데, 필요한 것은 \(P(a)\) 와 \(P(b)\) 다.

시도 2 — C7주차 문제 17을 귀납으로

명제: \(x^2 = 2y^2\) 인 양의 정수 \(x, y\) 는 존재하지 않는다.

“귀납을 걸려면 사다리의 칸을 세는 변수 \(n\) 이 필요하다. 그런데 이 명제에는

그런 \(n\) 이 없다. 무엇에 대해 기저를 잡고 무엇을 한 칸 올릴지가 정해지지 않으므로

첫 줄이 나오지 않는다.”

두 시도가 막힌 이유는 서로 다르다.

확인 1. 시도 1과 시도 2가 막힌 이유는 각각 무엇인가. 한쪽은 “가정이 좁아서”이고 다른 한쪽은 그것이 아니다. 어느 쪽이 어느 쪽인가.

답

시도 1은 가정의 폭 문제다. 명제는 참이고 쪼개기도 옳은데, 약한 귀납이 주는

출발점이 \(P(n)\) 하나뿐이라 \(a\) 와 \(b\) 를 덮지 못한다. 출발점을 \(P(2), \ldots, P(n)\)

전부로 넓히면 그 자리에서 풀린다 — §1.3의 강한 귀납이다.

시도 2는 가정의 폭 문제가 아니다. 귀납을 걸 변수가 없다. 명제가 “그런 것은

없다”는 부재 주장이라 한 칸씩 올릴 대상 자체가 무대에 없다. 이런 명제는 먼저

귀류로 대상을 하나 받아 낸 뒤(C7주차) 그중 가장 작은 것을 잡아야 손이 걸린다 —

§1.4의 최소 반례법이다.

이 주 전체의 기준

귀납이 막히면 두 가지를 검사한다.

① 귀납 단계에서 쓴 것이 가정한 것보다 넓은가 \(\to\) 가정을 넓힌다(강한 귀납).

② 애초에 올릴 사다리가 없는가 \(\to\) 반례를 가정하고 그중 최소인 것을 잡는다(최소 반례법).

2 약한 귀납의 원리 — 절차로 다시 적기

1권 31주차에서 서식으로 익히고 S14주차에서 조건문 증명으로 분해한 그 원리를, 이번에는 Chartrand가 쓰는 꼴 — 시작점 \(n_0\) 을 명시한 꼴 — 로 적는다.

정의 8.1 — 귀납의 원리 (principle of mathematical induction) [백지 암기 대상]

정수 \(n_0\) 이상의 모든 정수 \(n\) 에 대해 \(P(n)\) 이 참임을 보이려면, 다음 두 가지를

보이면 충분하다.

① 기저 단계: \(P(n_0)\) 이 참이다.

② 귀납 단계: \(n_0\) 이상의 모든 정수 \(n\) 에 대해, \(P(n)\) 이 참이면 \(P(n+1)\) 도 참이다.

표기 — \(P(n)\) 과 \(n_0\)

\(P(n)\) 은 “피 엔”이라 읽고, \(n\) 이 정해질 때마다 참\(\cdot\)거짓이 정해지는 문장 하나를

가리킨다. “\(P(n)\) 을 가정한다”는 그 문장을 참이라고 놓는다는 뜻이다.

\(n_0\) 은 “엔 제로”라 읽고 사다리의 첫 칸을 가리킨다. 1권 31주차는 \(n_0 = 1\) 인

경우를 주로 다루었고, 여기서는 \(n_0\) 이 \(4\) 나 \(8\) 인 명제도 함께 다룬다.

식 자체에 새로운 것은 없다. 1권 31주차의 “기초 단계 + 귀납 단계”와 글자 하나 다르지 않다. 새로 하는 일은 이 두 줄을 답안의 걸음으로 펼쳐, 걸음마다 무엇을 막고 있는지를 확인하는 것이다.

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 기저 확인	사다리의 첫 칸을 실제로 놓는다	전달만 남고 출발점이 없다. 거짓 명제도 통과한다 (아래 삭제 실험)
② 귀납 가정 선언	조건문의 출발점을 이름 있는 문장으로 무대에 올린다	무엇을 소비할지 정해지지 않아 아래 ④에서 쓸 대상이 없다
③ 쪼개기	\(P(n+1)\) 의 식 안에서 \(P(n)\) 의 식이 보이도록 재그룹한다	가정을 대입할 자리가 생기지 않는다. 귀납이 막히는 자리의 대부분이 여기다
④ 가정 소비	드러난 자리에 가정을 실제로 대입한다	가정 미소비 — 증명 대상을 다른 이름으로 인용하게 된다 (문제 10)
⑤ 결론 선언	두 단계가 모두 갖춰졌음을 밝히고 명제를 선언한다	무엇이 증명되었는지가 답안에 없다

걸음 삭제 실험 — ①을 빼면. 기저 확인 의무를 지우면 다음 답안이 합법이 된다.

삭제 실험 — 기저 없는 귀납

명제: 모든 자연수 \(n\) 에 대해 \(n = n + 1\) 이다.

“귀납 단계만 보이겠다. \(P(n)\) 을 가정하자 — 곧 \(n = n+1\) 이다. 양변에 \(1\) 을

더하면 \(n + 1 = n + 2\) 이고, 이것이 곧 \(P(n+1)\) 이다. 따라서 귀납 단계가 성립하므로

모든 자연수에서 \(n = n+1\) 이다.”

확인 2. 위 답안에서 참인 문장과 거짓인 문장을 갈라 보자. 귀납 단계 자체는 참인가 거짓인가. 그리고 결론이 거짓인 이유를 한 문장으로 적어 보자.

답

귀납 단계는 참이다. “\(n = n+1\) 이면 \(n+1 = n+2\) 이다”는 전건이 거짓인 조건문이고,

조건문은 전건이 거짓일 때 참이다(C5주차의 공허한 증명). 곧 이 답안의 계산에는

틀린 줄이 하나도 없다.

거짓인 것은 결론이다. 전달 법칙만 있고 첫 칸이 없으면 사다리 전체가 공중에 뜬다 —

\(P(1)\) 이 거짓이므로 \(P(2)\) 로 갈 출발점이 애초에 없다. 1권 31주차 문제 17이 같은

결함을 다룬다. 귀납 답안의 검사는 계산 검사이기 전에 두 걸음의 존재 검사다.

확인 3. 다음 답안에는 다섯 걸음 중 세 개가 비어 있다. 어느 걸음인가. 그리고 그 결과로 생기는 병의 이름을 적어 보자. “명제: 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n i = \frac{n(n+1)}2\). 증명: (기저) \(n=1\) 에서 \(1 = \frac{1 \cdot 2}2\) 로 성립한다. (귀납 단계) \(\sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}2\) 임을 보이자. 등차수열의 합 공식에 의해 이 값은 \(\frac{(n+1)(n+2)}2\) 이다. 따라서 성립한다.”

답

비어 있는 걸음은 ② 귀납 가정 선언, ③ 쪼개기, ④ 가정 소비다. “(귀납 단계)” 뒤에

곧바로 도착점 “\(\sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}2\) 임을 보이자”만 적혀 있고

“\(P(n)\) 을 가정하자”에 해당하는 줄이 없다. ②가 비었으므로 소비할 대상 자체가 무대에

없고, 그래서 ③과 ④도 불가능해졌다 — ②의 부재가 나머지 둘의 부재를 부른 원인이다.

실제로 답안 어디에도 \(\sum_{i=1}^{n+1} i\) 를

\(\left(\sum_{i=1}^{n} i\right) + (n+1)\) 로 재그룹한 줄이 없고, 따라서 가정 \(P(n)\) 이

한 번도 쓰이지 않았다.

병의 이름은 가정 미소비이고, 그 결과가 순환이다 — 인용한 “등차수열의 합 공식”이

곧 지금 증명하려는 명제 자신이기 때문이다(S14주차 문제 12). 진단의 기준 하나:

답안에서 “가정에 의해”라고 적힌 줄을 손가락으로 짚을 수 없으면 그 답안은 미완성이다.

3 의존의 폭 — 사례를 모아 보고 이름 붙이기

약한 귀납이 통하는 명제와 통하지 않는 명제를 가른 것은 무엇이었는가. 네 명제를 놓고, \(P(n+1)\) 을 쪼갠 결과와 그 결과가 실제로 요구하는 이전 항을 적어 보자.

명제	\(P(n+1)\) 을 쪼갠 결과	실제로 필요한 이전 항
\(\sum_{i=1}^n i = \frac{n(n+1)}2\)	\(\sum_{i=1}^{n+1} i = \left(\sum_{i=1}^n i\right) + (n+1)\)	\(P(n)\) 하나
피보나치 수열의 부등식	\(F_{n+2} = F_{n+1} + F_n\)	\(\underline{\quad(1)\quad}\)
소인수분해의 존재	\(n+1 = ab\), \(2 \le a \le n\), \(2 \le b \le n\)	\(\underline{\quad(2)\quad}\)
\(n \ge 8\) 은 3원\(\cdot\)5원으로 지불 가능	\(n+1 = (n-2) + 3\)	\(\underline{\quad(3)\quad}\)

확인 4. 표의 (1)(2)(3)을 채우고, 아래 세 행이 첫 행과 공통으로 어긋나는 지점을 한 문장으로 적어 보자.

답

(1) \(P(n)\) 과 \(P(n+1)\) 두 항 — 직전과 그 앞이 함께 필요하다.

(2) \(P(a)\) 와 \(P(b)\) — 어느 항인지 미리 알 수 없고, \(2\) 와 \(n\) 사이 어디든 될 수 있다.

(3) \(P(n-2)\) 한 항 — 하나면 되지만 그것이 직전이 아니다.

공통으로 어긋나는 지점: 필요한 이전 항이 직전 하나가 아니다. 약한 귀납이 주는

출발점은 정확히 직전 하나뿐이므로, 세 경우 모두 출발점이 부족하다.

부족하면 넓히면 된다. 이 관찰에 정식 이름과 형식을 붙인다.

정의 8.2 — 강한 귀납법 (strong induction) [백지 암기 대상]

정수 \(n_0\) 이상의 모든 정수 \(n\) 에 대해 \(P(n)\) 이 참임을 보이려면, 다음 두 가지를

보이면 충분하다.

① 기저 단계: \(P(n_0), P(n_0+1), \ldots, P(n_0+k-1)\) 이 참이다 (필요한 개수 \(k\) 만큼).

② 귀납 단계: \(n \ge n_0 + k - 1\) 인 모든 정수 \(n\) 에 대해, \(n_0 \le i \le n\) 인 모든 \(i\) 에서 \(P(i)\) 가 참이면 \(P(n+1)\) 도 참이다.

두 정의의 차이는 두 군데다. 정의 8.1과 정의 8.2를 나란히 놓으면 다른 곳이 둘이다. 첫째, 귀납 단계의 출발점이 “\(P(n)\)” 에서 “\(P(n_0)\) 부터 \(P(n)\) 까지 전부”로 넓어졌다 — 가정의 폭이다. 둘째, 기저가 \(k\) 개로 늘면서 귀납 단계가 성립해야 할 범위의 시작점도 \(n_0\) 에서 \(n_0 + k - 1\) 로 함께 올라갔다. 두 변화는 묶여 있다. 기저를 \(k\) 개 두었다는 것은 \(n_0 + k - 1\) 까지를 손으로 채웠다는 뜻이고, 귀납 단계는 그 위에서만 돌면 된다. 절차 자체에 새로운 것은 없다 — 확인 4의 표에서 부족하다고 판정한 만큼을 채웠을 뿐이다. 아래 확인 5가 계산하는 것이 정확히 이 둘째 차이, 곧 \(k\) 를 정하는 일이다.

기저 개수 삭제 실험 — 기저를 하나만 두면. 강한 귀납에서 기저가 몇 개 필요한지는 취향이 아니라 계산이 정한다. 확인 4의 넷째 행 무대에서 실험한다.

삭제 실험 — 기저를 \(n = 8\) 하나만 둔 답안

명제: \(8\) 이상의 모든 정수는 3원과 5원 동전으로 지불할 수 있다.

“(기저) \(8 = 3 + 5\).

(귀납 단계) \(8\) 부터 \(n\) 까지 전부 지불 가능하다고 가정하자. \(n+1\) 을 지불하려면

\((n+1) - 3 = n - 2\) 를 지불한 뒤 3원을 얹으면 된다. 가정에 의해 \(n-2\) 는 지불

가능하다.”

확인 5. 위 답안이 실제로 실패하는 \(n+1\) 값을 모두 찾아 보자. 그리고 기저를 몇 개 두어야 하는지, 그 개수를 정하는 것이 무엇인지 적어 보자.

답

\(n+1 = 9\) 와 \(n+1 = 10\) 에서 실패한다. 각각 \(n-2 = 6\), \(n-2 = 7\) 인데 둘 다 \(8\) 보다

작아 가정의 사정권 밖이다 — 가정에는 \(P(6)\) 도 \(P(7)\) 도 들어 있지 않다.

따라서 기저는 \(8, 9, 10\) 의 세 개가 필요하다. 개수를 정하는 것은 **되돌아보는

보폭**이다. 귀납 단계가 \(P(n-2)\) 를 쓰므로 보폭이 \(3\) 이고, 보폭만큼의 칸을 손으로

채워 두어야 그 다음부터 재귀가 돈다. 1권 33주차 문제 8이 같은 계산을 다룬다.

4 최소 반례법 — 귀류와 최소원리가 만나는 자리

시도 2가 막힌 이유는 올릴 사다리가 없다는 것이었다. 그런데 이미 그런 명제를 상대해 본 적이 있다. 세 논증을 놓고, 각각이 “가장 작은 것”을 어디에 쓰는지 적어 보자.

어디서 본 논증	최소로 잡은 것	그 최소성을 소비한 자리
1권 33주차 문제 13 (\(\sqrt2\))	분모가 최소인 표현 \(\frac{a_0}{b_0}\)	분모가 더 작은 표현을 만들어 최소성과 충돌시켰다
C7주차 문제 17 (\(x^2 = 2y^2\))	\(x\) 가 최소인 해 \((x, y)\)	\(\underline{\quad(1)\quad}\)
1권 33주차 문제 11 (합 공식)	\(\underline{\quad(2)\quad}\)	\(\underline{\quad(3)\quad}\)

확인 6. 표의 (1)(2)(3)을 채우고, 세 논증이 공통으로 수행한 동작을 한 문장으로 적어 보자.

답

(1) \(x' = \frac x2\) 인 더 작은 해 \((x', y')\) 을 실제로 만들어 \(x\) 의 최소성과 충돌시켰다.

(2) 공식이 성립하지 않는 자연수, 곧 반례들 중 가장 작은 것 \(m\).

(3) \(m\) 보다 작은 \(m-1\) 은 반례가 아니라는 사실을 써서 \(P(m)\) 을 유도하고, “\(m\) 은

반례다”와 충돌시켰다.

공통 동작: **반례(또는 해)가 있다고 가정하고, 그중 가장 작은 것을 잡아, 그보다

작은 곳에서 얻은 참으로 모순을 만든다.** 셋 다 최소원리 없이는 “가장 작은 것”을

잡는 첫 줄부터 적을 수 없다.

이 동작에 정식 이름과 서식을 붙인다.

정의 8.3 — 최소 반례법 (proof by smallest counterexample) [백지 암기 대상]

정수 \(n_0\) 이상의 모든 정수 \(n\) 에 대해 \(P(n)\) 임을 보이려면:

① 귀류 개시 — \(P(n)\) 이 거짓인 \(n \ge n_0\) 이 존재한다고 가정한다.

② 최소 반례 확보 — 반례들의 집합은 공집합이 아니고, \(n_0 \ge 1\) 인 이번 주의 무대에서는 그것이 공집합이 아닌 양의 정수 집합이다. 따라서 §1.7에 등록된 최소원리에 의해 최소원소 \(m\) 이 존재한다.

③ 기저 배제 — \(P(n_0)\) 이 참임을 직접 확인해 \(m \neq n_0\), 곧 \(m > n_0\) 임을 얻는다. 따라서 \(m - 1 \ge n_0\) 이다.

④ 최소성 소비와 모순 — \(m-1\) 은 \(m\) 보다 작으므로 반례가 아니다. 곧 \(P(m-1)\) 이 참이고, 이로부터 \(P(m)\) 을 유도해 “\(m\) 은 반례다”와 충돌시킨다.

⑤ 결론 복귀 — 반례가 존재하지 않으므로 \(n_0\) 이상의 모든 \(n\) 에서 \(P(n)\) 이다.

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 귀류 개시	없다고 말하려는 대상을 일단 무대에 올린다	잡을 대상이 없어 최소원리를 적용할 집합이 만들어지지 않는다
② 최소 반례 확보	최소원리로 “가장 작은” 하나를 특정한다	아무 반례나 잡으면 그보다 작은 곳의 참을 주장할 근거가 없다
③ 기저 배제	\(m-1\) 이 무대 안에 있음을 보장한다	\(m-1\) 이 무대 밖으로 나가 ④의 \(P(m-1)\) 이 뜻을 잃는다 (아래 삭제 실험)
④ 최소성 소비와 모순	최소성을 실제로 쓰고 충돌한 두 문장을 지목한다	최소성을 쓰지 않은 귀류가 되어 아무 데도 닿지 않는다
⑤ 결론 복귀	부정 가정을 철회하고 원 명제를 선언한다	모순만 적히고 무엇이 증명되었는지가 없다

걸음 삭제 실험 — ③을 빼면. 기저 배제 의무를 지우면 다음 답안이 합법이 된다.

삭제 실험 — 기저를 배제하지 않은 답안

명제: 모든 자연수 \(n\) 에 대해 \(\sum_{i=1}^n (2i-1) = n^2\) 이다.

“반례가 있다고 가정하고 최소 반례를 \(m\) 이라 하자. \(m\) 이 최소이므로 \(m-1\) 은

반례가 아니고, 따라서 \(\sum_{i=1}^{m-1}(2i-1) = (m-1)^2\) 이다. 여기에 \((2m-1)\) 을

더하면 \(m^2\) 이므로 \(m\) 은 반례가 아니다. 모순.”

확인 7. 위 답안에서 \(m = 1\) 인 경우를 따로 따라가 보자. \(m-1\) 은 얼마이고, 그때 \(\sum_{i=1}^{m-1}(2i-1)\) 은 무엇을 뜻하는가.

답

\(m - 1 = 0\) 이고, \(\sum_{i=1}^{0}(2i-1)\) 은 항이 하나도 없는 합이다. 자연수를 무대로

삼은 이 명제에서는 \(P(0)\) 이라는 문장 자체가 정의되어 있지 않으므로, “\(m-1\) 은

반례가 아니다”라는 문장이 아무것도 말하지 못한다. 곧 \(m = 1\) 인 경우에 논증이

통과하지 못한다.

수리 방법은 걸음 ③ 그대로다. \(n = 1\) 에서 \(\sum_{i=1}^1 (2i-1) = 1 = 1^2\) 임을 먼저

확인해 \(1\) 이 반례가 아님을 밝히면 \(m \ge 2\) 가 확보되고, 그때 \(m-1 \ge 1\) 이

자연수가 된다. 최소 반례법의 걸음 ③은 약한 귀납의 기저 단계가 자리를 옮겨 앉은 것이다.

확인 8. 최소 반례법의 다섯 걸음 중 정의 8.1의 기저 단계에 대응하는 것과 귀납 단계에 대응하는 것을 각각 고르고, 무엇이 뒤집혀 있는지 한 문장으로 적어 보자.

답

기저 단계에 대응하는 것은 ③ 기저 배제이고, 귀납 단계에 대응하는 것은 ④ 최소성

소비다. 계산 내용은 양쪽이 완전히 같다 — 둘 다 “\(P(k-1)\) 에서 \(P(k)\) 로 가는 한 칸”을

만든다.

뒤집힌 것은 그 한 칸을 쓰는 방향이다. 약한 귀납은 그 칸을 타고 위로 올라가고,

최소 반례법은 그 칸으로 “가장 아래 칸에서 이미 참이었다”를 만들어 최소성을 깨뜨린다.

그래서 최소 반례법을 귀납의 귀류판이라 부른다(S14주차 문제 14).

5 무한강하 — 걸음 ④의 다른 실행 방식

최소 반례법의 걸음 ④에는 두 가지 실행 방식이 있다. 하나는 \(P(m-1)\) 에서 \(P(m)\) 을 유도하는 방식이고(정의 8.3의 기본형), 다른 하나는 최소 반례에서 더 작은 반례를 실제로 만들어 최소성과 직접 충돌시키는 방식이다. 뒤쪽을 무한강하(infinite descent)라 부른다.

백지 암기 대상

무한강하

조건을 만족하는 대상이 존재한다고 가정하고, 그중 어떤 양이 최소인 것을 잡는다.

그 대상에서 같은 조건을 만족하면서 그 양이 더 작은 대상을 실제로 구성한다.

최소성과 충돌하므로 그런 대상은 존재하지 않는다.

C7주차 문제 17에서 \(x^2 = 2y^2\) 의 최소 해를 잡아 \(x' = \frac x2\) 인 해를 만들어 낸 그 동작이 바로 이것이다. 1권 33주차 문제 13에서 분모가 최소인 표현을 잡아 더 작은 분모의 표현을 만들어 냈던 그 계산이, 여기서 무한강하라는 이름을 얻는다.

확인 9. 정의 8.3의 기본형과 무한강하는 무엇이 다른가. “\(m-1\)” 이라는 낱말을 써서 한 문장으로 구분해 보자.

답

기본형은 \(m-1\) 이라는 정해진 대상의 참을 최소성에서 받아 와 \(P(m)\) 을 유도한다.

무한강하는 \(m-1\) 을 쓰지 않는다 — 최소 반례에서 계산으로 새로운 더 작은 반례를

만들어 낸다. 한 칸 아래가 필요한지, 얼마만큼이든 아래가 필요한지가 갈림길이다.

정수 무대에서는 둘 다 최소원리 하나에 기대므로 논리적 힘이 같다.

6 세 형태와 최소원리의 관계

형태	귀납 단계의 출발점	논법의 방향	대표 무대
약한 귀납	\(P(n)\) 하나	순방향 연쇄	합 공식\(\cdot\)나누어떨어짐\(\cdot\)부등식
강한 귀납	\(P(n_0), \ldots, P(n)\) 전부	누적 순방향	소인수분해\(\cdot\)점화식\(\cdot\)보폭 있는 도약
최소 반례	최소 반례보다 작은 곳은 전부 참	귀류 + 최소원리	부재 명제\(\cdot\)하강이 자연스러운 무대

확인 10. 세 형태의 논리적 힘을 비교해 보자. 어느 하나로 증명되는 명제가 다른 것으로는 증명되지 않는 경우가 있는가.

답

없다. 셋은 논리적으로 동치이며 전부 자연수의 최소원리에서 나온다. 1권 33주차

문제 14가 “최소원리로 약한 귀납을 유도하는” 방향을, S14주차 문제 20이 세 형태가

한 원리의 세 표현임을 다룬다. 문제 19에서 같은 명제를 두 형태로 증명해 이 동치를

손으로 확인한다.

그러므로 형태의 선택은 참\(\cdot\)거짓의 문제가 아니라 답안이 짧아지는가의 문제다.

백지 암기 대상

형태 선택의 세 물음

① \(P(n+1)\) 을 쪼갰을 때 필요한 이전 항이 직전 하나인가 \(\to\) 약한 귀납.

② 필요한 이전 항이 여럿이거나 어느 것인지 미리 알 수 없는가 \(\to\) 강한 귀납. 기저 개수는 되돌아보는 보폭이 정한다.

③ 올릴 사다리가 없는 부재 명제인가, 또는 반례에서 더 작은 반례를 만들 길이 보이는가 \(\to\) 최소 반례법(무한강하).

1권 33주차 문제 20에서 “셋이 한 가족”이라고만 적었던 관계가 이 표로 굳는다.

7 이번 주에 쓸 수 있는 근거 — 목록 갱신

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식의 성질 ④ 이미 증명한 명제. 이번 주에 ④로 등록되거나 인정하고 쓰는 항목은 다음과 같다. 답안에서 인용할 때는 이름을 밝히고 그 가정이 충족되었음을 확인한 뒤 결론을 가져온다.

이번 주에 인용하는 기성 사실	진술	출처와 취급
최소원리(정렬성)	공집합이 아닌 양의 정수 집합에는 최소원소가 있다	1권 33주차. 이번 주 세 형태 전체의 토대이며, 증명 없이 인정하고 쓴다
합성수의 분해	합성수 \(N\) 에는 \(N = ab\) 이면서 \(1 < a < N\), \(1 < b < N\) 인 정수 \(a, b\) 가 있다	합성수의 정의를 푼 것이다. S14주차 문제 13이 같은 도구를 쓴다
유클리드 보조정리	\(p\) 가 소수이고 \(p \mid ab\) 이면 \(p \mid a\) 또는 \(p \mid b\)	C7주차 §1.8에 이미 등록되어 있다. 문제 14에서 \(p = 3\) 으로 쓴다
연속한 두 정수의 곱	\(n(n+1)\) 은 짝수다	1권 1주차 문제 16. 문제 13에서 쓴다
이항계수의 값	\(\binom n2 = \frac{n(n-1)}2\)	1권 13주차. 문제 16에서 쓴다
나누어떨어짐의 추이성	\(p \mid a\) 이고 \(a \mid b\) 이면 \(p \mid b\)	1권 2주차. 문제 15에서 쓴다
부등식의 곱셈 성질	양수를 곱하면 부등호 방향이 보존된다	1권 16주차 (W1)~(W6). 문제 8\(\cdot\)17에서 쓴다

소인수분해의 유일성은 이 목록에 없다. 예제 2.2가 증명하는 것은 존재 파트뿐이고, 유일성은 C15주차에서 유클리드 호제법을 세운 뒤에 청산한다(1권 33주차 문제 16이 남겨 둔 빚이다). 이번 주 답안에서 유일성을 인용하지 않는다.

확인 11. 다음 두 인용은 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) “\(n+1\) 이 합성수이므로 \(n+1 = ab\) 이면서 \(2 \le a \le n\) 인 정수 \(a\) 가 있다” (나) “소인수분해는 순서를 빼면 유일하므로 \(a\) 의 분해와 \(b\) 의 분해를 이어 붙이면 된다”

답

(가) 허용 — 근거 ①(합성수의 정의)이다. \(1 < a < n+1\) 이고 \(a\) 가 정수이므로

\(2 \le a \le n\) 으로 정리한 것까지가 정의를 푼 결과다.

(나) 불허 — 유일성은 이 과정에서 아직 증명되지 않았고 목록에도 없다(C15주차의

몫이다). 게다가 예제 2.2가 증명하려는 것은 존재이므로, 유일성을 끌어오지 않아도

이어 붙이기는 성립한다. 필요 없는 사실을 인용하면 증명이 무엇에 기대는지가 흐려진다.