수학적 귀납법

‘모든 자연수 $n$에 대해’라는 무한히 많은 명제를 단 두 단계로 증명하는 방법이다. 첫 번째가 참이고, 하나가 참이면 다음 것도 참이라는 것을 보이면 된다.

핵심 개념

  • 수학적 귀납법: (1) $P(1)$이 참, (2) $P(k)$가 참이면 $P(k+1)$이 참 → 모든 $n\ge1$에서 $P(n)$이 참
  • 강한 귀납법: (2) 대신 ‘$P(1),\dots,P(k)$가 모두 참이면 $P(k+1)$이 참’
  • 정렬성 원리: 공집합이 아닌 자연수의 집합에는 가장 작은 원소가 있다.
차례로 넘어지는 도미노
첫 도미노와 ‘앞이 넘어지면 뒤도 넘어진다’만으로 모두 넘어진다

핵심 정리

수학적 귀납법은 정렬성 원리로 정당화된다.

증명 보기

(1), (2)가 성립하는데 어떤 $n$에서 $P(n)$이 거짓이라고 가정하자. 거짓인 $n$들의 집합은 공집합이 아니므로 정렬성 원리에 의해 가장 작은 원소 $m$이 있다. (1)에 의해 $m\neq1$이므로 $m-1\ge1$이고, $m$이 가장 작은 거짓이므로 $P(m-1)$은 참이다. 그러면 (2)에 의해 $P(m)$도 참이 되어 모순이다. $\blacksquare$

예제

$1+2+\cdots+n=\frac{n(n+1)}{2}$. $n=1$이면 $1=1$. $k$일 때 성립하면

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

이므로 $k+1$일 때도 성립한다.

잘못된 귀납법 (모든 말은 같은 색?): ‘$n$마리 말은 모두 같은 색’을 $k\to k+1$에서 ‘처음 $k$마리와 마지막 $k$마리가 각각 같은 색이고 겹치므로 모두 같다’로 증명하면, $k=1\to2$에서 두 무리가 겹치지 않아 논리가 무너진다. 귀납 단계는 모든 $k$에서 성립해야 한다.

확인 문제

모든 자연수 $n$에 대해 $4^n-1$은 $3$의 배수임을 귀납법으로 보이시오.

풀이 보기

$n=1$이면 $3$이다. $4^k-1=3m$이라 하면 $4^{k+1}-1=4\cdot4^k-1=4(3m+1)-1=12m+3=3(4m+1)$이다.

정리

  • 시작 단계 + 귀납 단계 = 모든 자연수
  • 귀납 단계는 모든 $k$에서 빈틈없이 성립해야 한다.
알림: 보호된 콘텐츠입니다.