수학적 귀납법에서 참을 가정하는 이유

수학적 귀납법 단계

수학적 귀납법은 3단계로 구성된다.

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

를 증명하는 걸로 한다면

1. 기본

n은 1일 때

$$n=1, 1= \frac{1(2)}{2}$$

이므로 성립한다.

2. 가정

n이 k일 때
$$1+2+3+4\cdots+k = \frac{k(k+1)}{2}$$
가 참이라고 가정한다.

3. 증명

n이 k+1이면
$$1+2+3+4\cdots+k+k+1 = \frac{k(k+1)}{2}+k+1$$
$$\frac{k(k+1)}{2}+k+1 = \frac{(k+1)(k+2)}{2}$$
이므로 귀납적 추론에 의해
$$1+2+3+4\cdots+n = \frac{n(n+1)}{2}$$
가 성립하게된다.

왜 참이라고 가정할까?

수학적 귀납법을 보면 가정 단계에서 밑도끝도 없이 어떤 식이나 명제를 참이라고 가정한다. 항상 거기에 대한 의문이 있었다.

그 이유를 알기 위해서는 명제
$$P \rightarrow Q$$
의 수학적 의미를 알아야한다.

 

먼저 P가 참이면

1. P가 참 Q가 참이면 이 명제 전체는 참이 된다.
2. P가 참 Q가 거짓이면 이 명제 전체는 거짓이 된다.

하지만 P가 거짓이면

1. P가 거짓 Q가 참이면 이 명제 전체는 참이 된다.
2. P가 거짓 Q가 거짓이면 이 명제 전체는 참이 된다.

Q에 상관없이 P가 거짓이면 항상 명제는 참이 된다. 따라서 귀납 가정에서 참을 가정하는 이유는 P가 참일 때만 Q의 참과 거짓을 판별하면 되기 때문이다. 직관적으로 이해하기는 어렵지만 수학적으로 그렇다고 하기때문에 받아들여야 한다..