[기초 정수론] 01. 수학적 귀납법

1. 수학적 귀납법

1) 수론: 정수 or 양의 정수들의 성질
2) 고대 그리스 시기 수를 양의 정수 뿐이라 여겼음.
3) 크로네커(Leopold Kronecker): 신은 자연수를 창조했고, 나머지는 인간의 창조물이다.
4) 정렬성 원리(Well Ordering Principle)
 공집합이 아니고, 음이 아닌 정수들을 원소로 갖는 모든 집합 S는 최소 원소를 가지고 있다. 다시 말해 S는 S에 속하는 모든  b에 대해 a≤b를 만족하는 a를 포함한다. 
5) 아르키메데스 원리
 a와 b가 양의 정수이면, na≥b를 만족하는 양의 정수 n이 존재한다. 
 
Proof.
위 정리가 참이 아니라고 가정하자. 그러면 a,b에 대해 모든 양의 정수 n은 na<b를 만족한다. 그러면 집합

S={b-na | n은 양의 정수}

는 양의 정수로만 이루어진다. 정렬성의 원리에 의해서 S는 최소 원소, 이를테면 b-ma를 가질 것이다. S가 이런 형태로 이루어진 모든 정수를 포함하므로, b-(m+1)a 또한 S에 포함된다. 또한, 우리는 

b-(m+1)a=(b-ma)-a<b-ma

즉, b-ma가 S의 최소 원소라는 선택에 모순되는 결과를 얻는다. 이것은 처음의 가정인 아르키메데스 원리가 성립하지 않는다는 것이 모순임을 알 수 있다. 결국, 이 원리는 참임이 증명된다. 
 
6) 유한 귀납법의 기본원리
양의 정수들로 이루어진 집합 S가 다음 두 가지 성질을 만족한다고 하자. 
(a) 정수 1은 S에 속한다.  =>종종 귀납법의 기저(basis for the induction)
(b) 정수 k가 S에 속하면, 다음 정수 k+1또한 S에 속한다.  =>귀납단계(induction step)
그러면 S는 모든 양의 정수를 가진다. 
*귀납단계를 수행하는 동안 만들어지는 가정들을 귀납추측(induction hypotheses)이라 한다. 
 
Proof. 
집합 T를 S에 속하지 않는 모든 양의 정수라 하고, T가 공집합이 아니라 하자. 정렬성의 원리에 의해 T는 최소 원소를 포함한다. 그 수를 a라 하자.  1이 S에 속하므로, a>1, 또한 0<a-1<a. a가 T의 최소 원소이기 때문에 a-1은 T에 속하지 않는다. 즉, a-1은 S에 속한다. 가정에 의해 S는 (a-1)+1=a를 가져야 한다. 이것은 a가 T에 들어간다는 가정에 모순이다. 따라서 T가 공집합이라는 것을 알 수 있고,  S는 모든 양의 정수를 포함한다는 결론을 얻는다. 
 
예제.

 

2. 유한 귀납법의 기본원리 응용

1) 귀납단계의 타당성은 증명을 하려는 명제의 사실성 여부에 반드시 의존하지는 않는다. 

2) 첫 번째 버전처럼 두 번째 버전 역시 실제로 모든 양의 정수로 이루어진 특정한 양의 정수 집합을 보장하는 두 가지 조건을 제시한다. (a)는 그대로 유지하고, (b)는 (b')로 대치한다. 
 (b') 만약 k가 1, 2, ..., k가 모두 S에 속하도록 하는 양의 정수라면, k+1은 S에 속한다. 
 

3. 정의의 방법으로 사용되는 수학적 귀납법

1) n!
(a) 1!=1,
(b) 자연수 n>1에 대해 n!=n*(n-1)!
 
n!=n*(n-1)...3*2*1
0!=1
 
📒 뤼까 수열(Lucas sequence)