제 4 절 수학적 귀납법
모든 자연수에 대해 성립하는 명제를 증명할 때는 수학적 귀납법을 사용할 수 있다.
정 리 2.23 [수학적 귀납법(mathematical induction)]
자연수 n에 대한 명제함수 P (n)가 아래 두가지 조건을 만족한다고 하자.
(1) P (1)이 성립한다.
(2) 임의의 자연수 k에 대해 P (k) =⇒ P (k + 1).
그러면 P (n)은 모든 자연수 n에 대해 성립한다.
위 정리는 자연수에 대한 페아노(Peano) 공리계에서 부터 얻어진다.
[[ 예 ]] 2.24 수학적 귀납법을 사용하여 아래 공식을 증명하여라.
1 + 2 + 3 +· · · + n = n(n + 1) 2 증명. 먼저 P (n)을 명제
1 + 2 + 3 +· · · + n = n(n + 1) 2 이라 하자.
(1) P (1)이 성립한다. 왜냐하면
1 = (1· 2) 2 (2) 이제 P (k)가 성립한다고 가정하자. 그러면
1 + 2 + 3 +· · · + k = k(k + 1) 2
이다. 양변에 k + 1을 더해주면
1 + 2 + 3 +· · · + k + (k + 1) = k(k + 1)
2 + (k + 1) (2.1)
= k(k + 1)
2 + 2(k + 1)
2 (2.2)
= (k + 2)(k + 1)
2 (2.3)
= (k + 1)(k + 2)
2 (2.4)
이식은 P (k + 1)이 성립한다는 것을 보여준다.
(1)과 (2)에 의해 수학적 귀납법의 조건을 만족시킨다는 것을 알 수 있다. 따 라서 모든 자연수 n에 대해 명제 P (n)이 성립한다. 즉, 모든 자연수 n에 대 해
1 + 2 + 3 +· · · + n = n(n + 1) 2
이 성립한다.
