# 31주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 귀납 증명을 함께 만들기 완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 가우스의 합 공식 **명제.** 모든 자연수 $n$에 대해 $\displaystyle 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$. **설계 — 쓰기 전에 정하는 네 가지.** 귀납 증명은 증명이 두 개이므로 번역표도 네 칸이다. 무엇에 대한 귀납인지, 기초에서 무엇을 확인하는지, 귀납 단계의 출발점과 도착점이 각각 무엇인지를 먼저 정한다. | | **말** | **수식 번역** | |---|---|---| | 귀납 대상 | 항의 개수 $n$ | $P(n)$: $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ | | [기초] 확인할 것 | $P(1)$ | 좌변 $1$, 우변 $\frac{1 \cdot 2}{2}$ — 각각 계산해 비교 | | [귀납] 출발점 | 귀납 가정 $P(k)$ | $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ | | [귀납] 도착점 | $P(k+1)$ | $1 + 2 + \cdots + (k+1) = \underline{\quad(?)\quad}$ | :::{container} quotebox **확인 10.** 도착점 칸의 빈칸을 채워 보자. $P(n)$의 우변에서 $n$ 자리에 무엇을 어떻게 넣는가. ::: :::{admonition} 답 :class: quotebox dropdown $\frac{(k+1)(k+2)}{2}$. 우변 $\frac{n(n+1)}{2}$에서 $n$이 나타나는 **모든** 자리에 $k+1$을 통째로 넣으면 $\frac{(k+1)\big((k+1)+1\big)}{2}$이고, 정리하면 $\frac{(k+1)(k+2)}{2}$이다. $\frac{k(k+1)}{2} + 1$처럼 적는 경우가 있는데, 그것은 우변 전체에 1을 더한 것이지 $n$에 $k+1$을 넣은 것이 아니다. 도착점을 잘못 적으면 이후 계산이 도달할 곳을 잃는다. ::: **1단계 — 무엇에 대한 귀납인지 선언한다.** 이 문장이 있어야 뒤에 나오는 $k$가 무엇의 첨자인지 정해진다. :::{container} quotebox **확인 11.** 첫 문장을 완성해 보자: "$\underline{\quad}$에 대한 $\underline{\qquad}$으로 증명한다." ::: :::{admonition} 답 :class: quotebox dropdown "$n$에 대한 수학적 귀납법으로 증명한다." 이번 주에는 대상이 대개 $n$이지만 문제 13은 지수 $m$에 대한 귀납이고 문제 14는 집합의 개수 $n$에 대한 귀납이다. 대상이 여럿일 수 있으므로 이를 밝히는 것이 첫 문장의 임무다. ::: **2단계 — [기초] 최소 사례를 확인한다.** 확인은 양변을 **각각** 계산해 비교하는 것이다. 한쪽만 계산하고 "같다"고 적으면 비교가 없었던 것이다. :::{container} quotebox **확인 12.** [기초] 문장을 완성해 보자: "$n = 1$일 때 좌변 $= \underline{\quad}$, 우변 $= \underline{\qquad}$이므로 $P(1)$이 성립한다. ✓" ::: :::{admonition} 답 :class: quotebox dropdown 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$. "$n = 1$이면 명백하다"로 적으면 확인이 없었던 것이다. 기초 단계가 하는 일은 사슬의 시작점을 실제로 확보하는 것이므로, 계산을 생략하면 확보되는 것이 없다. ::: **3단계 — [귀납] 가정을 선언하고 도착점을 적어 둔다.** 이 두 문장이 작성 요령 ①에 해당한다. :::{container} quotebox **확인 13.** [귀납] 첫 두 문장을 완성해 보자: "$k \ge 1$인 자연수 $k$에 대해 $\underline{\qquad}$이 성립한다고 가정하자(귀납 가정). 보일 것은 $\underline{\qquad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown 가정: $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$. 보일 것: $1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$. 출발점과 도착점이 나란히 적혀 있으므로 이제 할 일은 왼쪽에서 오른쪽으로 가는 계산뿐이다 — 1주차 이래의 번역표가 하는 일과 같다. ::: **4단계 — 도착점 쪽 좌변에서 마지막 항을 분리한다.** 여기가 준비 운동 유형 1이 막히는 자리다. $1 + 2 + \cdots + (k+1)$을 처음부터 다시 더하려 하면 §1.1의 시도 (나)와 같은 벽에 부딪힌다. 마지막 항 $(k+1)$을 떼어 내면 남은 부분이 정확히 귀납 가정이 다루는 대상이 된다(§1.7). :::{container} quotebox **확인 14.** 다음을 완성해 보자: "$1 + 2 + \cdots + (k+1) = \big(\underline{\qquad}\big) + \underline{\quad} = \underline{\qquad} + (k+1)$ (귀납 가정)" ::: :::{admonition} 답 :class: quotebox dropdown $\big(1 + 2 + \cdots + k\big) + (k+1) = \frac{k(k+1)}{2} + (k+1)$. 첫 등호는 합의 마지막 항 분리(근거 ③), 둘째 등호가 귀납 가정의 투입이다. 표시를 다는 자리가 바로 이 둘째 등호다. ::: **5단계 — 도착점 꼴로 묶고 마감한다.** 도착점이 $\frac{(k+1)(k+2)}{2}$이므로 $(k+1)$을 공통인수로 묶는 방향이 이미 정해져 있다. :::{container} quotebox **확인 15.** 다음을 완성해 보자: "$\frac{k(k+1)}{2} + (k+1) = (k+1)\Big(\underline{\qquad}\Big) = \underline{\qquad}$" ::: :::{admonition} 답 :class: quotebox dropdown $(k+1)\Big(\frac{k}{2} + 1\Big) = (k+1) \cdot \frac{k+2}{2} = \frac{(k+1)(k+2)}{2}$. 도착점과 같은 식이 나왔으므로 $P(k+1)$이 성립한다. 마지막으로 원리를 인용하며 마감한다: "수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$" ::: **완성본.** 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $n$에 대한 수학적 귀납법으로 증명한다. | 귀납 대상의 선언. 뒤에 나올 $k$가 무엇의 첨자인지 여기서 정해진다. | | **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$이므로 $P(1)$이 성립한다. ✓ | 사슬의 시작점 확보. 양변을 **각각** 계산해 비교한다 — 이 계산이 없으면 확보되는 것이 없다. | | **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $1 + \cdots + k = \frac{k(k+1)}{2}$이 성립한다고 가정하자. 보일 것은 $1 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$이다. | 조건문의 앞부분을 가정하고 시작한다(8$\cdot$15주차 서식). 도착점을 먼저 적어야 인수분해 방향이 정해진다. | | $1 + \cdots + (k+1) = \big(1 + \cdots + k\big) + (k+1) = \frac{k(k+1)}{2} + (k+1)$ (귀납 가정) | 마지막 항 분리(근거 ③)로 귀납 가정이 다루는 대상을 드러내고 가정을 투입한다. 사용 지점에 표시를 단다. | | $= (k+1)\Big(\frac{k}{2} + 1\Big) = \frac{(k+1)(k+2)}{2}$ | 도착점이 $(k+1)$을 인수로 가지므로 공통인수로 묶는다(근거 ③). 도착점과 같은 식이 되면 끝이다. | | 따라서 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ | 전달 고리의 완성을 선언하고 원리(근거 ④)를 인용하며 마감한다. | **이 두 개의 증명이 "모든" $n$을 처리하는 이유.** 귀납 단계의 $k$에 3을 넣어 읽어 보자: "$1 + 2 + 3 = \frac{3 \cdot 4}{2} = 6$이라 가정하자. $1 + 2 + 3 + 4 = 6 + 4 = 10 = \frac{4 \cdot 5}{2}$." — 모든 줄이 그대로 성립한다. $k = 99$를 넣어도 마찬가지다. :::{container} quotebox **확인 16.** 이 증명의 $k$ 자리에 넣을 수 있는 것은 어느 쪽인가. (가) 방금 넣어 본 몇 개의 자연수만 (나) 1 이상의 아무 자연수나 ::: :::{admonition} 답 :class: quotebox dropdown (나). 증명의 어느 줄도 $k$가 특정 자연수라는 사실을 쓰지 않았기 때문이다 — 쓴 것은 "$k \ge 1$인 자연수"라는 자격뿐이다. 그래서 고리 하나의 증명이 무한 개의 고리를 준다. 확인 3에서 "실제로 증명할 것은 두 개"라고 셈한 절약이 여기서 실현된다. ::: ### 예제 2.2 — 제곱의 합 (17주차 문제 14의 약속 이행) **명제.** 모든 자연수 $n$에 대해 $\displaystyle \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$. 이번에는 설계만 함께 하고, 본문은 완성된 산문으로 본다. :::{container} quotebox **확인 17.** 번역표를 채워 보자. [기초] 확인할 것: $n = 1$에서 좌변 $= \underline{\quad}$, 우변 $= \underline{\qquad}$. [귀납] 출발점: $\sum_{i=1}^{k} i^2 = \underline{\qquad}$. [귀납] 도착점: $\sum_{i=1}^{k+1} i^2 = \underline{\qquad}$. ::: :::{admonition} 답 :class: quotebox dropdown [기초] 좌변 $= 1$, 우변 $= \frac{1 \cdot 2 \cdot 3}{6} = 1$. [귀납] 출발점 $\frac{k(k+1)(2k+1)}{6}$, 도착점은 $n$이 나타나는 모든 자리에 $k+1$을 넣은 $\frac{(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)}{6} = \frac{(k+1)(k+2)(2k+3)}{6}$. 도착점을 먼저 정리해 두면 계산 도중 만나는 이차식을 어느 꼴로 인수분해할지가 이미 정해진다 — 아래 증명에서 $(k+2)(2k+3)$을 노리는 근거가 이것이다. ::: **증명.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= \frac{1 \cdot 2 \cdot 3}{6} = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$이라 가정하자. 보일 것은 $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}$이다. 마지막 항 $(k+1)^2$을 분리해 귀납 가정을 투입한 뒤 공통인수 $(k+1)$로 묶으면 $$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \ \text{(귀납 가정)} = \frac{(k+1)\big(k(2k+1) + 6(k+1)\big)}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6} $$ 이고, 도착점이 $(k+2)(2k+3)$을 인수로 가지므로 그 꼴로 인수분해한다: $2k^2 + 7k + 6 = (k+2)(2k+3)$. 따라서 $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}$이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **요령.** 귀납 단계의 계산이 길어지는 것은 대개 도착점을 적어 두지 않아서다. 도착점을 옆에 두면 인수분해의 방향을 역산할 수 있다 — $2k^2 + 7k + 6$을 보고 $(k+2)(2k+3)$을 노린 것이 그 역산이다. 검산으로 $k = 1$을 넣으면 $2 + 7 + 6 = 15$이고 $(1+2)(2+3) = 15$로 맞는다. 17주차 문제 14가 남겨 둔 "$\frac{n(n+1)(2n+1)}{6}$이 정수인 이유"도 이 등식으로 해결된다. 그 문항은 $n(n+1)(2n+1)$이 짝수임을 보여 "6으로 나누어떨어진다"의 절반만 확보하고 나머지 절반(3의 배수성)을 이 주에 맡겨 두었는데, 위 등식은 두 절반을 따로 따질 필요를 없앤다 — 좌변 $\sum_{i=1}^{n} i^2$은 정수들의 합이므로 정수이고, 우변이 그와 같은 수이므로 우변도 정수다. ### 예제 2.3 — 멱집합의 크기 $|\mathcal{P}(A)| = 2^n$ **명제.** $|A| = n$이면 $|\mathcal{P}(A)| = 2^n$이다 ($n \ge 0$). 4주차에서 "지금은 인정하고 쓴다(31주차에서 증명)"로 미뤄 둔 사실이다. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 18.** 세 가지를 먼저 정해 보자. ① 무엇에 대한 귀납인가: $\underline{\qquad}$ ② [기초]를 $n = 1$이 아니라 $n = 0$에서 잡아도 되는 이유: $\underline{\qquad}$ ③ [귀납] 도착점: $|A| = k+1$일 때 $|\mathcal{P}(A)| = \underline{\quad}$ ::: :::{admonition} 답 :class: quotebox dropdown ① 집합의 크기 $n$. 이 명제에는 합도 지수 계산도 없고, 크기가 하나 커질 때 멱집합이 어떻게 커지는지가 전부다. ② 명제가 $n \ge 0$에서 주장되므로 사슬의 시작점도 0이다(§1.3). ③ $2^{k+1}$. $2^k + 1$이 아니라 $2^k \cdot 2$가 되어야 하므로 귀납 단계에서 만들 것은 "$2^k$짜리 무리 두 개"다 — 도착점의 모양이 분할의 개수를 미리 알려 준다. ::: **증명.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 0$일 때 $A = \emptyset$이고 $\mathcal{P}(\emptyset) = \{\emptyset\}$이므로 $|\mathcal{P}(A)| = 1 = 2^0$이다. ✓ **[귀납]** $k \ge 0$인 정수 $k$에 대해, 크기가 $k$인 모든 집합의 멱집합 크기가 $2^k$라고 가정하자. 보일 것은 크기가 $k+1$인 집합 $A$에 대해 $|\mathcal{P}(A)| = 2^{k+1}$이라는 것이다. $|A| = k+1$이므로 $A$는 비어 있지 않고, 원소 $x \in A$를 하나 고정해 $A' = A - \{x\}$라 하면 $|A'| = k$이다. $A$의 부분집합 전체를 $x$를 기준으로 두 무리로 나눈다. - $x$를 포함하지 않는 부분집합: 이는 정확히 $A'$의 부분집합이다. 귀납 가정에 의해 $2^k$개다. - $x$를 포함하는 부분집합: $S \mapsto S \cup \{x\}$가 $A'$의 부분집합 전체와 이 무리 사이의 1대1 대응이므로 역시 귀납 가정에 의해 $2^k$개다. 어떤 부분집합이든 $x$를 포함하거나 포함하지 않거나 둘 중 정확히 하나이므로 두 무리는 겹치지 않고 전체를 덮는다. 덧셈 원리(14주차)에 의해 $|\mathcal{P}(A)| = 2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 정수 $n \ge 0$에서 성립한다. $\blacksquare$ **구조 읽기.** 귀납 가정이 투입된 곳은 두 무리의 개수를 각각 $2^k$라고 적은 두 지점이다. "$x$ 포함 / 미포함"이라는 분할은 13주차 파스칼 공식에서 한 사람을 기준으로 뽑기를 나눈 것과 같은 분할이다 — 세기 논증이 귀납 단계의 계산을 맡고, 귀납법이 그 논증을 모든 $n$으로 밀어 올린다. 4주차에서 "원소마다 넣는다/뺀다 두 가지"라는 관찰로 납득했던 것이 여기서 정식 증명이 되었다. ### 관찰 — 세 증명의 같은 뼈대 예제 2.1, 2.2, 2.3은 소재가 합$\cdot$합$\cdot$집합으로 다르지만 뼈대가 같다. 각 단계에 어느 문장이 대응하는지 빈칸을 채워 보자. :::{container} quotebox **확인 19.** 예제 2.3의 산문에서 각 단계에 해당하는 문장(또는 식)을 찾아 보자. ① 귀납 대상 선언: $\underline{\qquad}$ ② [기초]: $\underline{\qquad}$ ③ [귀납] 가정과 도착점: $\underline{\qquad}$ ④ 가정 투입과 변형: $\underline{\qquad}$ ::: :::{admonition} 답 :class: quotebox dropdown ① "$n$에 대한 수학적 귀납법으로 증명한다." ② "$n = 0$일 때 $A = \emptyset$이고 $\mathcal{P}(\emptyset) = \{\emptyset\}$이므로 $|\mathcal{P}(A)| = 1 = 2^0$이다." ③ "크기가 $k$인 모든 집합의 멱집합 크기가 $2^k$라고 가정하자. 보일 것은 $|A| = k+1$일 때 $|\mathcal{P}(A)| = 2^{k+1}$이라는 것이다." ④ 두 무리의 개수를 각각 $2^k$로 적은 두 지점(가정 투입)과 "$2^k + 2^k = 2^{k+1}$"(도착점 꼴로 변형). 예제 2.1과 2.2도 정확히 이 네 걸음이고, 다섯째 걸음인 마감 문장도 같다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **귀납 증명의 5단계 틀** ① 무엇에 대한 귀납인지 선언한다 $\to$ ② **[기초]** 최소 사례에서 양변(또는 명제 전체)을 각각 확인한다 $\to$ ③ **[귀납]** $P(k)$를 가정하고 도착점 $P(k+1)$의 구체적 모양을 적어 둔다 $\to$ ④ 도착점 쪽 대상에서 $P(k)$의 대상을 분리해 귀납 가정을 투입하고(표시를 단다) 도착점 꼴로 변형한다 $\to$ ⑤ 원리를 인용하며 마감한다. ::: 이 틀은 32~35주차의 부등식$\cdot$나누어떨어짐$\cdot$점화식 귀납에서 재료만 바꿔 그대로 쓴다. 1주차의 3단계 틀이 직접 증명의 기본형이듯, 이것이 귀납 증명의 기본형이다. ### 빚 회수 — 곱셈 원리와 덧셈 원리의 일반형 12~14주차는 두 세기 원리를 두 단계$\cdot$두 집합 꼴에서만 증명하고, 일반형은 "지금은 인정하고 쓴다(31주차에서 증명)"로 미뤄 두었다(12주차 §1.4, 13주차 §1.3, 14주차 §1.2). 미뤄 둔 것은 원리의 내용이 아니라 **"반복해서 얻는다"는 말**이었고, 그 말을 정식 증명으로 바꾸는 것이 방금 세운 5단계 틀이다. 아래 두 증명은 예제 2.1~2.3과 재료만 다르고 걸음은 같다. **사실 1 — 곱셈 원리의 일반형.** 길이 $n$의 목록을 만들 때 $i$번째 항목의 선택지가 (앞 선택과 무관하게) $a_i$가지이면, 가능한 목록의 총수는 $a_1 a_2 \cdots a_n$이다. **증명.** 목록의 길이 $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 목록은 1번째 항목 하나로 이루어지므로 총수는 $a_1$가지이고, 곱 $a_1$과 같다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해, 길이 $k$의 목록의 총수가 $a_1 a_2 \cdots a_k$라고 가정하자. 보일 것은 길이 $k+1$의 목록의 총수가 $a_1 a_2 \cdots a_k a_{k+1}$이라는 것이다. 길이 $k+1$의 목록은 "앞의 $k$개"를 정하고 "$k+1$번째 항목"을 정하는 두 단계로 만들어진다. 첫 단계의 선택지는 길이 $k$의 목록 전체이므로 귀납 가정에 의해 $a_1 a_2 \cdots a_k$가지이고 (귀납 가정), 둘째 단계의 선택지는 $a_{k+1}$가지이며 그 개수는 앞 단계의 결과와 무관하다. 두 단계 곱셈 원리(12주차 §1.4~1.5의 격자 논증, 근거 ④)에 의해 총수는 $\big(a_1 a_2 \cdots a_k\big) \times a_{k+1} = a_1 a_2 \cdots a_k a_{k+1}$이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **사실 2 — 덧셈 원리의 일반형.** 유한집합 $A_1, \dots, A_n$ ($n \ge 2$)이 쌍마다 서로소이면 $|A_1 \cup \cdots \cup A_n| = |A_1| + \cdots + |A_n|$이다. **증명.** 집합의 개수 $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 2$일 때 보일 것은 $|A_1 \cup A_2| = |A_1| + |A_2|$이고, 이는 14주차 §1.2에서 이어 붙이기 논증으로 증명한 두 집합 덧셈 원리다(근거 ④). 성립한다. ✓ **[귀납]** $k \ge 2$인 자연수 $k$에 대해, 쌍마다 서로소인 유한집합 $k$개에서 $|A_1 \cup \cdots \cup A_k| = |A_1| + \cdots + |A_k|$가 성립한다고 가정하자. 보일 것은 쌍마다 서로소인 유한집합 $k+1$개에서 $|A_1 \cup \cdots \cup A_{k+1}| = |A_1| + \cdots + |A_{k+1}|$이라는 것이다. $n$개 합집합의 왼쪽 묶기 표기 약속(27주차 문제 17 앞 상자, 근거 ①)에 의해 $A_1 \cup \cdots \cup A_{k+1} = \big(A_1 \cup \cdots \cup A_k\big) \cup A_{k+1}$이다. 이 두 집합은 서로소다 — 공통 원소 $x$가 있다면 $x \in A_1 \cup \cdots \cup A_k$에서 어떤 $i \le k$에 대해 $x \in A_i$이고 동시에 $x \in A_{k+1}$이어서 $A_i \cap A_{k+1} = \emptyset$에 어긋난다. 또 $A_1, \dots, A_k$는 여전히 쌍마다 서로소이므로 귀납 가정을 쓸 수 있다. 두 집합 덧셈 원리를 먼저, 귀납 가정을 그다음에 적용하면 $$ |A_1 \cup \cdots \cup A_{k+1}| = |A_1 \cup \cdots \cup A_k| + |A_{k+1}| = \big(|A_1| + \cdots + |A_k|\big) + |A_{k+1}| \ \text{(귀납 가정)} $$ 이며 이것이 도착점이다. 수학적 귀납법에 의해 $n \ge 2$인 모든 자연수 $n$에서 성립한다. $\blacksquare$ **구조 읽기.** 두 증명의 귀납 단계는 첫 동작이 같다 — **마지막 하나를 떼어 내기**다. 합에서 마지막 항을 분리하던 것(§1.7), 집합 $n$개에서 $A_{k+1}$을 떼어 내는 것(문제 14)과 같은 동작이며, 떼어 낸 자리에 12$\cdot$14주차의 두 단계$\cdot$두 집합 버전이 정확히 들어맞는다. 12~14주차의 세기 답안에서 "곱셈 원리에 의해", "덧셈 원리에 의해"라고 적을 때 붙어 있던 유보 문구는 이 두 증명으로 사라진다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** 모든 자연수 $n$에 대해 $1 + 3 + 5 + \cdots + (2n-1) = n^2$ (홀수 $n$개의 합). **증명.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= 1^2 = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $1 + 3 + \cdots + (2k-1) = \underline{\quad(1)\quad}$이 성립한다고 가정하자. 보일 것은 $1 + 3 + \cdots + \big(2(k+1)-1\big) = (k+1)^2$이다. 마지막 항을 분리해 귀납 가정을 투입하면 $$ 1 + 3 + \cdots + (2k-1) + \big(\underline{\quad(2)\quad}\big) = k^2 + 2k + 1 = \underline{\quad(3)\quad} $$ 이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ (첫 등호가 귀납 가정을 투입한 지점이다 — 자기 답안에는 그 자리에 "(귀납 가정)" 표시를 단다.) ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장도 빈칸이다. **명제.** 모든 자연수 $n$에 대해 $\displaystyle \sum_{i=1}^{n} 2i = n(n+1)$. **증명.** $\underline{\quad(1)\quad}$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= \underline{\quad(2)\quad}$, 우변 $= 1 \cdot 2 = 2$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $\sum_{i=1}^{k} 2i = \underline{\quad(3)\quad}$라 가정하자. 보일 것은 $\sum_{i=1}^{k+1} 2i = \underline{\quad(4)\quad}$이다. 그러면 $$ \sum_{i=1}^{k+1} 2i = \Big(\sum_{i=1}^{k} 2i\Big) + \underline{\quad(5)\quad} = k(k+1) + 2(k+1) $$ 이고, 첫 등호의 근거는 $\underline{\quad(6)\quad}$, 둘째 등호의 근거는 $\underline{\quad(7)\quad}$이다. 공통인수 $(k+1)$로 묶으면 $(k+1)(k+2)$이므로 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 5단계 틀의 각 칸을 통째로 채운다. **명제.** 모든 자연수 $n$에 대해 $\displaystyle \sum_{i=1}^{n} i(i+1) = \frac{n(n+1)(n+2)}{3}$. **증명의 뼈대.** - ① 귀납 대상 선언: $\underline{\quad(1)\quad}$ - ② [기초]: $\underline{\quad(2)\quad}$ - ③ [귀납] 가정과 도착점: $\underline{\quad(3)\quad}$ - ④ 가정 투입과 변형: $\underline{\quad(4)\quad}$ - ⑤ 마감: $\underline{\quad(5)\quad}$ (④에서 묶을 공통인수가 무엇인지는 도착점의 모양이 알려 준다. 이 훈련이 문제 9$\cdot$10의 예행연습이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 모든 귀납 답안에 [기초]/[귀납] 표기와 "(귀납 가정)" 사용 지점 표시를 지킨다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "귀납법에 의해 성립한다"는 0점이다. 세 가지가 채점의 전부다: ① [기초]에서 양변(또는 명제 전체)을 **각각** 계산해 확인했는가 ② [귀납]에서 도착점 $P(k+1)$의 구체적 모양을 적어 두었는가 ③ 귀납 가정을 실제로 사용한 지점에 표시가 있는가. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 귀납법의 원리(두 단계)와 서식을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 통째로 떠올리려 하지 말고 §1.4의 해부 표에서 조각을 하나씩 꺼낸다 — 대상 선언, 시작점, 고리의 전칭성, 한 칸 전달, 결론. 다섯 조각을 이으면 원리가 되고, 그 위에 [기초]/[귀납] 표기를 얹으면 서식이 된다. ::: **2.** 도미노 모형에서 기초 단계$\cdot$귀납 단계가 각각 무엇에 대응하는지, 하나라도 빠지면 무슨 일이 생기는지 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 부재 시나리오 두 개를 각각 본문의 어느 자리와 연결한다 — 기초가 없는 경우는 §1.4의 삭제 실험 1(그리고 문제 17), 전달이 없는 경우는 §1.1의 시도 (가)다. ::: **3.** 계산 워밍업: (a) $\sum_{i=1}^{10} i$ (b) $\sum_{i=1}^{5} (2i-1)$ (c) $\sum_{i=1}^{4} 2^i$ :::{admonition} 힌트 :class: quotebox dropdown (a)는 예제 2.1, (b)는 훈련 1의 공식을 그대로 쓴다. (c)는 첫 첨자가 $i = 1$임에 주의한다 — 문제 11의 공식은 $i = 0$부터의 합이라 그대로 쓰면 항이 하나 는다. ::: **4.** 빈칸 훈련(홀수 합 $= n^2$)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 막히는 자리는 대개 마지막 항이다. $n$번째 항이 $2n - 1$이므로 $(k+1)$번째 항은 $n$ 자리에 $k+1$을 통째로 넣은 $2(k+1) - 1$이다(§1.7의 대입 규칙). ::: **5.** 예제 2.1(가우스 합)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 5단계 틀의 칸을 먼저 그려 놓고 채운다. 도착점 $\frac{(k+1)(k+2)}{2}$를 계산 시작 전에 적어 두면 묶을 공통인수가 $(k+1)$이라는 것이 저절로 정해진다. ::: **6.** "귀납 가정은 반칙이 아니다"를 8주차 조건문 증명 서식과 연결해 세 문장 이내로 설명하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 문장의 뼈대: ① 귀납 단계가 증명하는 대상이 무엇인가 ② 그 대상의 표준 증명 서식은 무엇인가 ③ $P(k)$ 자체의 참은 어디에서 오는가. (§1.6과 확인 7) ::: ### 표준 ●●○ **7.** 예제 2.2($\sum i^2$)를 백지에 재현하시오. **8.** 모든 자연수 $n$에 대해 $\displaystyle \sum_{i=1}^{n} i^3 = \left[\frac{n(n+1)}{2}\right]^2$임을 증명하시오. (세제곱의 합 = 합의 제곱) :::{admonition} 힌트 :class: quotebox dropdown 도착점은 $\left[\frac{(k+1)(k+2)}{2}\right]^2$이다. 마지막 항 $(k+1)^3$을 더한 뒤 $(k+1)^2$을 공통인수로 묶으면 남는 괄호가 $k^2 + 4k + 4$가 되는지 확인한다. ::: **9.** 모든 자연수 $n$에 대해 $\displaystyle \sum_{i=1}^{n} (3i - 2) = \frac{n(3n-1)}{2}$임을 증명하시오 (등차수열 $1, 4, 7, \dots$의 합). **10.** 모든 자연수 $n$에 대해 $\displaystyle \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n+1}$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 마지막 항은 $\frac{1}{(k+1)(k+2)}$이다. $\frac{k}{k+1}$과 통분하면 분모가 $(k+1)(k+2)$이고, 분자 $k(k+2) + 1$을 전개해 보면 완전제곱으로 뭉친다. ::: **11.** 모든 정수 $n \ge 0$에 대해 $\displaystyle \sum_{i=0}^{n} 2^i = 2^{n+1} - 1$임을 증명하시오 (기초는 $n = 0$). :::{admonition} 힌트 :class: quotebox dropdown 기초가 $n = 0$이므로 좌변은 항 하나 $2^0 = 1$이다. 귀납 단계에서는 $(2^{k+1} - 1) + 2^{k+1}$을 정리하는데, 같은 것 두 개의 합이 $2 \cdot 2^{k+1}$임을 쓰면 지수가 하나 오른다. ::: **12.** 예제 2.3($|\mathcal{P}(A)| = 2^n$)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 부품이 다 있는지 점검한다: ① $x$ 포함/미포함 두 무리로의 분할 ② 포함 무리와 $A'$의 부분집합 사이의 1대1 대응 ③ 덧셈 원리로 두 수를 더하기. 하나라도 빠지면 $2^k + 2^k$라는 등식의 근거가 사라진다. ::: :::{admonition} 이번 주에 처음 쓰는 부품 — 합동식의 곱 보존 (문제 13) :class: quotebox 20주차에서 증명한 세 성질을 문제 13$\cdot$15에서 그대로 인용한다. (C1) 반사: $a \equiv a \pmod n$. (C4) $a \equiv b$이고 $c \equiv d$이면 $a + c \equiv b + d \pmod n$. (C5) $a \equiv b$이고 $c \equiv d$이면 $ac \equiv bd \pmod n$. 20주차 §1.6에서는 (C5)를 두 번, 세 번 반복 적용해 $a^2 \equiv b^2$, $a^3 \equiv b^3$을 얻고, 임의의 지수에 대한 일반형은 "지금은 인정하고 쓴다 (31주차에서 증명)"로 미뤄 두었다. 문제 13이 그 유보를 푸는 자리이며, 귀납 대상이 $n$이 아니라 **지수 $m$**이라는 점에 주의한다. ::: **13.** (20주차의 약속) $a \equiv b \pmod n$이면 모든 자연수 $m$에 대해 $a^m \equiv b^m \pmod n$임을 $m$에 대한 귀납법으로 증명하시오. (부품: (C5)) :::{admonition} 힌트 :class: quotebox dropdown 기초 $m = 1$에서 증명할 것은 $a^1 \equiv b^1$인데 이는 가정 그 자체다 — 새로 계산할 것이 없는 기초 단계도 있다. 귀납 단계에서는 (C5)에 넣을 합동식 두 개를 고른다: 하나는 귀납 가정, 다른 하나는 명제의 가정이다. ::: :::{admonition} 이번 주에 처음 쓰는 표기 — $n$개 집합의 합집합 (문제 14) :class: quotebox $A_1 \cup A_2 \cup \cdots \cup A_n$은 앞에서부터 두 개씩 묶어 가는 것으로 읽는다: $\big((A_1 \cup A_2) \cup A_3\big) \cup \cdots$. 이것은 $n$개 합집합의 왼쪽 묶기 **표기 약속**이며(27주차 문제 17 앞 상자, 근거 ①), 증명해야 할 사실이 아니라 표기의 정의다. 따라서 $A_1 \cup \cdots \cup A_{k+1}$은 그 자체로 $\big(A_1 \cup \cdots \cup A_k\big) \cup A_{k+1}$이고, 두 집합짜리 정리를 바로 적용할 수 있다. 이 "마지막 하나를 떼어 내기"가 합에서 마지막 항을 분리하던 것(§1.7)과 같은 동작이다. ::: **14.** (27주차 문제 17의 일반화) $n \ge 2$개의 집합에 대해 $\big(A_1 \cup A_2 \cup \cdots \cup A_n\big)^c = A_1^c \cap A_2^c \cap \cdots \cap A_n^c$임을 $n$에 대한 귀납법으로 증명하시오 (기초는 $n = 2$ — 27주차 예제 2.1). :::{admonition} 힌트 :class: quotebox dropdown 기초가 $n = 2$이고 그 경우는 이미 증명되어 있으므로 인용 한 줄로 끝난다. 귀납 단계에서 쓰는 정리는 두 개다 — 2집합 드모르간(근거 ④)과 귀납 가정. 어느 등호에서 어느 것을 썼는지 각각 표시한다. ::: ### 도전 ●●● **15.** (20주차 문제 15의 완성) (a) 모든 자연수 $k$에 대해 $10^k \equiv 1 \pmod 9$임을 귀납법으로 증명하시오. (b) 이를 이용해 임의 자릿수 자연수 $N = d_m 10^m + \cdots + d_1 10 + d_0$에 대해 $N \equiv d_m + \cdots + d_1 + d_0 \pmod 9$임을 논증하시오. :::{admonition} 힌트 :class: quotebox dropdown (a)의 기초는 $10^1 - 1 = 9$의 확인이고, 귀납 단계는 (C5)에 $10^k \equiv 1$과 $10 \equiv 1$을 넣는다. (b)는 각 자리를 따로 처리한 뒤 전부 더한다 — "따로 처리"에 쓰는 것이 (C5), "전부 더하기"에 쓰는 것이 (C4)다. ::: :::{admonition} 이번 주에 처음 쓰는 기술 — 부등식을 귀납으로 (문제 16) :class: quotebox 지금까지의 귀납 단계는 좌변을 변형해 도착점 **등식**을 만드는 일이었다. 도착점이 부등식이면 절차가 한 걸음 늘어난다. 귀납 가정을 투입하면 목표보다 약한 부등식이 나오는 것이 보통이고, 남은 간극을 부등식의 성질 (W2)(W3) (16주차)로 메워야 한다. 곧 $A > B$(귀납 가정에서)와 $B \ge C$(따로 확보)를 이어 $A > C$를 얻는 **연결 부등식** 두 개가 한 줄에 나란히 서는 모양이 된다. 32주차의 주된 기술이며, 이 문제가 첫 사례다. ::: **16.** 모든 자연수 $n$에 대해 $n < 2^n$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 도착점은 $k + 1 < 2^{k+1}$이다. $2^{k+1} = 2 \cdot 2^k$로 쓴 뒤 귀납 가정 $k < 2^k$의 양변에 2를 곱한다((W3)). 그러면 $2^{k+1} > 2k$까지 온다 — 남은 것은 $2k$와 $k+1$의 비교이고, $2k = k + k$로 쪼개면 $k \ge 1$이 답을 준다. ::: **17.** (진단 — 기초 없는 귀납) 다음 '증명'의 결함을 지적하시오. :::{container} quotebox "명제: 모든 자연수 $n$에 대해 $n = n + 1$이다. 증명: $k = k + 1$이라 가정하자. 양변에 1을 더하면 $k + 1 = k + 2$, 즉 $P(k+1)$이 성립한다. 따라서 귀납법에 의해 모든 $n$에서 $n = n+1$이다. $\blacksquare$" (귀납 단계 자체는 흠잡을 데 없다 — 그런데 왜 결론이 거짓인가?) ::: **18.** $r \neq 1$인 실수 $r$에 대해, 모든 정수 $n \ge 0$에서 $\displaystyle 1 + r + r^2 + \cdots + r^n = \frac{r^{n+1} - 1}{r - 1}$임을 증명하시오 (등비수열 합 — 고2 공식의 청산). :::{admonition} 힌트 :class: quotebox dropdown 가정 $r \neq 1$이 어디서 쓰이는지 먼저 정한다 — 우변의 분모가 0이 되지 않도록 보장하는 자리다. 귀납 단계는 $\frac{r^{k+1} - 1}{r - 1} + r^{k+1}$의 통분이고, 분자에서 $r^{k+1}$끼리 소거되는 것을 확인한다. ::: **19.** 예제 2.1의 공식에 대해: (a) 가우스의 짝짓기 풀이($1 + 100, 2 + 99, \dots$)를 $n = 100$에 대해 재현하시오. (b) 짝짓기 논증과 귀납 증명의 장단점을 각각 한 가지씩 비교하시오. (c) 우변 $\frac{n(n+1)}{2}$이 항상 자연수인 이유를 1주차 정리로 한 줄 설명하시오. **20.** (서술) (a) "무한히 많은 명제를 두 증명으로" — 귀납법이 $\forall n\, P(n)$을 처리하는 원리를 도미노 없이 논리의 언어로 두 문장 이내로 쓰시오. (b) 귀납 답안 자가 점검 질문 두 개(기초$\cdot$가정 사용)를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown (a)에서 쓸 낱말은 두 개다 — 조건문의 사슬과 긍정 논법(modus ponens, 11주차). "임의의 $n$이 1에서 유한 걸음 거리에 있다"는 사실이 사슬이 전부를 덮는 이유다. (b)는 채점 기준 상자의 세 항목 중 두 개를 질문 꼴로 바꾼다. ::: ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 5단계 틀(§2 관찰)과 근거 목록(§1.8)만 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 원리 문장과 본문은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 수학적 귀납법의 원리를 두 단계로 정확히 썼다 ("모든 $k \ge 1$에 대해"까지 조각 그대로). - [ ] 서식([기초]/[귀납]/"(귀납 가정)" 표시)을 백지에 재현했다. - [ ] 예제 2.1과 2.2를 처음부터 끝까지 재현했다 — 도착점을 먼저 적는 순서까지. - [ ] 예제 2.3에서 두 무리 분할$\cdot$1대1 대응$\cdot$덧셈 원리 세 부품을 각각 말했다. - [ ] "귀납 가정이 반칙이 아닌 이유"를 조건문의 언어로 한 문장에 담았다. - [ ] 기초 단계를 지우면 무엇이 무너지는지 문제 17의 사례로 설명했다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 첫 문장부터 나오지 않는다 | 예제 2.1의 1단계 — 첫 문장은 "무엇에 대한 귀납인지"의 선언이다 | | 기초 단계에서 무엇을 쓸지 모르겠다 | §1.4 해부 표 둘째 행 — 양변을 각각 계산해 비교하는 것이 전부다 | | 도착점 $P(k+1)$의 모양을 못 적겠다 | §1.7의 대입 규칙 — $n$이 나타나는 모든 자리에 $k+1$을 통째로 넣는다 | | 귀납 가정을 어디에 넣을지 모르겠다 | 예제 2.1의 4단계 — 마지막 항을 분리하면 가정이 다루는 대상이 드러난다 | | 묶은 다음이 나오지 않는다 | 예제 2.2의 요령 — 도착점에서 인수분해 방향을 역산한다 | | "가정할 것을 가정한다"가 계속 걸린다 | §1.6과 확인 7 — 증명 대상이 조건문임을 문장으로 다시 쓴다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $k^2$ (2) $2(k+1) - 1 = 2k + 1$ (3) $(k+1)^2$ ※ (2)가 급소다. $n$번째 홀수가 $2n - 1$이므로 $(k+1)$번째 홀수는 $n$ 자리에 $k+1$을 통째로 넣은 $2k + 1$이다. $2k - 1 + 1 = 2k$로 적는 경우가 있는데, 그것은 항의 값에 1을 더한 것이지 첨자에 1을 더한 것이 아니다. (3)은 $k^2 + 2k + 1$의 완전제곱 조립이고, 이 식이 도착점과 일치하는지 확인하는 것으로 귀납 단계가 닫힌다. 검산: $n = 3$에서 $1 + 3 + 5 = 9 = 3^2$ ✓. ### 빈칸 사다리 — 훈련 2 (1) $n$ (2) $2$ (3) $k(k+1)$ (4) $(k+1)(k+2)$ (5) $2(k+1)$ (6) 합의 마지막 항 분리 (§1.7, 근거 ③) (7) 귀납 가정 (근거 ①) ※ (4)를 $k(k+1) + 2$로 적는 경우가 있는데, 도착점은 우변의 $n$ 자리에 $k+1$을 넣은 $(k+1)(k+2)$다. (5)의 마지막 항은 $a_i = 2i$의 $i$ 자리에 $k+1$을 넣은 $2(k+1)$이다. (6)과 (7)을 구분해 적는 것이 이 훈련의 목적이다 — 분리는 등식의 성질이고 가정 투입은 귀납법이 허용한 한 걸음이며, 표시가 붙어야 할 곳은 (7)이다. 검산: $n = 3$에서 $2 + 4 + 6 = 12 = 3 \cdot 4$ ✓. ### 빈칸 사다리 — 훈련 3 (1) $n$에 대한 수학적 귀납법으로 증명한다. (2) $n = 1$일 때 좌변 $= 1 \cdot 2 = 2$, 우변 $= \frac{1 \cdot 2 \cdot 3}{3} = 2$이므로 성립한다. ✓ (3) $k \ge 1$인 자연수 $k$에 대해 $\sum_{i=1}^{k} i(i+1) = \frac{k(k+1)(k+2)}{3}$이라 가정하자. 보일 것은 $\sum_{i=1}^{k+1} i(i+1) = \frac{(k+1)(k+2)(k+3)}{3}$이다. (4) 마지막 항 $(k+1)(k+2)$를 분리해 귀납 가정을 투입하고 공통인수 $(k+1)(k+2)$로 묶으면 $\frac{k(k+1)(k+2)}{3} + (k+1)(k+2) = (k+1)(k+2)\big(\frac{k}{3} + 1\big) = \frac{(k+1)(k+2)(k+3)}{3}$이다. (5) 따라서 $P(k+1)$이 성립한다. "수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$" ※ 묶을 공통인수가 $(k+1)(k+2)$라는 것은 도착점이 알려 준다. 도착점을 적어 두지 않으면 좌변을 전개해 삼차식과 씨름하게 된다. 검산: $n = 2$에서 좌변 $2 + 6 = 8$, 우변 $\frac{2 \cdot 3 \cdot 4}{3} = 8$ ✓. ### 문제 1 **접근.** 통째 암기가 아니라 §1.4 해부 표의 조각에서 재구성한다. 다섯 조각은 대상 선언, 시작점, 고리의 전칭성, 한 칸 전달, 결론이며 이 순서로 이으면 원리 문장이 된다. 서식은 그 위에 답안 표기를 얹은 것이다. **풀이.** **원리.** 자연수에 대한 명제 $P(n)$에 대해 다음 두 가지가 증명되면 모든 자연수 $n$에 대해 $P(n)$이 참이다. (기초 단계) $P(1)$이 참이다. (귀납 단계) 모든 $k \ge 1$에 대해, $P(k)$가 참이면 $P(k+1)$도 참이다. **서식.** "**증명.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 (양변을 각각 계산해 확인). ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $P(k)$가 성립한다고 가정하자(귀납 가정). 보일 것은 $P(k+1)$이다. … 따라서 $P(k+1)$이 성립한다. 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $P(n)$이다. $\blacksquare$" **자가 채점.** ① "모든 $k \ge 1$에 대해"가 들어갔는가(빠지면 삭제 실험 2의 상태다) ② 귀납 단계가 조건문 $P(k) \Rightarrow P(k+1)$의 꼴로 적혔는가 ③ 기초 단계에 "확인한다"는 동작이 명시됐는가 ④ 마감이 원리의 인용인가. ### 문제 2 **접근.** 두 부품을 각각 원리의 어느 항목에 대응시키고, 부재 시나리오 두 개를 본문의 자리와 연결한다. 기초가 없는 경우는 §1.4 삭제 실험 1과 문제 17, 전달이 없는 경우는 §1.1 시도 (가)다. **풀이.** 기초 단계는 첫 번째 도미노를 실제로 넘어뜨리는 것에 대응한다 — $P(1)$이 참임을 계산으로 확인하는 일이다. 귀납 단계는 "어느 것이든 넘어지면 바로 다음 것이 넘어진다"는 간격 조정에 대응한다 — 조건문 $P(k) \Rightarrow P(k+1)$을 모든 $k$에 대해 확보하는 일이다. 기초가 빠지면 간격이 완벽해도 아무것도 넘어지지 않는다. 문제 17이 실제 사례이며, 그 '증명'의 귀납 단계는 참인 조건문이지만 결론은 거짓이다 — 거짓에서 거짓으로 가는 전달도 논리적으로는 유효하기 때문이다(8주차 진리표). 전달이 빠지면 첫 도미노만 넘어지고 멈춘다. 확보되는 것은 $P(1)$ 하나뿐이며, 이는 §1.1의 시도 (가)에서 값을 몇 개 넣어 본 상태와 같다. **복기.** 두 단계는 서로 다른 일을 하므로 서로를 대신하지 못한다. 답안을 검사할 때 "두 단계가 각각 있는가"를 먼저 보는 습관이 문제 17 같은 결함을 계산 검사보다 먼저 잡아낸다. ### 문제 3 **접근.** (a)는 예제 2.1, (b)는 훈련 1의 공식을 그대로 쓴다. (c)는 공식보다 직접 계산이 짧고, 문제 11의 공식과 첨자 범위가 다르다는 점이 확인 대상이다. 세 항 모두 공식으로 구한 뒤 직접 계산으로 검산한다. **풀이.** (a) 예제 2.1에서 $n = 10$: $\frac{10 \cdot 11}{2} = 55$. 검산으로 짝을 지으면 $(1+10) + (2+9) + (3+8) + (4+7) + (5+6) = 11 \times 5 = 55$ ✓. (b) 훈련 1의 공식 $1 + 3 + \cdots + (2n-1) = n^2$에서 $n = 5$이므로 $5^2 = 25$. 검산: $1 + 3 + 5 + 7 + 9 = 25$ ✓. (c) 첫 첨자가 $i = 1$이므로 항은 $2^1, 2^2, 2^3, 2^4$ 네 개이고 $2 + 4 + 8 + 16 = 30$이다. 문제 11의 공식은 $i = 0$부터의 합이므로 $\sum_{i=0}^{4} 2^i = 2^5 - 1 = 31$이고, 여기서 $2^0 = 1$을 빼면 $30$으로 일치한다 ✓. **복기.** 공식을 쓸 때 먼저 확인할 것은 값이 아니라 **첨자 범위**다. (c)에서 $31$로 적는 경우가 많은데 이는 $i = 0$ 항을 빼지 않은 것이다. 합 공식은 항상 "어디서 시작해 어디서 끝나는가"와 짝지어 외운다. ### 문제 4 **접근.** 훈련 1을 백지에서 다시 쓴다. 막히는 자리는 마지막 항이므로 $n$번째 항이 $2n - 1$이라는 것에서 $(k+1)$번째 항을 대입 규칙으로 만든다. 도착점 $(k+1)^2$을 먼저 적어 두면 $k^2 + 2k + 1$을 어느 꼴로 조립할지 정해진다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= 1^2 = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $1 + 3 + \cdots + (2k-1) = k^2$이 성립한다고 가정하자. 보일 것은 $1 + 3 + \cdots + (2k+1) = (k+1)^2$이다. $(k+1)$번째 항은 $2(k+1) - 1 = 2k + 1$이므로 $$ 1 + 3 + \cdots + (2k-1) + (2k+1) = k^2 + (2k+1) \ \text{(귀납 가정)} = k^2 + 2k + 1 = (k+1)^2 $$ 이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ (검산: $n = 4$에서 $1 + 3 + 5 + 7 = 16 = 4^2$ ✓.) ### 문제 5 **접근.** 예제 2.1의 재현이다. 5단계 틀의 칸을 먼저 그려 놓고 채운다. 도착점 $\frac{(k+1)(k+2)}{2}$를 계산 전에 적어 두는 것이 핵심이며, 그것이 공통인수 $(k+1)$로 묶는 방향을 정해 준다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$가 성립한다고 가정하자. 보일 것은 $1 + 2 + \cdots + (k+1) = \frac{(k+1)(k+2)}{2}$이다. 마지막 항을 분리해 귀납 가정을 투입한 뒤 공통인수로 묶으면 $$ 1 + \cdots + (k+1) = \big(1 + \cdots + k\big) + (k+1) = \frac{k(k+1)}{2} + (k+1) \ \text{(귀납 가정)} = (k+1)\Big(\frac{k}{2} + 1\Big) = \frac{(k+1)(k+2)}{2} $$ 이며(첫 등호가 마지막 항 분리, 둘째 등호가 귀납 가정) 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **자가 채점.** [기초]에서 양변을 각각 계산했는가, 도착점을 적어 두었는가, "(귀납 가정)" 표시가 있는가 — 채점 기준의 세 항목으로 자기 답안을 검사한다. 검산: $n = 5$에서 $1 + 2 + 3 + 4 + 5 = 15 = \frac{5 \cdot 6}{2}$ ✓. ### 문제 6 **접근.** 세 문장의 뼈대를 먼저 정한다. ① 귀납 단계가 증명하는 대상은 무엇인가 ② 그 대상의 표준 서식은 무엇인가 ③ $P(k)$ 자체의 참은 어디에서 오는가. 낱말 "조건문"이 반드시 들어가야 한다(§1.6, 확인 7). **풀이.** (예시 답안) 귀납 단계에서 증명하는 대상은 명제 $P(k)$가 아니라 조건문 "$P(k) \Rightarrow P(k+1)$"이다. 조건문의 표준 증명은 앞부분을 참이라 놓고 시작하는 것이므로(8$\cdot$15주차 서식), "$P(k)$가 성립한다고 가정하자"는 반칙이 아니라 서식 그 자체다. $P(k)$ 자체의 참은 이 단계에서 주장되지 않으며, 기초 단계가 확보한 $P(1)$에서 전달을 유한 번 적용한 결과로 별도로 확보된다. **복기.** 이 설명이 통하는 이유는 "무엇을 증명 중인가"를 명시적으로 적었기 때문이다. 증명이 반칙처럼 보일 때 첫 점검은 언제나 증명 대상의 재확인이며, 같은 점검이 22주차의 가정 소비 점검과 29주차의 반증 대상 확인에서도 쓰인다. ### 문제 7 **접근.** 예제 2.2의 재현이다. 도착점 $\frac{(k+1)(k+2)(2k+3)}{6}$을 먼저 적어 두고, 계산 중 나오는 이차식을 그 꼴로 인수분해하는 방향을 정한다. 공통인수 $(k+1)$로 묶는 것이 첫 동작이다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= \frac{1 \cdot 2 \cdot 3}{6} = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$이라 가정하자. 보일 것은 $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}$이다. 마지막 항 $(k+1)^2$을 분리해 귀납 가정을 투입하고 $(k+1)$로 묶으면 $$ \sum_{i=1}^{k+1} i^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \ \text{(귀납 가정)} = \frac{(k+1)\big(k(2k+1) + 6(k+1)\big)}{6} = \frac{(k+1)(2k^2 + 7k + 6)}{6} $$ 이고 $2k^2 + 7k + 6 = (k+2)(2k+3)$이므로 $\sum_{i=1}^{k+1} i^2 = \frac{(k+1)(k+2)(2k+3)}{6}$, 곧 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **검산.** $n = 3$에서 좌변 $1 + 4 + 9 = 14$, 우변 $\frac{3 \cdot 4 \cdot 7}{6} = 14$ ✓. 인수분해도 $k = 1$에서 $15 = 3 \cdot 5$로 검산된다. ### 문제 8 **접근.** 도착점은 $\left[\frac{(k+1)(k+2)}{2}\right]^2$이다. 마지막 항 $(k+1)^3$을 분리해 귀납 가정을 넣으면 $\frac{k^2(k+1)^2}{4} + (k+1)^3$이 되고, 도착점이 $(k+1)^2$을 인수로 가지므로 그것으로 묶는 방향이 정해진다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 1$, 우변 $= \left[\frac{1 \cdot 2}{2}\right]^2 = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $\sum_{i=1}^{k} i^3 = \left[\frac{k(k+1)}{2}\right]^2 = \frac{k^2(k+1)^2}{4}$이라 가정하자. 보일 것은 $\sum_{i=1}^{k+1} i^3 = \left[\frac{(k+1)(k+2)}{2}\right]^2$이다. 마지막 항 $(k+1)^3$을 분리해 귀납 가정을 투입하고 $(k+1)^2$으로 묶으면 $$ \sum_{i=1}^{k+1} i^3 = \frac{k^2(k+1)^2}{4} + (k+1)^3 \ \text{(귀납 가정)} = \frac{(k+1)^2\big(k^2 + 4(k+1)\big)}{4} = \frac{(k+1)^2(k+2)^2}{4} $$ 이고(괄호 안은 $k^2 + 4k + 4 = (k+2)^2$) 이 값은 $\left[\frac{(k+1)(k+2)}{2}\right]^2$, 곧 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **복기.** 우변이 예제 2.1의 우변을 제곱한 것이므로 이 등식은 $\sum i^3 = \big(\sum i\big)^2$로도 읽힌다. 두 공식의 이 관계는 증명으로 확정된 사실이지 우연한 관찰이 아니다. 검산: $n = 3$에서 좌변 $1 + 8 + 27 = 36$, 우변 $\left[\frac{3 \cdot 4}{2}\right]^2 = 36$ ✓. ### 문제 9 **접근.** $(k+1)$번째 항은 $3i - 2$의 $i$ 자리에 $k+1$을 넣은 $3(k+1) - 2 = 3k + 1$이다. 도착점은 $\frac{(k+1)\big(3(k+1) - 1\big)}{2} = \frac{(k+1)(3k+2)}{2}$이므로, 통분한 뒤 분자에서 $(k+1)$을 인수로 뽑는 방향으로 정리한다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= 3 \cdot 1 - 2 = 1$, 우변 $= \frac{1 \cdot 2}{2} = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $\sum_{i=1}^{k}(3i-2) = \frac{k(3k-1)}{2}$이라 가정하자. 보일 것은 $\sum_{i=1}^{k+1}(3i-2) = \frac{(k+1)(3k+2)}{2}$이다. 마지막 항 $3(k+1) - 2 = 3k+1$을 분리해 귀납 가정을 투입하면 $$ \sum_{i=1}^{k+1}(3i-2) = \frac{k(3k-1)}{2} + (3k+1) \ \text{(귀납 가정)} = \frac{3k^2 - k + 6k + 2}{2} = \frac{3k^2 + 5k + 2}{2} = \frac{(k+1)(3k+2)}{2} $$ 이고, $3k + 2 = 3(k+1) - 1$이므로 이 식은 $\frac{(k+1)\big(3(k+1)-1\big)}{2}$, 곧 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **복기.** 마지막 한 줄("$3k+2 = 3(k+1) - 1$")을 빼면 도착점과 같은 식이라는 확인이 없는 셈이다. 정리된 결과와 도착점이 겉보기에 다를 때는 한쪽을 다른 쪽의 꼴로 다시 적어 일치를 보인다. 검산: $n = 3$에서 $1 + 4 + 7 = 12$이고 $\frac{3 \cdot 8}{2} = 12$ ✓. ### 문제 10 **접근.** 마지막 항은 $\frac{1}{(k+1)(k+2)}$이다. 도착점이 $\frac{k+1}{k+2}$이므로 통분해 분자를 정리했을 때 $(k+1)^2$이 나와야 하고, 분모 $(k+1)(k+2)$와 약분되어 도착점이 된다. 분자 전개가 완전제곱이 되는지가 관건이다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 좌변 $= \frac{1}{1 \cdot 2} = \frac12$, 우변 $= \frac{1}{2}$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $\frac{1}{1 \cdot 2} + \cdots + \frac{1}{k(k+1)} = \frac{k}{k+1}$이라 가정하자. 보일 것은 그 합에 $\frac{1}{(k+1)(k+2)}$을 더한 값이 $\frac{k+1}{k+2}$이라는 것이다. 마지막 항을 분리해 귀납 가정을 투입하면 $$ \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} \ \text{(귀납 가정)} = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{k^2 + 2k + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2} $$ 이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **복기.** 통분한 분자가 완전제곱으로 뭉치고 분모의 한 인수와 약분되는 구조가 이 문제의 전부다. 같은 합이 45~46주차에서 부분합으로 다시 나오며, 그때는 $\frac{n}{n+1}$이 1에 가까워지는지를 묻는다. 검산: $n = 2$에서 $\frac12 + \frac16 = \frac23$ ✓. ### 문제 11 **접근.** 기초를 $n = 0$에서 잡는다(§1.3). 귀납 단계에서는 마지막 항 $2^{k+1}$을 분리해 귀납 가정을 넣으면 $(2^{k+1} - 1) + 2^{k+1}$이 되고, 같은 것 두 개의 합이 $2 \cdot 2^{k+1} = 2^{k+2}$가 되어 지수가 하나 오른다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 0$일 때 좌변 $= 2^0 = 1$, 우변 $= 2^{1} - 1 = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 0$인 정수 $k$에 대해 $\sum_{i=0}^{k} 2^i = 2^{k+1} - 1$이라 가정하자. 보일 것은 $\sum_{i=0}^{k+1} 2^i = 2^{k+2} - 1$이다. 마지막 항 $2^{k+1}$을 분리해 귀납 가정을 투입하면 $$ \sum_{i=0}^{k+1} 2^i = \Big(\sum_{i=0}^{k} 2^i\Big) + 2^{k+1} = (2^{k+1} - 1) + 2^{k+1} \ \text{(귀납 가정)} = 2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 $$ 이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 정수 $n \ge 0$에서 성립한다. $\blacksquare$ **복기.** 이 등식은 문제 18의 등비 합 공식에서 $r = 2$인 경우다. 첨자가 0부터 시작한다는 점이 문제 3(c)에서 걸린 지점이므로, 공식을 외울 때 범위를 함께 외운다. 검산: $n = 3$에서 $1 + 2 + 4 + 8 = 15 = 2^4 - 1$ ✓. ### 문제 12 **접근.** 예제 2.3의 재현이다. 세 부품이 다 있는지 점검한다 — ① $x$ 포함/미포함 두 무리로의 분할 ② 포함 무리와 $A'$의 부분집합 사이의 1대1 대응 ③ 덧셈 원리. 하나라도 빠지면 $2^k + 2^k$라는 등식의 근거가 사라진다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 0$일 때 $A = \emptyset$이고 $\mathcal{P}(\emptyset) = \{\emptyset\}$이므로 $|\mathcal{P}(A)| = 1 = 2^0$이다. ✓ **[귀납]** $k \ge 0$인 정수 $k$에 대해, 크기가 $k$인 모든 집합의 멱집합 크기가 $2^k$라 가정하자. $|A| = k+1$이라 하고, $A$가 비어 있지 않으므로 원소 $x \in A$를 하나 고정해 $A' = A - \{x\}$라 하면 $|A'| = k$이다. $A$의 부분집합 전체를 두 무리로 나눈다. $x$를 포함하지 않는 부분집합은 정확히 $A'$의 부분집합이므로 귀납 가정에 의해 $2^k$개다. $x$를 포함하는 부분집합은 $S \mapsto S \cup \{x\}$가 $A'$의 부분집합 전체와의 1대1 대응이므로 역시 귀납 가정에 의해 $2^k$개다. 어떤 부분집합이든 $x$를 포함하거나 포함하지 않거나 둘 중 정확히 하나이므로 두 무리는 겹치지 않고 전체를 덮는다. 덧셈 원리에 의해 $|\mathcal{P}(A)| = 2^k + 2^k = 2^{k+1}$이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 정수 $n \ge 0$에서 성립한다. $\blacksquare$ **복기.** 귀납 가정이 두 번 투입된다는 점이 이 증명의 특징이므로, 두 무리의 개수를 세는 자리마다 표시를 붙인다. 검산: $|A| = 2$에서 $\mathcal{P}(\{1,2\}) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$로 4개이고 $2^2 = 4$ ✓. ### 문제 13 **접근.** 귀납 대상이 $n$이 아니라 **지수 $m$**이다. 기초 $m = 1$에서 보일 것은 $a^1 \equiv b^1$인데 이는 명제의 가정 그 자체이므로 계산할 것이 없다. 귀납 단계에서는 (C5)에 넣을 합동식 두 개를 고른다 — 하나는 귀납 가정 $a^k \equiv b^k$, 다른 하나는 가정 $a \equiv b$다. **풀이.** $a \equiv b \pmod n$이라 하자. $m$에 대한 수학적 귀납법으로 증명한다. **[기초]** $m = 1$일 때 보일 것은 $a^1 \equiv b^1 \pmod n$이고, $a^1 = a$, $b^1 = b$이므로 이는 가정 $a \equiv b \pmod n$ 그 자체다. 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $a^k \equiv b^k \pmod n$이라 가정하자. 보일 것은 $a^{k+1} \equiv b^{k+1} \pmod n$이다. (C5) 곱 보존을 두 합동식 $a^k \equiv b^k$ (귀납 가정)과 $a \equiv b$ (명제의 가정)에 적용하면 $a^k \cdot a \equiv b^k \cdot b \pmod n$이고, 좌변은 $a^{k+1}$, 우변은 $b^{k+1}$이므로 $a^{k+1} \equiv b^{k+1} \pmod n$이다. 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $m$에서 성립한다. $\blacksquare$ **복기.** 20주차 §1.6에서 (C5)를 "두 번, 세 번 반복 적용"해 얻던 것이 정리가 되었다 — 반복 논법을 정식 증명으로 바꾸는 것이 귀납법이 하는 일이다. 주의할 것은 되돌리기가 보장되지 않는다는 점이다: $a^3 \equiv b^3$에서 $a \equiv b$를 끌어내는 서술은 (C5)가 지지하지 않는다. 검산: $7 \equiv 2 \pmod 5$이고 $7^3 = 343 = 5 \cdot 68 + 3$, $2^3 = 8 = 5 + 3$으로 둘 다 나머지 3 ✓. ### 문제 14 **접근.** 기초가 $n = 2$이고 그 경우는 27주차 예제 2.1에서 이미 증명되었으므로 인용 한 줄로 끝난다. 귀납 단계에서는 $k+1$개의 합집합을 $\big(A_1 \cup \cdots \cup A_k\big) \cup A_{k+1}$로 묶어 두 집합짜리 정리를 먼저 쓰고, 그다음에 귀납 가정을 쓴다. 두 등호에 각각 다른 근거가 붙는다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 2$일 때 보일 것은 $(A_1 \cup A_2)^c = A_1^c \cap A_2^c$이고, 이는 27주차 예제 2.1에서 증명한 2집합 드모르간 법칙이다(근거 ④). 성립한다. ✓ **[귀납]** $k \ge 2$인 자연수 $k$에 대해 $\big(A_1 \cup \cdots \cup A_k\big)^c = A_1^c \cap \cdots \cap A_k^c$이라 가정하자. 보일 것은 $\big(A_1 \cup \cdots \cup A_{k+1}\big)^c = A_1^c \cap \cdots \cap A_{k+1}^c$이다. 표기 약속으로 마지막 집합을 떼어 낸 뒤 2집합 드모르간과 귀납 가정을 차례로 쓰면 $$ \big(A_1 \cup \cdots \cup A_{k+1}\big)^c = \Big(\big(A_1 \cup \cdots \cup A_k\big) \cup A_{k+1}\Big)^c = \big(A_1 \cup \cdots \cup A_k\big)^c \cap A_{k+1}^c = \big(A_1^c \cap \cdots \cap A_k^c\big) \cap A_{k+1}^c $$ 이고(첫째 등호가 왼쪽 묶기 표기 약속(근거 ①), 둘째 등호가 2집합 드모르간, 셋째 등호가 귀납 가정), 이는 $A_1^c \cap \cdots \cap A_{k+1}^c$, 곧 도착점이다. 수학적 귀납법에 의해 $n \ge 2$인 모든 자연수 $n$에서 성립한다. $\blacksquare$ **복기.** 27주차 문제 17은 이 정리의 $n = 3$인 경우이며, 그때는 2집합 버전을 두 번 적용해 손으로 처리했다. "두 번 적용"을 "$k$번 적용"으로 밀어 올리는 장치가 귀납법이고, §2 끝의 빚 회수 절에서 적은 곱셈$\cdot$덧셈 원리 일반형의 증명도 같은 모양이다 — 사실 2의 귀납 단계가 이 문항과 같은 자리에서 같은 표기 약속을 쓴다. 다만 28주차의 첨자 드모르간($\forall i$ 형태)은 별개의 정리다 — 그쪽은 임의의 첨자를 양화사로, 이쪽은 유한 개를 귀납으로 다룬다. ### 문제 15 **접근.** (a)는 지수 $k$에 대한 귀납이고 기초는 $10^1 - 1 = 9$의 확인이다. 귀납 단계는 (C5)에 $10^k \equiv 1$과 $10 \equiv 1$을 넣는다. (b)는 각 자리를 따로 처리한 뒤 전부 더한다 — "따로 처리"가 (C5), "전부 더하기"가 (C4)다. **풀이.** **(a)** $k$에 대한 수학적 귀납법으로 증명한다. **[기초]** $k = 1$일 때 $10 - 1 = 9 = 9 \times 1$이므로 $9 \mid (10 - 1)$, 곧 $10^1 \equiv 1 \pmod 9$이다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $10^k \equiv 1 \pmod 9$이라 가정하자. 보일 것은 $10^{k+1} \equiv 1 \pmod 9$이다. (C5)를 두 합동식 $10^k \equiv 1$ (귀납 가정)과 $10 \equiv 1$([기초]에서 확인)에 적용하면 $10^k \cdot 10 \equiv 1 \cdot 1 \pmod 9$, 곧 $10^{k+1} \equiv 1 \pmod 9$이다. 수학적 귀납법에 의해 모든 자연수 $k$에서 성립한다. $\blacksquare$ **(b)** $N = d_m 10^m + \cdots + d_1 10 + d_0$이라 하자. 각 $i$ ($1 \le i \le m$)에 대해 (a)에 의해 $10^i \equiv 1 \pmod 9$이고 $d_i \equiv d_i \pmod 9$는 (C1) 반사로 참이므로, (C5)를 이 두 합동식에 적용하면 $d_i 10^i \equiv d_i \cdot 1 = d_i \pmod 9$이다. $i = 0$일 때는 $10^0 = 1$이므로 $d_0 \equiv d_0$이 그대로 성립한다. 이제 (C4) 합 보존을 두 개씩 $m$번 이어 적용해 $m+1$개의 합동식을 하나로 합치면 $$ N = \sum_{i=0}^{m} d_i 10^i \equiv \sum_{i=0}^{m} d_i = d_m + \cdots + d_1 + d_0 \pmod 9 $$ 를 얻는다. $\blacksquare$ (자릿수는 유한하므로 (C4)의 적용도 유한 번으로 끝난다. 임의의 $m$에 대해 이 반복 자체를 정식화하려면 $m$에 대한 또 한 번의 귀납이 필요하고, 그 형태는 문제 13과 같다.) **복기.** 20주차 문제 15는 세 자리 수에 한정된 9의 배수 판정법이었고, 이제 자릿수 제한이 사라졌다. 판정법의 정체는 "$10 \equiv 1 \pmod 9$"라는 한 줄이며 거듭제곱 보존이 그 한 줄을 모든 자리로 옮겨 준다. 검산: $N = 4728$에서 자릿수 합은 $21 = 9 \cdot 2 + 3$이고 $4728 = 9 \cdot 525 + 3$으로 나머지가 같다 ✓. ### 문제 16 **접근.** 도착점이 등식이 아니라 부등식 $k + 1 < 2^{k+1}$이다. 귀납 가정을 투입하면 목표보다 약한 결과가 나오므로 남은 간극을 부등식의 성질로 메운다. $2^{k+1} = 2 \cdot 2^k$로 쓰고 귀납 가정의 양변에 2를 곱한 뒤((W3)), $2k$와 $k+1$을 비교한다. **풀이.** $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 1$일 때 $1 < 2 = 2^1$이므로 성립한다. ✓ **[귀납]** $k \ge 1$인 자연수 $k$에 대해 $k < 2^k$이라 가정하자. 보일 것은 $k + 1 < 2^{k+1}$이다. 귀납 가정의 양변에 양수 2를 곱하면 (W3)에 의해 부등호 방향이 유지되어 $2k < 2 \cdot 2^k = 2^{k+1}$이다. 한편 $k \ge 1$이므로 (W2)에 의해 $k + k \ge k + 1$이다. 두 부등식을 이으면 $$ 2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1 $$ 이므로 $k + 1 < 2^{k+1}$이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 자연수 $n$에서 성립한다. $\blacksquare$ **복기.** 부등식 귀납의 표준 모양은 두 단계다 — ① 귀납 가정을 투입해 얻는 부등식 ② 남은 간극을 메우는 별도의 부등식. 여기서 ①은 $2^{k+1} > 2k$, ②는 $2k \ge k+1$이며, ②의 근거는 $k \ge 1$이라는 귀납 단계의 범위 조건이다. 32주차의 $2^n \ge n^2$이 같은 2단 구조를 더 넓은 간극에서 쓴다. 검산: $n = 5$에서 $5 < 32$ ✓. ### 문제 17 **접근.** 두 단계를 각각 점검한다. 귀납 단계의 계산은 등식의 양변에 1을 더한 것이므로 흠이 없고 조건문으로서도 참이다. 그렇다면 남은 곳은 기초 단계뿐이며, §1.4의 삭제 실험 1이 정확히 이 사례였다. **풀이.** 결함은 **기초 단계가 없다**는 것이다. 그리고 있을 수도 없다 — $P(1)$은 "$1 = 2$"이므로 거짓이고, 어떤 $n$에서도 $P(n)$은 거짓이다. 귀납 단계 "$P(k) \Rightarrow P(k+1)$"은 실제로 참인 조건문이다. $k = k+1$을 가정하고 양변에 1을 더하면 $k+1 = k+2$가 나오므로 전달은 정상적으로 성립한다. 다만 8주차 진리표에서 확인했듯 거짓에서 거짓으로 가는 조건문도 참이므로, 귀납 단계가 참이라는 사실만으로는 어떤 명제의 참도 확보되지 않는다. 전달 고리는 이미 넘어진 것이 있을 때만 다음 것을 넘어뜨린다. 따라서 결론은 도출되지 않는다 — 원리는 두 항목이 **모두** 증명될 것을 요구하는데 이 '증명'은 하나만 갖추었고, 기초 단계는 형식적 절차가 아니라 사슬의 시작점을 확보하는 논리적 필수 조건이다. **복기.** 답안을 검사할 때 계산보다 먼저 볼 것은 두 단계의 존재 여부다. 계산이 한 줄도 틀리지 않았는데 결론이 거짓이면 오류는 계산이 아니라 구조에 있다 — 1주차 문제 6에서 계산이 아니라 설정에 오류가 있던 것과 같은 종류다. 35주차 오류 진단에서 이 사례가 "기초 누락" 유형으로 다시 나온다. ### 문제 18 **접근.** 기초는 $n = 0$이고, 이때 좌변은 항이 하나뿐이므로 $1$이다. 가정 $r \neq 1$이 쓰이는 자리를 먼저 정한다 — 우변의 분모 $r - 1$이 0이 되지 않도록 보장하는 자리이며, 이 가정이 없으면 명제 자체가 성립하지 않는다. 귀납 단계는 $\frac{r^{k+1} - 1}{r - 1} + r^{k+1}$의 통분이다. **풀이.** $r \neq 1$인 실수 $r$가 주어졌다고 하자. 이때 $r - 1 \neq 0$이므로 우변의 분모는 0이 아니다. $n$에 대한 수학적 귀납법으로 증명한다. **[기초]** $n = 0$일 때 좌변은 항이 하나뿐이므로 $1$, 우변 $= \frac{r^{1} - 1}{r - 1} = 1$이므로 성립한다. ✓ **[귀납]** $k \ge 0$인 정수 $k$에 대해 $1 + r + \cdots + r^k = \frac{r^{k+1} - 1}{r - 1}$이라 가정하자. 보일 것은 $1 + r + \cdots + r^{k+1} = \frac{r^{k+2} - 1}{r - 1}$이다. 마지막 항 $r^{k+1}$을 분리해 귀납 가정을 투입하고 통분하면 $$ 1 + r + \cdots + r^{k+1} = \frac{r^{k+1} - 1}{r - 1} + r^{k+1} \ \text{(귀납 가정)} = \frac{r^{k+1} - 1 + r^{k+2} - r^{k+1}}{r - 1} = \frac{r^{k+2} - 1}{r - 1} $$ 이며 이것이 도착점이다. 수학적 귀납법에 의해 모든 정수 $n \ge 0$에서 성립한다. $\blacksquare$ **복기.** 분자에서 $r^{k+1}$과 $-r^{k+1}$이 소거되는 것이 계산의 전부다. 문제 11은 이 정리의 $r = 2$인 경우다. 가정 $r \neq 1$을 어디에 썼는지 답안에 명시하지 않으면 가정을 소비하지 않은 증명이 된다(22주차의 점검 습관). 검산: $r = 3$, $n = 2$에서 좌변 $1 + 3 + 9 = 13$, 우변 $\frac{27 - 1}{2} = 13$ ✓. ### 문제 19 **접근.** (a)는 양 끝에서 안쪽으로 짝을 지어 쌍의 개수와 쌍의 값을 센다. (b)는 두 논증이 각각 무엇을 주고 무엇을 주지 못하는지로 비교한다. (c)는 1주차 문제 16(연속한 두 정수의 곱은 짝수)의 인용이다. **풀이.** (a) $1$부터 $100$까지를 양 끝에서 짝지으면 $1 + 100 = 101$, $2 + 99 = 101$, …, $50 + 51 = 101$이다. $100$개의 수가 두 개씩 묶이므로 쌍은 $50$개이고, 각 쌍의 합이 $101$이므로 전체 합은 $50 \times 101 = 5050$이다. 예제 2.1의 공식에 $n = 100$을 넣으면 $\frac{100 \cdot 101}{2} = 5050$으로 일치한다 ✓. (b) (예시) 짝짓기 논증의 장점은 공식이 **왜** $\frac{n(n+1)}{2}$의 모양인지 보여 준다는 것이다 — 쌍의 값 $n+1$과 쌍의 개수 $\frac{n}{2}$가 우변의 두 인수로 그대로 나타난다. 단점은 $n$이 홀수일 때 가운데 수가 짝을 잃어 논의를 따로 붙여야 한다는 것이다. 귀납 증명의 장점은 $n$의 홀짝에 상관없이 같은 두 단계로 완결된다는 것이고, 단점은 공식을 미리 알아야 시작할 수 있어 발견에는 쓰이지 않는다는 것이다. 발견은 짝짓기로, 확정은 귀납으로 한다. (c) $n(n+1)$은 연속한 두 정수의 곱이므로 짝수이고(1주차 문제 16), 따라서 $n(n+1) = 2t$인 정수 $t$가 존재해 $\frac{n(n+1)}{2} = t$는 정수다. $n \ge 1$이면 이 값은 양수이므로 자연수다. **복기.** (c)는 30주 전에 증명한 명제가 지금 답안의 한 줄로 그대로 인용되는 사례다. 근거 ④의 목록은 시간이 지나도 줄지 않으며, 오래된 정리일수록 인용 빈도가 높다. ### 문제 20 **접근.** (a)는 도미노 모형을 걷어 내고 조건문의 사슬과 긍정 논법(11주차)으로 같은 내용을 다시 쓴다. 핵심은 "임의의 $n$이 1에서 유한 걸음 거리에 있다"는 사실이다. (b)는 채점 기준의 세 항목 중 두 개를 질문 꼴로 바꾼다. **풀이.** (예시 답안) (a) 기초 단계는 $P(1)$을 확보하고, 귀납 단계는 조건문 사슬 $P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow \cdots$의 모든 고리를 한꺼번에 제공하므로, 임의의 자연수 $n$에 대해 긍정 논법(11주차)을 $n-1$번 적용하면 $P(n)$에 도달한다. 어떤 자연수도 1에서 유한 걸음 거리에 있으므로 이 사슬이 자연수 전체를 덮는다. (b) ① "기초 단계에서 양변(또는 명제 전체)을 실제로 계산해 확인했는가 — '명백하다'로 넘긴 곳은 없는가?" ② "귀납 단계에서 귀납 가정을 실제로 사용한 지점에 표시가 있는가 — 없다면 이 증명에 귀납법이 필요하기는 했는가?" **복기.** (a)에서 "유한 걸음"이 결정적이다. 무한히 많은 명제를 다루면서도 각 명제까지의 거리는 유한하다는 점이 두 개의 증명으로 충분한 이유이며, 33주차에서 이 성질을 최소원리 쪽에서 다시 바라본다. --- **다음 주 예고:** 귀납법을 부등식($2^n \ge n^2$ — 29주차 문제 8(b)에서 실험으로 범위만 제안해 둔 그 명제)과 나누어떨어짐($6 \mid (n^3 - n)$의 귀납 버전)으로 확장한다. 도착점이 등식이 아닐 때 귀납 가정을 투입한 뒤 남는 간극을 16주차 부등식 도구로 메우는 2단 구조가 다음 주의 기술이며, 이번 주 문제 16이 그 첫 사례였다. 나누어떨어짐 쪽에서는 $f(k+1)$을 $f(k)$의 배수 항과 잔여 항으로 쪼개는 변형이 표준 첫수가 된다.