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

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

이 주의 길잡이

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

이 주의 위치: 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. 수학적 귀납법의 원리(기초 단계 + 귀납 단계)와 증명 서식을 백지에 정확히 쓰고, 각 조각이 무엇을 막는지 설명할 수 있다.

  2. 합 공식(\(\sum i\), \(\sum i^2\), \(\sum i^3\), 홀수 합, 등비 합)을 귀납으로 증명한다 — 고2 수열 단원에서 공식으로만 외운 등식들의 회수.

  3. \(|\mathcal{P}(A)| = 2^n\)(4주차), \(a \equiv b \Rightarrow a^m \equiv b^m\)(20주차), \(n\)집합 드모르간(27주차)을 증명해 미뤄 둔 약속을 이행한다.

  4. “귀납 가정은 가정할 것을 가정하는 반칙이 아니다”를 8주차 조건문의 언어로 설명할 수 있다.

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

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

  1. \(\sum_{i=1}^{4} i^2\)을 계산하시오.

  2. 조건문 “\(P \Rightarrow Q\)”를 증명할 때 답안의 첫 문장은 무엇인가 (8\(\cdot\)15주차). 한 줄로 쓰시오.

  3. 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주 동안 쌓은 도구만으로 밀어붙여 본다.

명제. 모든 자연수 \(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주차 이래의 절차인데, 첫걸음에서 멈춘다.

시도 — 좌변을 전개하기

“\(n\)을 자연수라 하자. 그러면 \(1 + 2 + \cdots + n = \ \) … “

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

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

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

답

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

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

필요한 것은 명제 하나하나를 따로 상대하지 않는 길이다. 명제가 \(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\)

확인 2. 빈칸 (1)~(4)를 채우고, “\(P(3)\)이 참임을 이미 알고 있을 때 \(P(4)\)를

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

답

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

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

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

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

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

확인 3. 위 방식으로 \(P(100)\)에 도달하려면 어떤 사실들이 필요한가.

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

답

\(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에서 셈한 절약을 문장으로 굳혔을 뿐이다.

백지 암기 대상

수학적 귀납법의 원리 (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) [백지 암기 대상]#

위 원리의 첫째 항목을 증명하는 부분을 기초 단계(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)\)”은 참이다.

확인 4. 그런데 “\(n = n+1\)”은 어떤 자연수에서도 거짓이다. 무엇이 이 결론을

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

답

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

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

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

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

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

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

확인 5. 기초 단계 \(P(1)\)까지 있을 때, 이 상태에서 확보되는 명제를 전부

적어 보자.

답

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

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

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

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

적용된 것이다.

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

5 서식#

백지 암기 대상

귀납 증명의 서식

명제. 모든 자연수 \(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)\)의 구체적인 모양을 옆에 적어 둔다 — 도착점을 모르면 어느 방향으로 인수분해할지 정해지지 않는다. ② 귀납 가정을 실제로 쓴 지점에 “(귀납 가정)”이라고 표시한다.

확인 6. 어떤 답안의 [귀납] 부분에 “(귀납 가정)” 표시가 한 군데도 없다.

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

답

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

답안이 완성된다. ② 가정을 한 번도 쓰지 않고 \(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)\)에서 전달을 유한 번 적용해 따로 얻는다.

확인 7. “귀납 단계는 \(P(k)\)를 가정하므로 순환 논증이다”라는 지적에

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

답

귀납 단계가 증명하는 것은 \(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주차). 오른쪽 등식이 귀납 단계의 표준 첫수다 — 합의 마지막 항을 떼어 내면 남은 부분이 정확히 귀납 가정이 다루는 대상이 된다.

확인 8. \(\sum_{i=1}^{k+1} i^2\)을 분리 규칙으로 다시 써 보자.

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

답

\(\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도 같은 반복을 귀납 단계로 적어 보이는 사례다.

확인 9. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

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

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

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

(다) “\(k(k+1)\)은 연속한 두 정수의 곱이므로 짝수다”

답

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

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

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

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

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

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