수학적 귀납법(Mathematical Induction) 톺아보기

여태까지 기초적인 증명을 다뤘지만, 이 증명 외에도 자주 쓰이는 증명이 있다. 수학적 귀납법이라고 불리는 이 증명 방식은, 고등학교에서도 다룰 만큼 유명한 증명방식이지만, 생각지도 못한 곳에서 자주 튀어나오는, 꼭 익혀둬야 할 증명방식이다.

 

---

수학적 귀납법이란?

수학적 귀납법은 다른 증명들과 마찬가지로, 명제가 사실임을 보이는 과정이다. 그 중에서도 특히, 자연수에서만 성립한다.

 

수학적 귀납법은 도미노와 비슷하다. 수학적 귀납법은 크게 2가지 과정으로 나뉘어 진다. 다음과 같은 명제가 있다고 하자.

 

∀n ∈ N P (n) : 자연수인 모든 n에 대하여, P(n)이 성립한다.

 

1. 이 명제가 가장 작은 조건(일반적으로 1)에서 성립함을 보인다. (즉, P(1))

2. 이 명제가 어떤 n에서 성립한다면, n+1에서 성립함을 보인다. (즉, P(n) => P(n+1))

 

이 2가지를 보인다면, P(1)이 성립하고 P(n) => P(n+1) 이므로 n=1이면 P(2)가 성립한다. 마찬가지로, n=2면 P(3)가 성립하고, 이 과정은 무한히 지속될 수 있기 때문에 모든 자연수에서 이 명제가 성립하게 된다.

 

수학적 귀납법이 자연수에서만 성립하는 이유는, 자연수가 아닌 집합은 1과 2사이에 무한히 많은 수가 존재하기 때문이다. (즉, 도미노가 성립할 수 없다.)

---

수학적 귀납법의 예시

말로만 해서는 잘 와닿지 않는다. 수학은 보통 듣고 배우기보다는 문제를 직접 풀어보면서 익히는 것이다. 수학적 귀납법을 사용해서 다음과 같은 명제를 증명해보자.

 

∀n ∈ N  1+3+5+⋅⋅⋅+(2n−1) = n^2 : 모든 자연수에 대해서, 1부터 n까지의 홀수의 합은 n^2이다.

 

1. 1에서 성립하는지 확인하기

 

1부터 1까지의 홀수의 합이 1^2과 동일한지 확인하면 된다. 이는 1 = 1^2으로 간단하게 확인할 수 있다.

 

2. P(n) => P(n+1) 보이기

 

P(n)이 성립한다고 가정하자. 즉, 1 + 3 + 5 + ... + (2n-1) = n^2이 성립한다.

 

여기서 양변에 2n+1을 더하자. 그럼 왼쪽 변은 1에서 n+1까지의 홀수의 합이 된다.

 

1 + 3 + 5 + ... + (2n-1) + (2n+1) = n^2 + (2n + 1)

 

오른쪽 항인 n^2 + 2n + 1 을 인수분해하면 (n+1)^2이 된다.

 

이는 P(n+1)일때의 오른쪽 항이다!

 

3. 수학적 귀납법

 

1과 2가 합쳐져서, 이 명제는 모든 자연수에 대해서 성립한다.

---

수학적 귀납법의 수학적인 정당성

수학적 귀납법은 페아노 공리에서 유도되는 성질입니다.

---

수학적 귀납법 잘 하는 법

수학적 귀납법을 잘 활용하기 위해서는 수학적 귀납법에서 흔히 쓰이는 기술들을 익혀야 하는데, 이는 이론서를 통달하는 것 보다 직접 많은 문제를 풀어보는게 좋다. 수학적 귀납법은 수열의 합이나 절대 부등식 등을 증명할때 많이 쓰이는데, 어떤 대상에 쓰느냐에 따라 필요한 사고법이 조금 다르다.

---