[이산 수학] 수학적 귀납법

수학적 귀납법

• 첫 번째 단계가 성립하고 `n` 번째 단계가 성립한다고 가정했을 때, `n + 1` 번째 단계로 성립함을 보이는 방식의 증명 방법을 수학적 귀납법이라고 한다.
• 수학적 귀납법은 0보다 크거나 같은 정수의 범위에서 발생하는 일정한 규칙을 증명하는 데 유용하다.

 

수학적 귀납법(Mathematical Induction)

0보다 크거나 같은 정수 범위에서 발생하는 일정한 규칙을 나타내는 명제 `P(n)` 이 성립함을 증명하는 방법

 

• 수학적 귀납법은 다음 세 단계로 증명한다.

① 기본 가정 : 명제의 논의 영역 `D` 의 첫 번째 값 `d` 에 대하여, `P(d)` 가 참(T)임을 보인다.
② 귀납 가정 : 논의 영역에 속하는 임의의 값 `k` 에 대하여, `P(k)` 가 참(T)이라고 가정한다.
③ 귀납 증명 : 기본 가정과 귀납 가정을 이용해 논의 영역에 속하는 값 `k + 1` 에 대하여, `P(k + 1)` 이 참(T)임을 증명한다.

 

예 : 수학적 귀납법을 이용하여 `n ≥ 1` 인 자연수 `n` 에 대하여, $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ 이 성립하는지 증명하기

• 제시된 논의 영역 `D` 와 명제 `P(n)` 은 다음과 같다.

$$D = \{ n | n ≥ 1, \; n ∈ N \}$$
$$P(n) : 1 + 2 + \cdots + n = \frac{n(n +1)}{2}$$

① 기본 가정 : 논의 영역 `D` 의 첫 번째 값은 `1` 이므로, `P(1)` 이 참(T)인지 확인한다.

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

∴ P(1)이 참(T)이다.

② 귀납 가정 : 논의 영역 `D` 에 속하는 임의의 값 `k` 에 대하여, 다음이 참(T)이라고 가정한다.

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

③ 귀납 증명 : 기본 가정과 귀납 가정을 이용해 논의 영역 `D` 에 속하는 임의의 값 `k + 1` 에 대하여, `P(k + 1)` 이 참(T)인지 증명한다.

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

귀납 가정에서 `P(k)` 가 참(T)이라고 가정하였으므로 다음이 성립한다.

$P(k + 1) : 1 + 2 + \cdots + k + (k + 1) $  $= P(k) + (k + 1)$ $\displaystyle = \frac{k(k + 1)}{2} + (k + 1)$ $\displaystyle = \frac{k(k + 1) + 2(k + 1)}{2}$ $\displaystyle = \frac{k^{2} + k + 2k + 2}{2}$ $\displaystyle = \frac{k^{2} + 3k + 2}{2}$ $\displaystyle = \frac{(k + 1)(k + 2)}{2}$ $\displaystyle = \frac{(k + 1)\{(k + 1) +1\} }{2}$

∴ `P(k + 1)` 이 참(T)이다.

• ∴ `n ≥ 1` 인 자연수 `n` 에 대하여, $\displaystyle 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ 이 성립한다.