수학적 귀납법
- Basic Step : Show P(1) is true
- Inductive Step : 모든 양의 정수 k에 대해 P(k) → P(k+1)이 참임을 보인다
술어논리로 정리하면 다음과 같다
\[[P(1)∧∀k(P(k)→P(k+1))] → ∀nP(n)\]정의역은 양의 정수의 집합이다
수학적 귀납법의 양의 정수 집합의 비어있지 않은 모든 하위 집합이 최소 요소를 갖는다는 well-ordering property(잘 정렬된 속성) 때문에 유효하다
Proof
- P(1)이 성립하고 모든 양의 정수 K에 대해 $P(k) → P(k+1)$이 참이라 가정하자
- P(n)이 거짓인 양의 정수 n이 하나 있다고 가정하자. 그럼, P(n)이 거짓인 양의 정수 집합 S는 비어있지 않다
- 잘 정렬된 속성에 따라 S는 m이라는 최소 요소를 가진다
- P(1)이 성립하므로, $m \ne 1$ 이다
- m은 양수이고 1보다 크므로, m-1은 양의 정수여야 한다. $P(m-1)$은 $m-1 < m$으므로 S에 있지 않으므로, P(m-1)은 참이다
- 그러나 모든 양의 정수 k에 대해 $P(k)→P(k+1)$이 성립하므로 P(m)도 참이어야 하며 이는 P(m)이 거짓이라는 것과 모순된다$
- 따라서 모든 P(n)은 모든 양의정수 n에 대해 참이어야 한다
문제 1 : 첫 n개의 양의 정수의 합
Show that $\sum_{k=1}^{n}k = \frac{n(n+1)}{2}$
풀이
Basis Step : P(1)은 참이다 : $\frac{1(1+1)}{2} = 1$
Inductive Step : P(k)에 대해 가정하자
\[\sum_{i=1}^{k+1}i = \sum_{i=1}^{k}i + (k+1) = \frac{k(k+1)}{2} + (k+1)\] \[= (\frac{k}{2} + 1)(k+1)\] \[= \frac{(k+1)(k+2)}{2}\]$P(n)$이 모든 양의 정수 n에 대해 유효하다
문제 2 : 첫 n개의 홀수의 합
첫 n개의 홀수인 정수의 합에 대한 공식에 대한 가설을 새우고 증명하라
풀이
다음을 알수 있다
- $1 = 1$
- $1+3 = 4$
- $1+3+5 = 9$
- $1+3+5+7 = 16$
- $1+3+5+7+9 = 25$
첫 n개의 홀수의 합이 n^2이라고 가정할 수 있다
\[1+3+ \cdots + (2n-1) = n^2\]이 가설을 수학적 귀납법을 통해 증명한다
Basis Step : P(1)은 참이다. $1 = 1^2$
Inductive Step : 모든 양의 정수 k에 대해 $P(k) → P(k+1)가 참임을 증명
$\sum_{i=1}^{k}(2i-1) = k^2$ 라 가정하자. 그럼,
\[\sum_{i=1}^{k+1}(2i-1) = \sum_{i=1}^{k}(2i-1) + (2k+1)= k^2 + 2k + 1 = (k+1)^2\]따라서 $P(k)→P(k+1)$이 참임을 보였다
그러므로, 모든 첫 n개의 홀수의 합은 $n^2$이다
문제 3 : $n < 2^n$ 증명
모든 양의 정수 $n$에서 $n < 2^n$ 임을 수학적 귀납법을 이용해 증명하라
풀이
$P(n)$을 $n < 2^n$라 하자
Basis Step : $P(1)$은 참이다 : $1 < 2^1$
Inductive Step
- P(k)가 참이라 가정하자
- P(k+1)가 참임을 보이기 위해 다음과 같이
그러므로 모든 양의 정수 $n$에 대해 $n < 2^n$를 만족한다. QED
문제 4 : $2^n < n!$ 증명
정수 $n \ge 4$에서 $2^n < n!$ 임을 수학적 귀납법을 이용해 증명하라
풀이
$P(n)$을 $2^n < n!$이라고 하자
Basis Step : P(4)는 참이다 : $4^2 = 16 < 4! = 24$
Inductive Step
- P(k)를 참이라 가정하자
- P(k+1)를 보이기 위해
따라서 정수 $n \ge 4$에서 $2^n < n!$ 을 만족한다
문제 5 : 나누기 증명
모든 양의 정수 n에 대해 $n^3-n$이 3으로 나누어질 수 있음을 수학적 귀납법을 이용해 증명하라
풀이
$P(n)$을 $n^3-n$ divisible by 3이라고 하자
Basis Step : P(1)은 참이다 : $1^3-3 = 0$은 3으로 나누어질 수 있다
Inductive Step
- P(k) 가 참이라고 가정하자
- P(k+1)를 보이기위한 방법은 다음과 같다
이 귀납적 가설에 의해 $(k^3-k)$은 3으로 나누어질 수 있으며, $3(k^2+k)$ 또한 나누어질 수 있다. 따라서 $(k+1)^3 - (k+1)$ 은 3으로 나누어질 수 있다
그러므로 모든 양의 정수 $n$에 대해 $n^3-n$은 3으로 나누어질 수 있다. (Q.E.D.)
문제 6 : 유한한 집합의 부분집합의 크기
WIP_DN_08_15
문제 7 : 체크보드 문제
WIP_DN_08_16
수학적 귀납식의 잘못된 가정
예시
P(n)를 평면에 있는 n개의 선 집합중 두개가 평행하지 않은 모든 집합이 공통점에서 만난다고 가정한다
Basis Step : 평면에서 평행하지 않은 두 선이 공통점에서 만나기 때문에 P(2)는 참이다
Inductive Step
- $k \ge 2$에 대해 $P(k)$가 참이라고 가정한다
- 즉, 평면에 있는 모든 $k$개의 선이 공통 점에서 만난다
문제점
WIP_DN_08_18
가이드라인 : 수학적 귀납법
