[이산수학] 강 귀납법 (Strong Induction)

1. 강 귀납법?

이산수학에서 "강 귀납법"은 귀납법(Induction)의 한 형태로, 수학적인 증명에 사용되는 중요한 방법 중 하나이다. 귀납법은 주로 어떤 명제나 성질이 모든 자연수 또는 양의 정수에 대해 참임을 증명하기 위해 사용된다.

 

 

2. 귀나법과의 차이

 기본 단계는 귀납법의 가본 단계와 같지만 일반 귀납법과 달리, 명제가 자연수 1부터 k까지 모든 자연수에 대해 참이라고 가정하고, 이를 기반으로 k+1에 대해 명제가 참임을 증명한다. 즉, 일반 귀납법에서는 k에 대한 가정이 하나였다면, 강 귀납법에서는 모든 1부터 k까지의 자연수에 대한 가정이 포함되는 것이다.

3. 강 귀나법의 예시

p(n)은 'n은 소수들의 곱으로 나타낼 수 있다" 라는 명제를 다루어보자.

• 초기 단계 (Base Case): n = 2인 경우, n은 소수 2 하나로 나타낼 수 있으므로 초기 단계에서 명제가 참임을 확인할 수 있다.
• 귀납 단계 (Inductive Step): 다음과 같이 가정해보자. "p(k)는 'k는 소수들의 곱으로 나타낼 수 있다'라는 명제를 참이다." 이 가정을 사용하여 p(k+1)이 참임을 보여줘야 하는데, 아래와 같이 2가지 경우를 우린 생각해야한다.
  • k가 소수인 경우: k 자체가 소수이므로 k는 1과 k를 곱해서 나타낼 수 있고, p(k+1)도 k+1이 소수인 경우 같은 이유로 참이다.
  • k가 소수가 아닌 경우: k는 소수들의 곱으로 나타낼 수 없는 합성수가 된다. 이 경우, k를 소인수 분해하면 k = ab (a, b는 정수)가 되는데, 여기서 a와 b는 모두 1보다 큰 정수이며, a와 b 모두 k보다 작을 것이다. 따라서 p(a)와 p(b)가 참이므로, p(k+1)도 참임을 확인할 수 있다.