[수학의 증명] 수학적 귀납법 Mathematical Induction

앞서 수학은 크게 두 가지의 증명방식: 연역과 귀납으로 이뤄진다고 하였다. 이번 글에서는 그 중 하나인 귀납법에 대해 다뤄보겠다. 

 

수학적 귀납법 Mathematical Induction은 수학의 증명 방법 중 하나이며 어떤 명제가 모든 자연수 $\mathbb{N}$에 대해 성립함을 보이려 할 때 증명 방법으로서 사용된다. 

 

수학적 귀납법에는 여러 종류가 있는데 우선 가장 기본적인 형태를 살펴본 후 변형 형태까지 살펴보겠다. 

 

 

수학적 귀납법을 증명하기 전에 살펴볼 공리가 있다. 

 

 

Well Ordering Principle

well ordering principle ( Introduction to Real Analysis 4th edition )

 

쉽게 말해 모든 공집합이 아닌 자연수 집합 $\mathbb{N}$의 부분집합은 최소값인 원소를 가진다는 뜻이다. 

 

 

 

 

수학적 귀납법 

수학적 귀납법 ( Introduction to Real Analysis 4th edition )

 

수학적 귀납법은 공리가 아닌 정리이다. 이 말은 이 방법 역시 증명이 필요하다는 뜻이다. 

 

증명은 귀류법을 통해 진행한다. 수학적 귀납법이 내리는 결론인 $S = \mathbb{N}$을 부정하여 $S \ne \mathbb{N}$라고 가정하여 모순을 이끌어냄으로써 수학적 귀납법이 참임을 보이게 된다. 그러면 증명을 정리해보겠다. 

 

증명

 

우선 결론인 $S = \mathbb{N}$ 을 부정하여 $S \ne \mathbb{N}$ 라고 하자. 그러면 집합 $\mathbb{N} \setminus S$는 공집합이 아니다. 따라서 Well-Ordering Principle에 의해서 집합 $\mathbb{N} \setminus S$ 에는 최소 원소 $m$이 존재한다. 

 

주어진 가정에서 $1 \in S$ 로부터   $1 \notin \mathbb{N} \setminus S$ 이고  최소 원소 $m > 1$ 이다. 

그러면 $m-1 > 0$이며  $m-1 \in \mathbb{N}$ 이고  $m-1 \notin \mathbb{N} \setminus S$ 이므로  $m-1 \in S$ 이다. 

 

주어진 두 번째 (2) 가정으로부터 $m-1 \in S$ 이면 $m \in S$이다. 그런데 이는 $m \notin S$라는 것에 모순이다. 

 

따라서 $S = \mathbb{N}$ 이고 수학적 귀납법은 성립한다. 

 

 

 

 

명제 형태의 수학적 귀납법 

 

다음과 같이 명제 형태로도 수학적 귀납법을 표현할 수 있다. 

 

 

 

 

 

 

마무리

수학 증명에서 가장 기본적인 귀납법을 다뤘다. 추후 이 글에 변형 버전의 귀납법들을 추가해 올리도록 하겠다. 

 

 

 

 

 

 

References

 

* Introduction to Real Analysis 4th edition 

 

 

https://jjycjnmath.tistory.com/99

수학적 귀납법 (Mathematical Induction) - 1. 수학적 귀납법과 다양한 변형