수학적 귀납법 공부 이모저모

구체수학과 koosaga님 블로그를 참고했습니다.

 

1. 수학적 귀납법

정수 $n$에 관한 어떤 명제가 모든 $n\ge n_0$에 대해 참임을 증명하는 일반적인 방법이다.

이는 2가지 단계로 나뉜다.

• 기초(basis) 단계: $n_0$에 대한 증명
• 귀납(induction) 단계: $n_0,\cdots, n-1$에 대해 증명되었다는 가정 하에 $n>n_0$에 대해 증명

 

2. 하노이탑

세 개의 탑에서 하노이탑 규칙에 따라 옮기는 최소 이동 횟수를 구하면 된다.

우선, 정의를 잘 하는 것이 중요하다. 책의 필자는 명명정복이라고 한다.

 

$T_n:=$ 규칙 하에 다른 한 기둥으로 옮기는데 필요한 최소 이동 횟수

 

1번 기둥에서 2번 기둥으로 위쪽 $n-1$개의 원판을 옮기고, $n$번째 원판을 3번 기둥으로 옮긴 후 2번 기둥에 있던 $n-1$개의 원판을 3번 기둥에 올린다. 그럼 총 이동 횟수 $T_n$은 $T_n\le T_{n-1}+1+T_{n-1}=2T_{n-1}+1$가 된다.

 

이 때, $n$번 원판을 움직이기 위해서 $n-1$개를 들어내는 작업과 $n$번 원판을 놓은 뒤 그 위에 $n-1$개를 쌓는 작업은 필수적으로 동반되므로 $T_n\ge 2T_{n-1}+1$이라는 식도 성립한다. 따라서 $T_n = 2T_{n-1}+1$이다.

 

3. 직선의 평면 최대 분할

• $L_n:=n$개의 직선이 분할한 최대 평면 수

$\text{Theorem. }L_n=L_{n-1}+n$

보조정리 1에 따라 등호를 성립시키면 상한을 달성하므로 최대임이 증명된다.

기저) $n=1:$ $L_1=2=L_0+1.$

귀납) $n=k(>1):$ 선 $0,\cdots,$선 $k-1$과 새 선 $k$를 평행하지 않게, 어떤 교차점도 공유하지 않게 배치한다면 $L_k=L_{k-1}+k. \square$

---

보조정리 1. $L_n\le L_{n-1}+n$

"선 $n$에 의해 영역의 수가 $k$개 증가" $\Leftrightarrow$ "선 $n$이 분할하는 기존 영역이 $k$개" $\Leftrightarrow$ "선 $n$이 기존의 선들과 $k-1$개의 서로 다른 점에서 교차"

두 선은 많아야 한 점에서 교차 $\Rightarrow$ 새로운 선은 많아야 $n-1$개의 서로 다른 점에서 교차

$\therefore k\le n$만큼 영역의 수 증가 $\Rightarrow$ $L_n\le L_{n-1}+n.$

$\square$

---

 

4. Well Ordering Principle

$S(\neq \varnothing) \in \mathbb N$에는 최소원이 존재한다. 즉, $\forall b\in S,\; \exists a\in S\text{ such that } a\le b$이다.

이 공리는 수학적 귀납법, 강한 수학적 귀납법과 동치이다. 또한 무한 강하법도 이 공리에서 파생된다. 주의할 점은 이 성질이 $\mathbb Z, \mathbb R$에서 성립하지 않는다는 것이다. 유한집합만을 생각하면 안되기 때문이다.

WOP는 "임의의 자연수 부분집합에는 무한히 감소하는 수열이 존재하지 않는다"라고도 표현할 수 있다. (무한 강하법)

 

참고로, WOP $\iff$ 수학적 귀납법 $\iff$ 강한 수학적 귀납법 $\iff$ 무한 강하법 이다.

 

Exercise 1

$\text{Theorem. }0<n<1$인 자연수 $n$은 존재하지 않는다.

집합 $S:=\{n|0<n<1\}$은 공집합이 아니라고 가정하자.

최소원 $m$에 대해, $0<m<1$이므로 $0<m^2<m<1$이다.

따라서 $m$보다 작은 $m^2$이 $S$의 원소이므로 모순이다. $\square$

---

Exercise 2

$\text{Theorem. }na\ge b(a,b\in \mathbb N)$인 자연수 $n$은 존재한다.

$\forall n\in \mathbb N, na<b$라고 가정하자.

$b-na>0$이므로 $b-na\in \mathbb N$이다.

$S:=\{b-na\}$라 하면, 최소원 $b-ma$에 대해 항상 더 작은 $b-(m+1)a$를 찾을 수 있으므로 가정에 모순이다. $\square$

---

Exercise 3

$\text{Theorem. }1$보다 큰 모든 자연수는 소인수를 갖는다.

집합 $S:=\{n|n(>1)$은 소인수를 갖지 않는다$\}$는 공집합이 아니라고 가정하자.

최소원 $m$에 대해, $m$은 소인수를 갖지 않으므로 $m$은 소수가 아니다. 따라서 $m$은 소수가 아닌 인수 $k(1<k<m)$를 갖는다.

소수가 아닌 인수 $k$는 $S$의 최소원 $m$보다 작으므로 $S$에 포함되지 않는다. 따라서 $k$는 소인수를 갖는다.

$k$의 소인수 $p$가 존재하므로 $p|k\wedge k|m\to p|m$이므로 가정에 모순이다. $\square$

---

Exercise 4

$\text{Theorem. }1$보다 큰 모든 자연수는 소수의 곱으로 표현할 수 있다.

nyam nyam

---