수학적 귀납법 — 원리, 단계, 예제

수학적 귀납법은 어떤 명제가 특정 시작점 이후의 모든 정수에 대해 참임을 보이는 증명 방법입니다. 모든 $n \ge n_0$에 대해 어떤 주장을 증명하려면, 먼저 첫 번째 경우가 참임을 보이고, 이어서 한 정수에서 참이면 그다음 정수에서도 참이 된다는 것을 보여야 합니다.

이 두 부분이 모두 맞으면, 그 명제는 주어진 범위의 모든 정수에 대해 성립합니다. 이것이 핵심 아이디어입니다.

수학적 귀납법의 작동 원리

명제를 $P(n)$이라고 씁니다. 그러면 귀납법은 다음 구조를 가집니다.

1. 기초 단계를 증명합니다: $P(n_0)$가 참임을 보입니다.
2. 귀납 단계를 증명합니다: 임의의 정수 $k \ge n_0$에 대해 $P(k)$가 참이라고 가정했을 때, $P(k+1)$도 참임을 보입니다.

이 두 가지가 끝나면, 모든 정수 $n \ge n_0$에 대해 $P(n)$이 참이라고 결론낼 수 있습니다.

논리는 순차적으로 이어집니다. 기초 단계가 사슬을 시작하고, 귀납 단계가 그 사슬을 한 정수씩 앞으로 이어 가게 합니다.

왜 기초 단계와 귀납 단계가 모두 중요한가

기초 단계는 첫 번째 참인 명제를 제공합니다. 귀납 단계는 그 참이 한 정수에서 다음 정수로 전달된다는 뜻입니다.

따라서 $P(n_0)$가 참이면 $P(n_0 + 1)$도 참입니다. 그러면 $P(n_0 + 2)$도 참이고, 이런 식으로 계속 이어집니다. 귀납법은 시작점을 건너뛰지 않으며, 한 경우에서 다음 경우로 이어지는 연결도 생략하지 않습니다.

예제로 보기: 귀납법으로 합 공식 증명하기

대표적인 예는 다음 공식입니다.

$$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

이 식이 모든 정수 $n \ge 1$에 대해 성립함을 보이는 것입니다.

다음을 정의합시다.

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

기초 단계

$n = 1$일 때를 봅시다. 왼쪽은 $1$이고, 오른쪽은

$$\frac{1(1+1)}{2} = 1$$

입니다.

따라서 $P(1)$은 참입니다.

귀납 단계

어떤 임의의 정수 $k \ge 1$에 대해 $P(k)$가 참이라고 가정합시다. 즉,

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

입니다.

이제 $P(k+1)$을 증명합니다. $k+1$일 때의 왼쪽 식에서 시작하면,

$$1 + 2 + 3 + \cdots + k + (k+1)$$

이고, 귀납 가정을 이용하면

$$\frac{k(k+1)}{2} + (k+1)$$

가 됩니다.

여기서 $(k+1)$을 묶어 내면,

$$(k+1)\left(\frac{k}{2} + 1\right)$$

이고, 이를 정리하면

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

입니다.

이것은 정확히 $n = k+1$일 때의 공식입니다. 따라서 $P(k+1)$도 참입니다.

기초 단계와 귀납 단계가 모두 증명되었으므로, 이 공식은 모든 정수 $n \ge 1$에 대해 성립합니다.

수학적 귀납법은 언제 쓰는가

귀납법은 어떤 명제가 정수 매개변수에 의존하고, 각 경우가 이전 경우와 자연스럽게 연결될 때 유용합니다. 이런 상황은 합, 나눗셈 성질, 부등식, 점화식, 알고리즘 증명에서 자주 나타납니다.

먼저 올바른 시작값을 찾아야 합니다. 어떤 명제는 $n = 0$에서 시작하고, 어떤 것은 $n = 1$에서 시작하며, 더 큰 정수에서만 의미가 있는 경우도 있습니다.

그다음에는 다음으로 확인해야 할 경우가 무엇인지 봐야 합니다. 보통은 $k$에서 $k+1$로 가는 단계이지만, 명제가 짝수 정수에 대해서만 다뤄진다면 $k$에서 $k+2$로 가는 단계가 맞는 형태일 수 있습니다.

귀납법 증명에서 자주 하는 실수

기초 단계만 증명하는 경우

기초 단계는 첫 번째 값만 확인합니다. 그것만으로는 이후의 정수들에 대한 성립을 증명할 수 없습니다.

시작값을 잘못 잡는 경우

명제가 모든 $n \ge 2$에 대해 성립해야 한다면, $P(1)$만 증명해서는 도움이 되지 않습니다. 기초 단계는 실제 명제의 범위와 일치해야 합니다.

귀납 가정을 부주의하게 다루는 경우

귀납 단계에서는 성립 범위 안의 임의의 한 정수 $k$에 대해 $P(k)$를 가정합니다. 정리 전체가 이미 증명되었다고 가정하는 것은 아닙니다.

잘못된 다음 경우를 증명하는 경우

정리가 $k \to k+1$ 단계를 필요로 한다면, 왜 충분한지 설명하지 않는 한 다른 단계를 증명해서는 논증이 완성되지 않습니다.

유용한 확장: 강한 귀납법

때로는 $P(k+1)$을 증명할 때 $P(k)$만으로는 부족한 경우가 있습니다. 이런 상황에서는 강한 귀납법을 사용해 $k$까지의 모든 이전 경우를 가정한 뒤 다음 경우를 증명할 수 있습니다.

아이디어는 매우 가깝지만, 가정이 더 강합니다. 예를 들어 어떤 수를 더 작은 부분들로 나누는 방식에 의존하는 증명에서 유용합니다.

직접 해 보기

다음 명제를 생각해 봅시다.

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

이 식이 모든 정수 $n \ge 1$에 대해 성립함을, 같은 구조를 사용해 증명해 보세요. 먼저 기초 단계를 하고, 그다음 $k$에서 $k+1$로 가는 단계를 보이면 됩니다. 이 증명을 깔끔하게 쓸 수 있다면, 보통 귀납법의 감이 확실히 잡히게 됩니다.