수학적 귀납법

\(1 + 3 + 5 + \cdots + (2n - 1) = n^2\)은 \(n = 1, 2, 3, \ldots, 100\)까지 모두 확인해 보니 맞았다. 그렇다고 \(n = 101\)에서도 맞는다고 할 수 있을까? 자연수는 끝없이 많은데, 유한한 단계만으로 '모든 자연수에서 참'임을 보이려면 어떻게 해야 할까?

쓰러뜨린 단계

\(k \to k + 1\)이 끊긴 자리

3.7.1도미노처럼 이어서 증명하기

자연수 \(n\)에 대한 명제 \(p(n)\)이 모든 자연수에서 참임을 보이고 싶다. 하나씩 확인해서는 끝이 없다. 그래서 두 가지만 보인다. 먼저 \(n = 1\)일 때 참이다. 다음으로, 어떤 자연수 \(k\)에서 참이라고 가정하면 \(k + 1\)에서도 참이다.

이 두 가지가 보이면, 1에서 참이므로 2에서 참이고, 2에서 참이므로 3에서 참이며, 이렇게 끝없이 이어진다. 그림 1의 도미노와 같다. 첫 도미노를 쓰러뜨리고, 모든 도미노가 바로 다음 도미노를 쓰러뜨리도록 세워 두었다면 결국 모두 쓰러진다.

두 단계는 모두 필요하다. 그림 1에서 이음이 끊긴 자리를 만들어 보면, 첫 도미노가 쓰러져도 그 자리 뒤로는 전달되지 않는다. 반대로 (ⅱ)가 성립해도 (ⅰ)이 없으면 아무것도 시작되지 않는다.¹

3.7.2처음 질문 증명하기

(ⅰ) \(n = 1\)이면 좌변은 1, 우변은 \(1^2 = 1\)이므로 성립한다.

(ⅱ) \(n = k\)일 때 \(1 + 3 + \cdots + (2k - 1) = k^2\)이 성립한다고 가정하자. 양변에 다음 홀수 \(2(k + 1) - 1 = 2k + 1\)을 더하면, 좌변은 \(n = k + 1\)일 때의 좌변이 되고, 우변은 \(k^2 + 2k + 1 = (k + 1)^2\)이 된다. 따라서 \(n = k + 1\)일 때도 성립한다.

(ⅰ), (ⅱ)에 따라 모든 자연수 \(n\)에 대하여 \(1 + 3 + \cdots + (2n - 1) = n^2\)이다.

3.7.3예제 풀이

(ⅰ) \(n = 1\)이면 \(4 - 1 = 3\)이므로 3의 배수이다.

(ⅱ) \(n = k\)일 때 \(4^k - 1 = 3m\)(\(m\)은 자연수)이라 가정하자. 그러면 \(4^{k+1} - 1 = 4 \times 4^k - 1 = 4(3m + 1) - 1 = 12m + 3 = 3(4m + 1)\)이다. 따라서 \(n = k + 1\)일 때도 3의 배수이다.

(ⅰ), (ⅱ)에 따라 모든 자연수 \(n\)에 대하여 \(4^n - 1\)은 3의 배수이다.

(ⅱ)에서 길을 연 것은 \(4^{k+1}\)을 \(4^k\)으로 나타내 가정을 쓸 수 있게 만든 한 줄이다. 가정을 어디에 넣을지 찾는 것이 귀납법 증명의 대부분이다. 아래 탐구 카드에서 도미노의 이음을 끊어 보고, \(P(k)\)에서 \(P(k + 1)\)로 건너가는 단계를 직접 따라가 보자.

1. '\(n^2 + n + 41\)은 소수이다'는 \(n = 1\)부터 39까지 참이지만 \(n = 40\)에서 \(40^2 + 40 + 41 = 41^2\)이 되어 거짓이다. 많은 경우를 확인하는 것만으로는 증명이 되지 않는다.