# 31주차 — 수학적 귀납법의 원리

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 무한히 많은 명제를 두 개의 증명으로 — 첫 명제의 확인과 한 칸 전달.

**이 주의 위치**: 50주 과정의 31주차. 7부(귀납법)의 첫 주다. 4주차 $|\mathcal{P}(A)| = 2^n$, 12~14주차 곱셈$\cdot$덧셈 원리의 일반형, 17주차 $\sum i^2$의 정수성, 20주차 거듭제곱 보존, 27주차 $n$집합 드모르간 — "지금은 인정하고 쓴다(31주차에서 증명)"로 미뤄 둔 사실들을 회수하는 주다.

**원서 대응**: BoP(Book of Proof) 10장 도입부 (Mathematical Induction). 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 수학적 귀납법의 **원리**(기초 단계 + 귀납 단계)와 증명 서식을 백지에 정확히 쓰고, 각 조각이 무엇을 막는지 설명할 수 있다.
1. 합 공식($\sum i$, $\sum i^2$, $\sum i^3$, 홀수 합, 등비 합)을 귀납으로 증명한다 — 고2 수열 단원에서 공식으로만 외운 등식들의 회수.
1. $|\mathcal{P}(A)| = 2^n$(4주차), $a \equiv b \Rightarrow a^m \equiv b^m$(20주차), $n$집합 드모르간(27주차)을 증명해 미뤄 둔 약속을 이행한다.
1. "귀납 가정은 가정할 것을 가정하는 반칙이 아니다"를 8주차 조건문의 언어로 설명할 수 있다.

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

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

1. $\sum_{i=1}^{4} i^2$을 계산하시오.
1. 조건문 "$P \Rightarrow Q$"를 증명할 때 답안의 첫 문장은 무엇인가 (8$\cdot$15주차). 한 줄로 쓰시오.
1. 30주차 판별 시험에서 틀린 문항 하나를 골라 백지로 재시도하시오.

2번 문항이 이번 주의 급소다 — 귀납 단계에서 하는 일이 정확히 조건문 하나를 증명하는 일이기 때문이다.

### 자주 나오는 세 가지 답 — 2번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 결론부터 적기.** "$Q$를 보이겠다"로 시작한다. 도착점을 먼저 의식한

것은 옳다 — 번역표의 절반이 이미 채워져 있다. 빠진 것은 출발점이다. 가정 $P$를 무대에 올리지 않으면 변형에 쓸 재료가 없다. 이번 주에 이 유형은 "귀납 가정을 선언하지 않고 $P(k+1)$을 처음부터 다시 계산하려는 답안"으로 나타난다(예제 2.1의 4단계에서 그 계산이 왜 닫히지 않는지 본다).

- **유형 2 — 진리표로 답하기.** "$P$가 참이고 $Q$가 거짓인 경우가 없음을 보인다."

8주차의 정의 그대로이고 참$\cdot$거짓을 **판정**할 때는 정확하다. 다만 그것은 참의 기준이지 답안의 첫 문장이 아니다. 실행 서식의 첫 문장은 "$P$라 가정하자"이며, 이번 주 귀납 단계의 첫 문장이 그 문장의 특수한 경우다.

- **유형 3 — "$P$도 증명해야 하지 않는가".** 조심성 자체는 옳고, $P$가 어디선가

확보되어야 결론이 쓸모를 갖는 것도 맞다. 다만 조건문 자체는 $P$의 참을 주장하지 않으므로 그 증명에는 $P$의 참이 필요 없다. "귀납 가정은 반칙 아닌가"라는 물음이 정확히 이 자리에서 나오고, §1.6이 그 물음을 다룬다.

## 개념 — 무한히 많은 명제를 다루는 장치

### 1 지금까지의 도구로 시도하면 어디서 막히는가

이번 주의 대표 명제를 놓고, 30주 동안 쌓은 도구만으로 밀어붙여 본다.

:::{container} quotebox
**명제.** 모든 자연수 $n$에 대해 $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$이다.
:::

**시도 (가) — 값을 넣어 확인하기.** $n = 1$: 좌변 $1$, 우변 $1$. $n = 2$: $3$과 $3$. $n = 3$: $6$과 $6$. $n = 4$: $10$과 $10$. 네 번 모두 맞았으므로 참이라고 적고 싶어진다. 그러나 1주차 문제 18에서 $n^2 + n + 41$은 $n = 1$부터 39까지 소수였다가 40에서 무너졌다 — 확인한 사례 밖은 아무것도 확보되지 않는다.

**시도 (나) — 3단계 틀로 직접 증명하기.** 문자 $n$을 잡고 정의를 풀어 목표 꼴로 변형하는 것이 1주차 이래의 절차인데, 첫걸음에서 멈춘다.

:::{admonition} 시도 — 좌변을 전개하기
:class: quotebox

"$n$을 자연수라 하자. 그러면 $1 + 2 + \cdots + n = \ $ … "
:::

좌변을 전개하려면 항이 몇 개인지 알아야 하는데 항의 개수가 $n$ 자체다. $n$이 문자인 한 $\cdots$ 자리에 무엇이 몇 개 들어가는지 적을 수 없다. 1주차의 $2a + 2b$나 2주차의 $(ak)l$처럼 유한 개의 기호로 좌변을 붙잡는 길이 없다.

:::{container} quotebox
**확인 1.** 두 시도가 각각 어디서 멈췄는지 한 구절씩 적고, 다음 줄이 나오려면

무엇이 손에 있어야 하는지 짐작해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(가)는 확인한 사례 밖에서 멈춘다 — 자연수는 무한히 많으므로 확인은 끝나지

않는다. (나)는 좌변의 항 개수가 문자라서 전개가 시작되지 않는다.

필요한 것은 명제 하나하나를 따로 상대하지 않는 길이다. 명제가 $n$마다 하나씩

있다면 **이웃한 두 명제 사이의 관계**를 한 번 확보해 반복하는 방법이 남는다.
:::

### 2 이웃한 두 명제의 관계 — 표로 찾기

$n$마다 명제가 하나씩 있으므로 이름을 붙인다. $n$번째 명제를 $P(n)$이라 쓰고 "피 오브 엔"으로 읽는다. $P$는 함수가 아니라 명제에 붙인 이름표이고, $P(3)$은 "$1 + 2 + 3 = \frac{3 \cdot 4}{2}$"라는 **문장** 하나를 가리킨다.

| **$n$** | **$P(n)$의 좌변** | **$P(n)$의 우변** | **다음 줄의 좌변으로 갈 때 더하는 것** |
|---|---|---|---|
| $1$ | $1$ | $\frac{1 \cdot 2}{2} = 1$ | $+2$ |
| $2$ | $1 + 2 = 3$ | $\frac{2 \cdot 3}{2} = 3$ | $+3$ |
| $3$ | $1 + 2 + 3 = \underline{\quad(1)\quad}$ | $\frac{3 \cdot 4}{2} = \underline{\quad(2)\quad}$ | $+4$ |
| $4$ | $\underline{\quad(3)\quad}$ | $\frac{4 \cdot 5}{2} = \underline{\quad(4)\quad}$ | $+5$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(4)를 채우고, "$P(3)$이 참임을 이미 알고 있을 때 $P(4)$를

확인하는 가장 짧은 길"을 한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $6$  (2) $6$  (3) $10$  (4) $10$.

짧은 길: $P(3)$의 좌변 $6$에 $4$만 더하면 $P(4)$의 좌변이 되고, 우변끼리도

$6 + 4 = 10$으로 맞는다. 처음부터 다시 더할 필요가 없다 — 앞 줄의 결과에 한

항만 얹으면 된다. 어느 줄에서 다음 줄로 가든 방식이 같다.
:::

넘어가는 방식이 전부 같다는 것이 관찰의 핵심이다. 그렇다면 그 넘어가기를 문자 $k$로 한 번만 증명하면 넘어가기 전부가 한꺼번에 확보된다.

:::{container} quotebox
**확인 3.** 위 방식으로 $P(100)$에 도달하려면 어떤 사실들이 필요한가.

그중 실제로 **증명해야 할 것**은 몇 개인가.
:::

:::{admonition} 답
:class: quotebox dropdown

$P(1)$ 하나와 "$P(1)$이면 $P(2)$", …, "$P(99)$이면 $P(100)$"이라는 조건문

99개가 필요하다. 그런데 99개가 전부 같은 모양이므로 문자 $k$로

"$P(k)$이면 $P(k+1)$"을 한 번 증명하면 99개가 동시에 확보된다. 실제로 증명할

것은 **두 개** — $P(1)$과 조건문 하나다. 그리고 이 두 개는 $100$뿐 아니라

**모든** 자연수에 대해 같은 일을 한다.
:::

**도미노 모형.** 도미노가 한 줄로 무한히 서 있다고 하자. ① 첫 번째를 실제로 넘어뜨린다. ② 어느 것이든 넘어지면 바로 다음 것이 넘어지도록 간격을 맞춰 둔다. 이 둘이 갖추어지면 전부 넘어진다 — 어떤 번호든 첫 번째에서 유한 번의 전달로 도달되기 때문이다. ①이 기초 단계, ②가 귀납 단계에 대응한다(문제 2).

### 3 원리에 이름 붙이기

방금 표에서 한 일에 정식 이름을 붙인다. 식 자체에 새로운 것은 없다 — 확인 3에서 셈한 절약을 문장으로 굳혔을 뿐이다.

:::{admonition} 백지 암기 대상
:class: keybox

**수학적 귀납법의 원리 (principle of mathematical induction)**

자연수에 대한 명제 $P(n)$에 대해 다음 두 가지가 증명되면, **모든** 자연수 $n$에 대해 $P(n)$이 참이다.

**(기초 단계)** $P(1)$이 참이다.

**(귀납 단계)** 모든 $k \ge 1$에 대해, $P(k)$가 참이면 $P(k+1)$도 참이다.
:::

이 원리는 자연수의 성질이며, 이 과정에서는 **공리**(증명 없이 받아들이는 출발점)로 쓴다. 33주차에서 최소원리와 서로를 이끌어 낸다는 것을 확인한다.

시작점이 $1$이 아니어도 된다. 명제가 $n \ge 0$에서 주장되면 $P(0)$을 확인하고 고리를 $k \ge 0$에서 세운다 — 사슬의 시작점이 어디든 그 뒤 전부가 확보된다는 점은 같다. 시작점은 명제가 주장하는 범위의 최솟값에 맞춘다(예제 2.3, 문제 11, 문제 14, 문제 18이 각각 $0$, $0$, $2$, $0$에서 시작한다).

### 정의 31.1 — 기초 단계와 귀납 단계 (base case, inductive step) [백지 암기 대상]

:::{container} quotebox
위 원리의 첫째 항목을 증명하는 부분을 **기초 단계**(base case), 둘째 항목을 증명하는 부분을 **귀납 단계**(inductive step)라 한다.

귀납 단계에서 "$P(k)$가 참이다"라고 놓는 가정을 **귀납 가정**(inductive hypothesis)이라 한다.
:::

답안에서는 두 단계를 **[기초]**, **[귀납]**으로 표시하고, 귀납 가정을 실제로 사용한 지점에 "(귀납 가정)"이라고 적는다. 이 표기까지가 서식이다.

### 4 원리 해부 — 조각마다 하는 일

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "자연수에 대한 명제 $P(n)$" | 대상의 선언 | 무엇에 대한 귀납인지 먼저 정한다 — 항의 개수인지, 집합의 크기인지, 지수인지 |
| "$P(1)$이 참이다" | 사슬의 시작점 확보 | 양변(또는 명제 전체)을 **각각** 계산해 확인한다 |
| "모든 $k \ge 1$에 대해" | 고리의 전칭성 | 고리 하나를 문자 $k$로 증명해 무한 개의 고리를 한 번에 얻는다 |
| "$P(k)$가 참이면 $P(k+1)$도 참" | 한 칸 전달 | 조건문이므로 $P(k)$를 가정하고 시작한다(8$\cdot$15주차 서식) |
| "모든 자연수 $n$에 대해 $P(n)$이 참" | 결론 | 두 증명이 끝나면 이 문장을 인용하며 마감한다 |

**조각 삭제 실험 1 — 기초 단계를 지운다.** 귀납 단계만 남기고 $P(n)$을 "$n = n+1$"로 잡아 보자. $k = k+1$이라 가정하고 양변에 1을 더하면 $k+1 = k+2$, 곧 $P(k+1)$이 나온다. 조건문 "$P(k) \Rightarrow P(k+1)$"은 참이다.

:::{container} quotebox
**확인 4.** 그런데 "$n = n+1$"은 어떤 자연수에서도 거짓이다. 무엇이 이 결론을

막는가. 귀납 단계에 흠이 있는가, 아니면 다른 곳인가.
:::

:::{admonition} 답
:class: quotebox dropdown

귀납 단계에는 흠이 없다. 거짓에서 거짓으로 가는 조건문도 참이므로

(8주차 진리표의 F$\Rightarrow$F$=$T) 전달 고리는 정상적으로 만들어진다.

막는 것은 **기초 단계의 부재**다 — $P(1)$은 "$1 = 2$"로 거짓이라 확인될 수

없고, 시작점이 없으면 고리가 아무리 완전해도 어느 $P(n)$도 확보되지 않는다.

기초 단계는 형식적 절차가 아니라 결론을 떠받치는 조건이다(문제 17).
:::

**조각 삭제 실험 2 — "모든 $k \ge 1$"을 지운다.** 고리를 특정한 $k$ 하나, 예컨대 $k = 5$에서만 증명했다고 하자.

:::{container} quotebox
**확인 5.** 기초 단계 $P(1)$까지 있을 때, 이 상태에서 확보되는 명제를 전부

적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

$P(1)$ 하나뿐이다. $P(1)$에서 $P(2)$로 가는 고리가 없으므로 사슬이 첫 칸에서

끊긴다. $k = 5$짜리 고리는 $P(5)$가 확보되기 전에는 아무 일도 하지 않는다.

고리는 **모든** $k$에서 있어야 하고, 그래서 고리의 증명은 반드시 문자 $k$로

한다 — 1주차 확인 13의 "문자 하나가 무한 개의 사례를 대신한다"가 고리에

적용된 것이다.
:::

**조각 삭제 실험 3 — 귀납 단계를 지운다.** 기초 단계만 남으면 $P(1)$ 하나가 확인된 상태이며, 이는 §1.1의 시도 (가)와 같은 자리다. 확인의 개수가 늘어도 상태는 달라지지 않는다.

### 5 서식

:::{admonition} 백지 암기 대상
:class: keybox

**귀납 증명의 서식**

**명제.** 모든 자연수 $n$에 대해 $P(n)$이다.

**증명.** $n$에 대한 수학적 귀납법으로 증명한다.

**[기초]** $n = 1$일 때: (양변 또는 명제 전체를 각각 계산해 확인). ✓

**[귀납]** $k \ge 1$인 자연수 $k$에 대해 $P(k)$가 성립한다고 가정하자(**귀납 가정**). 보일 것은 $P(k+1)$이다. $\quad\vdots\quad$ 따라서 $P(k+1)$이 성립한다.

수학적 귀납법에 의해 모든 자연수 $n$에 대해 $P(n)$이다. $\blacksquare$
:::

**작성 요령 두 가지.** ① 귀납 단계에 들어가면 계산을 시작하기 전에 $P(k+1)$의 구체적인 모양을 옆에 적어 둔다 — 도착점을 모르면 어느 방향으로 인수분해할지 정해지지 않는다. ② 귀납 가정을 실제로 쓴 지점에 "(귀납 가정)"이라고 표시한다.

:::{container} quotebox
**확인 6.** 어떤 답안의 [귀납] 부분에 "(귀납 가정)" 표시가 한 군데도 없다.

이 답안에 대해 무엇을 의심해야 하는가.
:::

:::{admonition} 답
:class: quotebox dropdown

두 가지 중 하나다. ① 가정을 실제로 썼는데 표시만 빠뜨렸다 — 표시를 넣으면

답안이 완성된다. ② 가정을 한 번도 쓰지 않고 $P(k+1)$을 처음부터 직접

계산했다 — 이 경우 그것은 귀납법이 아니라 직접 증명이고, 애초에 귀납법이

필요 없었거나 계산이 §1.1의 시도 (나)처럼 닫히지 않은 채 남아 있다.

표시는 장식이 아니라 어느 쪽인지 드러내는 장치다(22주차의 가정 소비 점검).
:::

### 6 "가정할 것을 가정한다"는 반칙인가

귀납 단계의 첫 문장은 "$P(k)$가 성립한다고 가정하자"이고, 증명하려는 것을 가정하는 것처럼 보인다. 준비 운동의 유형 3이 걸린 자리가 여기다.

증명하는 대상을 정확히 적으면 문제가 사라진다. 귀납 단계에서 증명하는 것은 $P(k)$가 아니라 **조건문 "$P(k) \Rightarrow P(k+1)$"** 이다. 조건문의 표준 증명은 앞부분을 가정하고 시작하는 것이므로(8$\cdot$15주차), "$P(k)$라 가정하자"는 반칙이 아니라 서식이다. 이 단계 어디에서도 "$P(k)$가 참이다"라고 주장하지 않는다 — 주장한 것은 "참이라면 다음도 참"이라는 전달뿐이다. $P(k)$ 자체의 참은 기초 단계가 확보한 $P(1)$에서 전달을 유한 번 적용해 따로 얻는다.

:::{container} quotebox
**확인 7.** "귀납 단계는 $P(k)$를 가정하므로 순환 논증이다"라는 지적에

한 문장으로 답해 보자. 답에 반드시 들어가야 할 낱말은 "조건문"이다.
:::

:::{admonition} 답
:class: quotebox dropdown

귀납 단계가 증명하는 것은 $P(k)$가 아니라 조건문 $P(k) \Rightarrow P(k+1)$이고,

조건문의 증명은 앞부분을 가정하고 시작하는 것이 서식이므로 순환이 아니다.

순환 논증이 되려면 $P(k+1)$을 얻는 과정에서 $P(k+1)$ 자체를 근거로 써야

하는데, 쓰는 것은 한 칸 앞의 $P(k)$다.
:::

### 7 합 기호와 마지막 항 분리

$$
\sum_{i=1}^{n} a_i = a_1 + a_2 + \cdots + a_n, \qquad \sum_{i=1}^{k+1} a_i = \Big(\sum_{i=1}^{k} a_i\Big) + a_{k+1}
$$

$\sum_{i=1}^{n} a_i$는 "아이가 1부터 엔까지 에이 아이의 합"으로 읽는다. $i$는 자리 이름이므로 $j$로 바꿔 써도 같은 수다(17주차). 오른쪽 등식이 귀납 단계의 표준 첫수다 — **합의 마지막 항을 떼어 내면 남은 부분이 정확히 귀납 가정이 다루는 대상이 된다.**

:::{container} quotebox
**확인 8.** $\sum_{i=1}^{k+1} i^2$을 분리 규칙으로 다시 써 보자.

떼어 내는 마지막 항은 무엇인가.
:::

:::{admonition} 답
:class: quotebox dropdown

$\sum_{i=1}^{k+1} i^2 = \Big(\sum_{i=1}^{k} i^2\Big) + (k+1)^2$. 마지막 항은

$a_i = i^2$의 $i$ 자리에 $k+1$을 통째로 넣은 $(k+1)^2$이다. $k^2 + 1$로 적는

경우가 있는데, 넣는 자리는 $i$가 나타나는 모든 자리다. 이 대입 규칙은

도착점 $P(k+1)$의 모양을 적을 때도 그대로 쓴다.
:::

### 8 근거 목록 갱신 — 칸은 그대로 네 개

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 기존 정의들 + **정의 31.1(기초 단계$\cdot$귀납 단계$\cdot$귀납 가정)**, $\sum$ 표기(17주차) | 답안에 [기초]/[귀납]을 세우고 "(귀납 가정)" 사용 지점을 표시한다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | $k$가 자연수이면 $k+1$도 자연수라는 확인 — 귀납 단계의 도착점이 명제의 범위를 벗어나지 않는다 |
| ③ 등식$\cdot$부등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산, (W2)(W3)(16주차) | 귀납 단계 변형의 대부분, 문제 16의 연결 부등식 |
| ④ 이미 증명한 명제 | **수학적 귀납법의 원리(§1.3, 공리)**, (C1)(C4)(C5)(20주차), 2집합 드모르간(27주차 예제 2.1), 두 집합 덧셈 원리(14주차 §1.2), 두 단계 곱셈 원리(12주차 §1.4~1.5), 1주차 문제 16, 이번 주에 증명하는 합 공식들과 두 세기 원리의 일반형(§2 빚 회수) | 마감 문장 "수학적 귀납법에 의해"가 곧 원리의 인용이다 |

12~14주차에서 곱셈 원리와 덧셈 원리의 일반형을 "지금은 인정하고 쓴다 (31주차에서 증명)"로 미뤄 두었다. 그 유보가 이번 주에 풀린다. 두 원리의 일반형은 두 단계$\cdot$두 집합 버전을 $n$번 반복해 얻는 것이고, "반복해서 얻는다"를 정식 증명으로 바꾸는 장치가 이번 주의 원리다. 두 증명은 5단계 틀을 세운 뒤 §2 끝의 빚 회수 절에 적는다. 예제 2.3과 문제 14도 같은 반복을 귀납 단계로 적어 보이는 사례다.

:::{container} quotebox
**확인 9.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) "$n = 1, 2, 3, 4$에서 성립함을 확인했으므로 모든 $n$에서 성립한다"

(나) "귀납 가정에 의해 $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$이다"

(다) "$k(k+1)$은 연속한 두 정수의 곱이므로 짝수다"
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 불허 — 유한 확인은 목록 밖이다(§1.1의 시도 (가)). 같은 계산을

[기초] $P(1)$의 확인으로 쓰면 근거 ①의 정상적인 한 줄이 된다.

(나) 허용 — 근거 ①. 정의 31.1이 귀납 단계 안에서 이 가정을 놓는 것을

서식으로 정하고 있다. 다만 [귀납] 표시 안에서만 유효하다.

(다) 허용 — 근거 ④. 1주차 문제 16에서 증명한 명제의 인용이다(문제 19(c)).
:::

정의 31.1과 원리 문장은 외운다. 통째로만 외우지 말고 §1.4의 조각별 역할과 함께 외운다 — 조각을 잊어도 "무엇을 막는 조건이었는가"에서 재구성할 수 있다.