강한 귀납법 (String Inductio)
강한 귀납법 : 모든 양의 정수 $n$에서 P(n)이 참임을 증명하기 위해 두 과정을 거쳐야 한다
- Basis Step : P(1)이 참임을 증명
- Inductive Step : 다음 조건문을 보이기
강한 귀납법은 수학적 귀납법의 두번째 원리, 또는 완전 귀납법(complete induction)으로도 불린다
예시 : 사다리
무한한 사다리의 첫번째와 두번째 사다리에 도달 할 수 있고, 한 개 사다리에 도달 할 수 있다면 두 개의 사다리에 도달 할 수 있다는 것을 알고 있다고 가정하자
모든 사다리의 단 도달할 수 있다는 것을 증명하라
풀이 : 강한 귀납법을 사용해 결과를 증명한다
- Basis Step : 첫번째 단에 도달 할 수 있다
- Induction Step
- 귀납적 가설은 $k \ge 2$인 경우 첫번째 k 번째 단에 도달할 수 있다는 것이다. 귀납적 가설에 의해 $k-1$번째 단에 도달할 수 있기 때문에, $k+1$ 단에 도달할 수 있다
- 그러므로, 모든 사다리의 단에 도달할 수 있다
어떤 형태의 귀납법을 사용하는 것이 좋은가?
항상 강력한 귀납법을 수학적 귀납법 대신 사용할 수 있으나, 수학적 귀납법을 쓰는 것이 더 간단하다면 굳이 강한 귀납법을 쓸 이유가 없다
사실 수학적 귀납법, 강한 귀납법, 정렬 정리(well-Ordering)의 원리는 모두 동일하다
필요에 따라 셋 중 하나의 방법을 쓰는 것이 적절하다
문제 1 : 산술의 기본 정리 증명
n이 1보다 큰 정수인 경우, n을 소수의 곱으로 쓸 수 있음을 증명하라
풀이
$P(n)$을 “n은 소수의 곱으로 쓸 수 있다”는 명제라 하자
Basis Step : $P(2)$는 소수이다. $2$ 자체로 소수이기 때문이다
Induction Step
- 귀납적 가설은 $2 \le j \le k$인 모든 정수 $j$에 대해 $j$가 참이라는 것이다
- 이 가정에서 $P(k+1)$이라는 것을 보이기 위해 두 경우를 고려해야 한다
- If $k+1$가 소수라면, $P(k+1)$은 참이다
- 반대로 $k+1$이 합성수이고, $2 \le a \le b < k+1$인 두 양의 정수 $a$와 $b$의 곱으로 쓸 수 있다
- 귀납적 가설에 따라 $a$와 $b$는 소수의 곱으로 쓸 수 있으므로 $k+1$도 해당 소수의 곱으로 쓸 수 있다
따라서 1보다 큰 모든 정수는 소수의 곱으로 쓸 수 있다는 것을 증명했다
문제 2-1 : 강한 귀납법을 이용한 증명
4센트, 5센트 우표만으로 12센트 이상의 모든 우표를 만들 수 있음을 증명해라
풀이
P(n) 을 4센트와 5센트 우표를 사용해 n센트의 우편 요금을 형성할 수 있다는 명제라고 하자
Basis Step : P(12), P(13), P(14), P(15) 에 대해
- P(12) : 4센트 우표 3장을 사용한다
- P(13) : 4센트 우표 2개와 5센트 우표 1개를 사용한다
- P(14) : 4센트 우표 하나와 5센트 우표 2개를 사용한다
- P(15) : 5센트 우표 3장을 사용한다
Inductive Step
- P(j)는 $k \le 15$일 때 $12 \le j \le k$ 에서 성립한다
- 귀납적 가설을 가정하면 $P(k+1)$ 이 성립한다는 것을 알 수 있다
- 귀납적 가설을 사용한면 $k-3 \ge 12$ 이므로, $P(k-3)$이 성립한다
- $k+1$센트 우표를 만드려면 $k-3$센트 우표에 4센트 우표를 추가하면 된다
따라서 $n \le 12$에 대해 $P(n)$은 성립한다
문제 2-2 : 수학적 귀납법을 이용한 증명
4센트, 5센트 우표만으로 12센트 이상의 모든 우표를 만들 수 있음을 증명해라
풀이
P(n) 을 4센트와 5센트 우표를 사용해 n센트의 우편 요금을 형성할 수 있다는 명제라고 하자
Basis Step
- P(12) : 4센트 우표 3장을 사용한다
Inductive Step
- 양의 정수 k에 대한 귀납적 가설 P(k)는 4센트와 5센트 우표를 사용해 k센트의 우편 요금을 만들 수 있다는 것이다
- $k \ge 12$인 경우 $P(k+1)$을 보여주기 위해 두가지 경우를 가정한다
- 4센트 우표가 하나 이상 사용된 경우, 5센트 우표로 교체해 총 $k+1$센트를 얻을 수 있다
- 4센트 우표가 사용되지 않고, 5센트 우표가 3개 이상 사용된 경우, 5센트 우표 3장을 4센트 우표 4장으로 대체해 총 $k+1$센트를 얻을 수 있다
그러므로, 모든 $n \ge 12$에 대해 $P(n)$이다
정렬된 특성 (Well-Ordering Property)
Well-ordering property : 비어있지 않은 모든 음이 아닌 정수 집합에는 최소 원소가 있다
well-ordering property은 양의 정수의 공리 중 하나이다
Well-ordering property은 일반화 할 수 있다
- 정의 : 모든 부분 집합이 최소 원소를 갖는다면 집합은 잘 정렬되었다 (well-ordered)
- $N$은 잘 정렬되었다 ($\le$에 대해)
- 사전적 순서를 사용하는 알파벳의 유한한 문자열 집합은 잘 정렬되었다
예제
잘 정렬된 속성을 사용해 $a$가 정수이고 $d$가 양의 정수인 경우 $0 \le r < d$인 고유한 정수 $q$, $r$이 존재하여 $a = dq + r$이 된다는 나눗셈 알고리즘을 증명하라
풀이
$S$를 $a - dq$ 형식의 음수가 아닌 양수의 집합이라고 하자, 여기서 $q$는 정수이다
이 집합은 $-dq$를 필요한 만큼 크게 만들 수 있으므로 비어있지 않다
- well-ordering 에 따라 $S$는 가장 작은 원소 $r = a - dq_0$을 가진다
- $r$은 음수가 아니다. 또한 $r < d$이어야 한다. 그렇지 않다면, 더 작은 원소가 존재할 것이다
즉, 다음과 같다
\[a - d(q_0+1) = a - dq_0 - d = r - d > 0\]그러므로, $0 \le r < d$인 정수 $q, r$가 존재한다