증명 도구 상자 · 노트

3 T3 귀납법과 재귀적 정의

$n$이 들어간 주장을 모든 자연수에서 증명할 때, 그리고 재귀식으로 정한 양이 하나로 정해짐을 보일 때 귀납법을 쓴다. 1회의 곱의 법칙, 포함배제의 귀납 증명, Pascal 재귀의 유일성이 이 절의 도구다.

3.1 정렬원리와 귀납법

자연수 $\NN=\{1,2,3,\dots\}$의 다음 성질을 공리로 받아들인다.

정의 3.1 (정렬원리) $\NN$의 공집합이 아닌 부분집합은 가장 작은 원소를 갖는다.

정리 3.2 (수학적 귀납법) 명제 $P(n)$에 대해 (i) $P(1)$이 참이고 (ii) 모든 $n\ge1$에서 $P(n)\Rightarrow P(n+1)$이면, 모든 $n\in\NN$에서 $P(n)$이 참이다.

증명 전략 거짓인 $n$이 있다고 가정하고, 그 가운데 가장 작은 것을 잡아 모순을 끌어낸다.

1. $S=\{n\in\NN:\ P(n)\text{이 거짓}\}$이 공집합이 아니라고 가정한다.귀류 가정 [T2]

2. $S$의 가장 작은 원소 $m$이 있다.정렬원리

3. (i)로 $1\notin S$이므로 $m\ge2$이고, $m-1\in\NN$이다.(i)

4. $m-1<m$이고 $m$이 $S$의 최소이므로 $m-1\notin S$, 곧 $P(m-1)$이 참이다.2

5. (ii)로 $P(m)$이 참이다. 이것은 $m\in S$와 모순이다.(ii)

시작점은 1이 아니어도 된다. $P(n_0)$과 $n\ge n_0$에서의 $P(n)\Rightarrow P(n+1)$을 보이면 $n\ge n_0$인 모든 $n$에서 성립한다. 귀납 단계에서 $P(1),\dots,P(n)$을 모두 가정해도 된다. 이것을 강한 귀납법이라 하고, 증명은 위와 같다(4에서 $m$보다 작은 모든 수가 $S$ 밖에 있다).

예제 3.3 (Bernoulli 부등식) $x\ge-1$이면 모든 $n\ge1$에서 $(1+x)^n\ge1+nx$이다.

전략 $(1+x)^{n+1}=(1+x)^n(1+x)$에 귀납 가정을 넣는다. $1+x\ge0$이어야 부등식에 곱할 수 있다.

1. $n=1$이면 양변이 $1+x$로 같다.기저

2. $(1+x)^n\ge1+nx$라 하자. $1+x\ge0$이므로 양변에 곱해도 부등호가 유지된다.

   $$\begin{align*} (1+x)^{n+1}&\ge(1+nx)(1+x) \tag*{\htmlClass{reason}{\text{귀납 가정, $x\ge-1$}}}\\ &=1+(n+1)x+nx^2 \\ &\ge1+(n+1)x \tag*{\htmlClass{reason}{\text{$nx^2\ge0$}}} \end{align*}$$

조건 $x\ge-1$은 2의 첫 부등호에서만 쓰였고, 빼면 결론이 깨진다. $x=-3$, $n=5$이면 왼쪽은 $(-2)^5=-32$, 오른쪽은 $1-15=-14$이다.

예제 3.4 (하키 스틱 항등식) $0\le m\le n$이면 $\sum_{k=m}^n\tbinom km=\tbinom{n+1}{m+1}$이다. $m$을 고정하고 $n$에 대한 귀납법을 쓴다. $n=m$이면 양변이 1이다. $n$에서 성립하면

$$\sum_{k=m}^{n+1}\binom km=\binom{n+1}{m+1}+\binom{n+1}{m}=\binom{n+2}{m+1} .$$

귀납 가정, Pascal 항등식

마지막 등호가 1회 정리 1.5의 Pascal 항등식이다. 이항계수의 항등식은 대부분 이처럼 Pascal 항등식 한 번으로 귀납 단계가 끝난다.

예제 3.5 (소인수의 존재 (강한 귀납)) $n\ge2$인 정수는 소수들의 곱이다. $n=2$는 소수다. $2,\dots,n$이 모두 소수들의 곱이라 하고 $n+1$을 보자. $n+1$이 소수이면 끝이다. 아니면 $n+1=ab$, $2\le a,b\le n$이고, 강한 귀납 가정으로 $a$와 $b$가 소수들의 곱이므로 $n+1$도 그렇다. 바로 앞의 $n$만 가정해서는 $a$, $b$에 대해 아무것도 말할 수 없으므로 강한 귀납법이 필요하다.

3.2 재귀적 정의와 유일성

$a_1,a_2$와 “$a_n$을 $a_{n-1},a_{n-2}$로 쓰는 식”을 주면 수열이 정해진다. 정해진다는 것은 두 가지다. 그런 수열이 있고, 두 개가 없다. 있다는 것은 식대로 계산해 나가면 되고, 하나뿐이라는 것은 두 해의 차가 0임을 귀납법으로 보인다. 1회 정리 5.13(Pascal의 재귀)의 유일성 단계가 이 구조이고, 거기서는 귀납의 기준이 $a+b$였다.

예제 3.6 (연속한 1이 없는 이진 문자열) 길이 $n$인 0·1 문자열 가운데 1이 연속해 나오지 않는 것의 수를 $a_n$이라 하자. 마지막 글자가 0이면 앞의 $n-1$글자는 아무 그런 문자열이고, 1이면 그 앞은 0이어야 하므로 앞의 $n-2$글자가 아무 그런 문자열이다. 따라서

$$a_n=a_{n-1}+a_{n-2}\ (n\ge3),\qquad a_1=2,\quad a_2=3 .$$

Fibonacci 수 $F_1=F_2=1$, $F_n=F_{n-1}+F_{n-2}$에 대해 $a_n=F_{n+2}$이다. $n=1,2$에서 $2=F_3$, $3=F_4$이고, 두 수열이 같은 재귀식을 따르므로 $n$에 대한 강한 귀납법으로 모든 $n$에서 같다. 작은 경우를 열거하면 $a_1,\allowbreak \dots,\allowbreak a_8=2,\allowbreak 3,\allowbreak 5,\allowbreak 8,\allowbreak 13,\allowbreak 21,\allowbreak 34,\allowbreak 55$이다.

흔한 실수 (1) 기저를 빠뜨린다. “$n^2+n$은 홀수다”는 귀납 단계가 성립한다. $n^2+n$이 홀수이면 $(n+1)^2+(n+1)=(n^2+n)+2(n+1)$도 홀수다. 그러나 $n=1$에서 $2$이므로 기저가 거짓이고, 실제로 $n^2+n=n(n+1)$은 언제나 짝수다. (2) 귀납 단계가 작은 $n$에서 깨진다. “말 $n$마리는 모두 같은 색이다”의 잘못된 증명은 $n+1$마리를 처음 $n$마리와 마지막 $n$마리로 나눠 각각 같은 색이라 하고, 두 묶음이 겹치므로 전체가 같은 색이라 한다. $n=1$에서 $n+1=2$이면 두 묶음 $\{1\}$과 $\{2\}$는 겹치지 않는다. 귀납 단계는 모든 $n\ge n_0$에서 성립해야 한다.

연습문제

연습 3.1 (제곱의 합 ★) $\sum_{k=1}^nk^2=\tfrac{n(n+1)(2n+1)}6$을 귀납법으로 보여라.

풀이

$n=1$이면 양변이 1이다. $n$에서 성립하면

$$\frac{n(n+1)(2n+1)}6+(n+1)^2=\frac{(n+1)\bigl(2n^2+7n+6\bigr)}6=\frac{(n+1)(n+2)(2n+3)}6 .$$

연습 3.2 (계승의 합 ★) $\sum_{k=1}^nk\cdot k!=(n+1)!-1$을 보여라.

풀이

$n=1$이면 $1=2!-1$이다. $n$에서 성립하면 $(n+1)!-1+(n+1)(n+1)!=(n+1)!(n+2)-1=(n+2)!-1$이다.

연습 3.3 (기저가 1이 아닌 귀납 ★) $n\ge5$이면 $2^n>n^2$임을 보여라. $n=2,3,4$에서는 왜 성립하지 않는가?

풀이

$n=5$이면 $32>25$이다. $n\ge5$에서 $2^n>n^2$이면 $2^{n+1}>2n^2$이고, $2n^2\ge(n+1)^2\iff(n-1)^2\ge2$는 $n\ge3$에서 참이다. $n=2,3,4$에서는 $4=4$, $8<9$, $16=16$으로 기저가 거짓이다. 귀납 단계는 $n\ge3$에서 성립하지만 처음으로 참인 기저가 $n=5$이다.

연습 3.4 (유한 Boole 부등식 ★★) $P(A\cup B)\le P(A)+P(B)$만 써서 $P(A_1\cup\cdots\cup A_n)\le\sum_{i=1}^nP(A_i)$를 귀납법으로 보여라.

풀이

$n=1$은 등호다. $n$에서 성립하고 $B=A_1\cup\cdots\cup A_n$이면

$$P(B\cup A_{n+1})\le P(B)+P(A_{n+1})\le\sum_{i=1}^nP(A_i)+P(A_{n+1}) .$$

연습 3.5 (Weierstrass의 곱 부등식 ★★) $p_1,\dots,p_n\in[0,1]$이면 $\prod_{i=1}^n(1-p_i)\ge1-\sum_{i=1}^np_i$임을 보여라. 독립인 사건 $A_i$가 $P(A_i)=p_i$일 때 이 부등식은 어떤 확률에 대한 무엇이 되는가?

풀이

$n=1$은 등호다. $n$에서 성립하고 $s=\sum_{i\le n}p_i$이면, $1-p_{n+1}\ge0$을 귀납 가정에 곱해

$$\prod_{i\le n+1}(1-p_i)\ge(1-p_{n+1})(1-s)=1-s-p_{n+1}+p_{n+1}s\ge1-\sum_{i\le n+1}p_i .$$

($1-s$가 음수여도 곱셈 단계는 맞다. 곱하는 수 $1-p_{n+1}$이 음이 아니기 때문이다.) 확률로 읽으면 $P(\text{아무것도 일어나지 않는다})\ge1-\sum P(A_i)$, 곧 $P(\text{적어도 하나})\le\sum P(A_i)$이다. 독립인 사건에 대한 Boole 부등식이다.

연습 3.6 (우표 문제 (강한 귀납) ★★) 4원짜리와 5원짜리 우표로 12원 이상의 모든 금액을 만들 수 있음을 강한 귀납법으로 보여라. 만들 수 없는 금액을 모두 구하라.

풀이

기저: $12=4+4+4$, $13=4+4+5$, $14=4+5+5$, $15=5+5+5$. $n\ge16$이고 $12,\dots,n-1$을 모두 만들 수 있으면 $n-4\ge12$를 만들고 4원을 하나 더한다. 네 개의 기저가 필요한 것은 귀납 단계가 4만큼 뒤를 보기 때문이다. 만들 수 없는 금액은 $1,2,3,6,7,11$이다(작은 경우를 모두 확인).

연습 3.7 (Fibonacci 수 ★★) $F_1=F_2=1$, $F_n=F_{n-1}+F_{n-2}$에 대해 (a) $\sum_{k=1}^nF_k=F_{n+2}-1$, (b) $F_n<(7/4)^n$을 보여라.

풀이

(a) $n=1$이면 $1=F_3-1$이다. $\sum_{k\le n+1}F_k=F_{n+2}-1+F_{n+1}=F_{n+3}-1$. (b) $F_1=1<\tfrac74$, $F_2=1<\tfrac{49}{16}$이다. $n\ge3$이고 앞의 두 값에서 성립하면

$$F_n=F_{n-1}+F_{n-2}<\Bigl(\frac74\Bigr)^{n-2}\Bigl(\frac74+1\Bigr)=\Bigl(\frac74\Bigr)^{n-2}\frac{44}{16}<\Bigl(\frac74\Bigr)^{n-2}\frac{49}{16}=\Bigl(\frac74\Bigr)^n .$$

연습 3.8 (잘못된 귀납 찾기 ★★) 다음 “증명”의 오류를 찾아라. 주장: 음이 아닌 모든 정수 $n$에서 $5n=0$이다. 증명: $n=0$이면 맞다. $0,1,\dots,n$에서 맞다고 하자. $n+1=a+b$인 $a,b\le n$을 잡으면 $5(n+1)=5a+5b=0+0=0$이다.

풀이

$n=0$에서 $n+1=1$로 갈 때 $1=a+b$, $a,b\le0$인 음이 아닌 정수가 없다. 귀납 단계가 $0\Rightarrow1$에서 깨진다. $1=0+1$로 쓰면 $b=1$이 귀납 가정의 범위($\le n=0$) 밖이다. 이 논증은 $n+1\ge2$에서만 작동하므로 기저 $n=1$이 필요한데, $5\cdot1\ne0$이다.

연습 3.9 (교란순열의 재귀 ★★★) $1,\dots,n$의 순열 가운데 어느 $i$도 제자리에 있지 않은 것의 수를 $D_n$이라 하자. (a) $D_n=(n-1)(D_{n-1}+D_{n-2})$ ($n\ge3$), $D_1=0$, $D_2=1$임을 보여라. (b) $D_n=n!\sum_{k=0}^n\tfrac{(-1)^k}{k!}$이 이 재귀와 처음 두 값을 만족함을 보이고, 유일성으로 공식을 증명하라. (1회의 Montmort 문제를 포함배제 없이 푼 것이다.)

풀이

(a) 교란순열 $\sigma$에서 $\sigma(n)=j$라 하자($j\ne n$, $n-1$가지). $\sigma(k)=n$인 $k$를 본다. $k=j$인 경우: $\sigma$는 $n$과 $j$를 맞바꾸고, 나머지 $n-2$개 위에서 교란순열이다. $D_{n-2}$가지다. $k\ne j$인 경우: $\{1,\dots,n-1\}$ 위의 $\tau$를 $\tau(k)=j$, 나머지는 $\tau(i)=\sigma(i)$로 정하면 $\tau$는 순열이고 $\tau(k)=j\ne k$이므로 교란순열이다. 거꾸로 교란순열 $\tau$와 $j$가 주어지면 $k=\tau^{-1}(j)\ne j$로 $\sigma$를 되살릴 수 있으므로 일대일 대응이다. $D_{n-1}$가지다. $j$마다 $D_{n-1}+D_{n-2}$가지이므로 $D_n=(n-1)(D_{n-1}+D_{n-2})$이다. $D_1=0$, $D_2=1$은 직접 센다. (b) $E_n=n!\sum_{k=0}^n(-1)^k/k!$이면 $E_n=nE_{n-1}+(-1)^n$이다(마지막 항이 $n!\cdot(-1)^n/n!$). $E_1=0$, $E_2=1$이다. $(n-1)E_{n-2}=E_{n-1}-(-1)^{n-1}$이므로

$$(n-1)(E_{n-1}+E_{n-2})=(n-1)E_{n-1}+E_{n-1}+(-1)^n=nE_{n-1}+(-1)^n=E_n .$$

$D_n$과 $E_n$은 같은 재귀와 같은 처음 두 값을 가지므로 강한 귀납법으로 모든 $n$에서 같다. 처음 값들은 $0,1,2,9,44,265,1854$이다. $D_n/n!$이 Montmort 문제에서 하나도 맞지 않을 확률이다.

이 절을 PDF로 보기 (8쪽)

이 회차에서 읽은 절 0개 · 회차 차례