# C8주차 — 귀납법: 일반 원리와 최소 반례 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 귀납의 세 형태는 가정의 폭과 논법의 방향만 다르다 — 약한 귀납은 직전 하나를 가정하고, 강한 귀납은 지금까지 전부를 가정하며, 최소 반례법은 같은 계산을 귀류 쪽에서 적는다. 셋 다 자연수의 최소원리 하나에서 나온다. **이 주의 위치**: 2학기 20주 과정의 C8주차. C7주차에서 세운 귀류와 최소원리가 여기서 결합해 최소 반례법이라는 정식 기법이 된다. C7주차 문제 17에서 최소 해를 잡아 더 작은 해를 만들어 낸 그 동작이 이번 주에 무한강하라는 이름을 얻는다. 1권 31~33주차와 S14주차가 여기서 한 장으로 다시 조직된다. **원서 대응**: Chartrand 6장 (Mathematical Induction). 1일차에 이 장을 통독한 상태로 이 교안에 온다. ::: ## 이번 주 목표 1. 약한 귀납의 2단 구조를 절차로 다시 적고, "귀납 단계 = 조건문 증명"(S14주차)을 걸음 삭제 실험으로 재확인한다. 1. **강한 귀납**을 "의존의 폭"이라는 기준으로 판정해 소인수분해$\cdot$점화식$\cdot$도약 무대에서 운용한다. 1. **최소 반례법**을 5단 서식으로 세운다 — C7주차의 귀류와 1권 33주차의 최소원리가 결합한 기법이다. 1. 세 형태가 최소원리의 세 표현임을 확인하고, 명제를 보고 형태를 고르는 세 물음을 세운다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. :::{admonition} 표기 — § 와 난이도 표시 :class: quotebox §는 "절"이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다. 다른 주차를 가리킬 때는 "S14주차 §1.4"처럼 주차를 앞에 적는다. 연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서 3으로 갈수록 지지대가 줄어든다. ::: ## 준비 운동 (C7주차 복습) 지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다. 1. 반례 답안의 4단 서식(부정 전개 $\to$ 증인 제시 $\to$ 자격 검증 $\to$ 사건 검증)을 쓰시오 (C7주차). 1. 귀류 답안의 4단 서식과 모순의 3대 산지를 쓰시오 (C7주차). 1. 최소원리(정렬성)를 진술하시오 (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주차의 약한 귀납 — 만으로 두 명제를 실제로 밀어붙여 본다. :::{admonition} 시도 1 — 준비 운동 4번을 약한 귀납으로 :class: quotebox 명제: 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)$ 다. :::{admonition} 시도 2 — C7주차 문제 17을 귀납으로 :class: quotebox 명제: $x^2 = 2y^2$ 인 양의 정수 $x, y$ 는 존재하지 않는다. "귀납을 걸려면 사다리의 칸을 세는 변수 $n$ 이 필요하다. 그런데 이 명제에는 그런 $n$ 이 없다. 무엇에 대해 기저를 잡고 무엇을 한 칸 올릴지가 정해지지 않으므로 첫 줄이 나오지 않는다." ::: 두 시도가 막힌 이유는 서로 다르다. :::{container} quotebox **확인 1.** 시도 1과 시도 2가 막힌 이유는 각각 무엇인가. 한쪽은 "가정이 좁아서"이고 다른 한쪽은 그것이 아니다. 어느 쪽이 어느 쪽인가. ::: :::{admonition} 답 :class: quotebox dropdown 시도 1은 **가정의 폭** 문제다. 명제는 참이고 쪼개기도 옳은데, 약한 귀납이 주는 출발점이 $P(n)$ 하나뿐이라 $a$ 와 $b$ 를 덮지 못한다. 출발점을 $P(2), \ldots, P(n)$ 전부로 넓히면 그 자리에서 풀린다 — §1.3의 강한 귀납이다. 시도 2는 가정의 폭 문제가 아니다. **귀납을 걸 변수**가 없다. 명제가 "그런 것은 없다"는 부재 주장이라 한 칸씩 올릴 대상 자체가 무대에 없다. 이런 명제는 먼저 귀류로 대상을 하나 받아 낸 뒤(C7주차) 그중 가장 작은 것을 잡아야 손이 걸린다 — §1.4의 최소 반례법이다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 귀납이 막히면 두 가지를 검사한다. ① 귀납 단계에서 **쓴 것**이 **가정한 것**보다 넓은가 $\to$ 가정을 넓힌다(강한 귀납). ② 애초에 올릴 사다리가 없는가 $\to$ 반례를 가정하고 그중 최소인 것을 잡는다(최소 반례법). ::: ### 2 약한 귀납의 원리 — 절차로 다시 적기 1권 31주차에서 서식으로 익히고 S14주차에서 조건문 증명으로 분해한 그 원리를, 이번에는 Chartrand가 쓰는 꼴 — 시작점 $n_0$ 을 명시한 꼴 — 로 적는다. ### 정의 8.1 — 귀납의 원리 (principle of mathematical induction) [백지 암기 대상] :::{container} quotebox 정수 $n_0$ 이상의 모든 정수 $n$ 에 대해 $P(n)$ 이 참임을 보이려면, 다음 두 가지를 보이면 충분하다. ① **기저 단계**: $P(n_0)$ 이 참이다. ② **귀납 단계**: $n_0$ 이상의 모든 정수 $n$ 에 대해, $P(n)$ 이 참이면 $P(n+1)$ 도 참이다. ::: :::{admonition} 표기 — $P(n)$ 과 $n_0$ :class: quotebox $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) | | ⑤ 결론 선언 | 두 단계가 모두 갖춰졌음을 밝히고 명제를 선언한다 | 무엇이 증명되었는지가 답안에 없다 | **걸음 삭제 실험 — ①을 빼면.** 기저 확인 의무를 지우면 다음 답안이 합법이 된다. :::{admonition} 삭제 실험 — 기저 없는 귀납 :class: quotebox 명제: 모든 자연수 $n$ 에 대해 $n = n + 1$ 이다. "귀납 단계만 보이겠다. $P(n)$ 을 가정하자 — 곧 $n = n+1$ 이다. 양변에 $1$ 을 더하면 $n + 1 = n + 2$ 이고, 이것이 곧 $P(n+1)$ 이다. 따라서 귀납 단계가 성립하므로 모든 자연수에서 $n = n+1$ 이다." ::: :::{container} quotebox **확인 2.** 위 답안에서 참인 문장과 거짓인 문장을 갈라 보자. 귀납 단계 자체는 참인가 거짓인가. 그리고 결론이 거짓인 이유를 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 귀납 단계는 **참**이다. "$n = n+1$ 이면 $n+1 = n+2$ 이다"는 전건이 거짓인 조건문이고, 조건문은 전건이 거짓일 때 참이다(C5주차의 공허한 증명). 곧 이 답안의 계산에는 틀린 줄이 하나도 없다. 거짓인 것은 결론이다. 전달 법칙만 있고 첫 칸이 없으면 사다리 전체가 공중에 뜬다 — $P(1)$ 이 거짓이므로 $P(2)$ 로 갈 출발점이 애초에 없다. 1권 31주차 문제 17이 같은 결함을 다룬다. **귀납 답안의 검사는 계산 검사이기 전에 두 걸음의 존재 검사다.** ::: :::{container} quotebox **확인 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$ 이다. 따라서 성립한다." ::: :::{admonition} 답 :class: quotebox dropdown 비어 있는 걸음은 ② 귀납 가정 선언, ③ 쪼개기, ④ 가정 소비다. "(귀납 단계)" 뒤에 곧바로 도착점 "$\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}$ | :::{container} quotebox **확인 4.** 표의 (1)(2)(3)을 채우고, 아래 세 행이 첫 행과 공통으로 어긋나는 지점을 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $P(n)$ 과 $P(n+1)$ 두 항 — 직전과 그 앞이 함께 필요하다. (2) $P(a)$ 와 $P(b)$ — 어느 항인지 미리 알 수 없고, $2$ 와 $n$ 사이 어디든 될 수 있다. (3) $P(n-2)$ 한 항 — 하나면 되지만 그것이 직전이 아니다. 공통으로 어긋나는 지점: **필요한 이전 항이 직전 하나가 아니다.** 약한 귀납이 주는 출발점은 정확히 직전 하나뿐이므로, 세 경우 모두 출발점이 부족하다. ::: 부족하면 넓히면 된다. 이 관찰에 정식 이름과 형식을 붙인다. ### 정의 8.2 — 강한 귀납법 (strong induction) [백지 암기 대상] :::{container} quotebox 정수 $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의 넷째 행 무대에서 실험한다. :::{admonition} 삭제 실험 — 기저를 $n = 8$ 하나만 둔 답안 :class: quotebox 명제: $8$ 이상의 모든 정수는 3원과 5원 동전으로 지불할 수 있다. "(기저) $8 = 3 + 5$. (귀납 단계) $8$ 부터 $n$ 까지 전부 지불 가능하다고 가정하자. $n+1$ 을 지불하려면 $(n+1) - 3 = n - 2$ 를 지불한 뒤 3원을 얹으면 된다. 가정에 의해 $n-2$ 는 지불 가능하다." ::: :::{container} quotebox **확인 5.** 위 답안이 실제로 실패하는 $n+1$ 값을 모두 찾아 보자. 그리고 기저를 몇 개 두어야 하는지, 그 개수를 정하는 것이 무엇인지 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown $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}$ | :::{container} quotebox **확인 6.** 표의 (1)(2)(3)을 채우고, 세 논증이 공통으로 수행한 동작을 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $x' = \frac x2$ 인 더 작은 해 $(x', y')$ 을 실제로 만들어 $x$ 의 최소성과 충돌시켰다. (2) 공식이 성립하지 않는 자연수, 곧 반례들 중 가장 작은 것 $m$. (3) $m$ 보다 작은 $m-1$ 은 반례가 아니라는 사실을 써서 $P(m)$ 을 유도하고, "$m$ 은 반례다"와 충돌시켰다. 공통 동작: **반례(또는 해)가 있다고 가정하고, 그중 가장 작은 것을 잡아, 그보다 작은 곳에서 얻은 참으로 모순을 만든다.** 셋 다 최소원리 없이는 "가장 작은 것"을 잡는 첫 줄부터 적을 수 없다. ::: 이 동작에 정식 이름과 서식을 붙인다. ### 정의 8.3 — 최소 반례법 (proof by smallest counterexample) [백지 암기 대상] :::{container} quotebox 정수 $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)$ 이 뜻을 잃는다 (아래 삭제 실험) | | ④ 최소성 소비와 모순 | 최소성을 실제로 쓰고 충돌한 두 문장을 지목한다 | 최소성을 쓰지 않은 귀류가 되어 아무 데도 닿지 않는다 | | ⑤ 결론 복귀 | 부정 가정을 철회하고 원 명제를 선언한다 | 모순만 적히고 무엇이 증명되었는지가 없다 | **걸음 삭제 실험 — ③을 빼면.** 기저 배제 의무를 지우면 다음 답안이 합법이 된다. :::{admonition} 삭제 실험 — 기저를 배제하지 않은 답안 :class: quotebox 명제: 모든 자연수 $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$ 은 반례가 아니다. 모순." ::: :::{container} quotebox **확인 7.** 위 답안에서 $m = 1$ 인 경우를 따로 따라가 보자. $m-1$ 은 얼마이고, 그때 $\sum_{i=1}^{m-1}(2i-1)$ 은 무엇을 뜻하는가. ::: :::{admonition} 답 :class: quotebox dropdown $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$ 이 자연수가 된다. **최소 반례법의 걸음 ③은 약한 귀납의 기저 단계가 자리를 옮겨 앉은 것이다.** ::: :::{container} quotebox **확인 8.** 최소 반례법의 다섯 걸음 중 정의 8.1의 기저 단계에 대응하는 것과 귀납 단계에 대응하는 것을 각각 고르고, 무엇이 뒤집혀 있는지 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 기저 단계에 대응하는 것은 ③ 기저 배제이고, 귀납 단계에 대응하는 것은 ④ 최소성 소비다. 계산 내용은 양쪽이 완전히 같다 — 둘 다 "$P(k-1)$ 에서 $P(k)$ 로 가는 한 칸"을 만든다. 뒤집힌 것은 그 한 칸을 **쓰는 방향**이다. 약한 귀납은 그 칸을 타고 위로 올라가고, 최소 반례법은 그 칸으로 "가장 아래 칸에서 이미 참이었다"를 만들어 최소성을 깨뜨린다. 그래서 최소 반례법을 **귀납의 귀류판**이라 부른다(S14주차 문제 14). ::: ### 5 무한강하 — 걸음 ④의 다른 실행 방식 최소 반례법의 걸음 ④에는 두 가지 실행 방식이 있다. 하나는 $P(m-1)$ 에서 $P(m)$ 을 유도하는 방식이고(정의 8.3의 기본형), 다른 하나는 최소 반례에서 **더 작은 반례를 실제로 만들어** 최소성과 직접 충돌시키는 방식이다. 뒤쪽을 **무한강하**(infinite descent)라 부른다. :::{admonition} 백지 암기 대상 :class: keybox **무한강하** 조건을 만족하는 대상이 존재한다고 가정하고, 그중 어떤 양이 최소인 것을 잡는다. 그 대상에서 같은 조건을 만족하면서 그 양이 더 작은 대상을 실제로 구성한다. 최소성과 충돌하므로 그런 대상은 존재하지 않는다. ::: C7주차 문제 17에서 $x^2 = 2y^2$ 의 최소 해를 잡아 $x' = \frac x2$ 인 해를 만들어 낸 그 동작이 바로 이것이다. **1권 33주차 문제 13에서 분모가 최소인 표현을 잡아 더 작은 분모의 표현을 만들어 냈던 그 계산이, 여기서 무한강하라는 이름을 얻는다.** :::{container} quotebox **확인 9.** 정의 8.3의 기본형과 무한강하는 무엇이 다른가. "$m-1$" 이라는 낱말을 써서 한 문장으로 구분해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 기본형은 $m-1$ 이라는 **정해진 대상**의 참을 최소성에서 받아 와 $P(m)$ 을 유도한다. 무한강하는 $m-1$ 을 쓰지 않는다 — 최소 반례에서 계산으로 **새로운 더 작은 반례**를 만들어 낸다. 한 칸 아래가 필요한지, 얼마만큼이든 아래가 필요한지가 갈림길이다. 정수 무대에서는 둘 다 최소원리 하나에 기대므로 논리적 힘이 같다. ::: ### 6 세 형태와 최소원리의 관계 | **형태** | **귀납 단계의 출발점** | **논법의 방향** | **대표 무대** | |---|---|---|---| | 약한 귀납 | $P(n)$ 하나 | 순방향 연쇄 | 합 공식$\cdot$나누어떨어짐$\cdot$부등식 | | 강한 귀납 | $P(n_0), \ldots, P(n)$ 전부 | 누적 순방향 | 소인수분해$\cdot$점화식$\cdot$보폭 있는 도약 | | 최소 반례 | 최소 반례보다 작은 곳은 전부 참 | 귀류 + 최소원리 | 부재 명제$\cdot$하강이 자연스러운 무대 | :::{container} quotebox **확인 10.** 세 형태의 논리적 힘을 비교해 보자. 어느 하나로 증명되는 명제가 다른 것으로는 증명되지 않는 경우가 있는가. ::: :::{admonition} 답 :class: quotebox dropdown 없다. 셋은 논리적으로 동치이며 전부 자연수의 최소원리에서 나온다. 1권 33주차 문제 14가 "최소원리로 약한 귀납을 유도하는" 방향을, S14주차 문제 20이 세 형태가 한 원리의 세 표현임을 다룬다. 문제 19에서 같은 명제를 두 형태로 증명해 이 동치를 손으로 확인한다. 그러므로 형태의 선택은 참$\cdot$거짓의 문제가 아니라 **답안이 짧아지는가**의 문제다. ::: :::{admonition} 백지 암기 대상 :class: keybox **형태 선택의 세 물음** ① $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이 남겨 둔 빚이다). 이번 주 답안에서 유일성을 인용하지 않는다. :::{container} quotebox **확인 11.** 다음 두 인용은 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "$n+1$ 이 합성수이므로 $n+1 = ab$ 이면서 $2 \le a \le n$ 인 정수 $a$ 가 있다" (나) "소인수분해는 순서를 빼면 유일하므로 $a$ 의 분해와 $b$ 의 분해를 이어 붙이면 된다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 허용 — 근거 ①(합성수의 정의)이다. $1 < a < n+1$ 이고 $a$ 가 정수이므로 $2 \le a \le n$ 으로 정리한 것까지가 정의를 푼 결과다. (나) 불허 — 유일성은 이 과정에서 아직 증명되지 않았고 목록에도 없다(C15주차의 몫이다). 게다가 예제 2.2가 증명하려는 것은 존재이므로, 유일성을 끌어오지 않아도 이어 붙이기는 성립한다. 필요 없는 사실을 인용하면 증명이 무엇에 기대는지가 흐려진다. :::