Induction I

2010.10.17.

논리를 증명하는데 있어서 자주 언급되는 것들로는 연역법과 귀납법이 있습니다. 위키피디아에 의하면 연역법(deductive reasoning)은 이미 알고 있는 사실로부터 새로운 사실을 추론하는 것이다라고 되어 있습니다. 그에 비해서 귀납법(Induction)은 경험적 근거를 바탕으로 한 사실을 말합니다. 연역법은 논리에 있어서 잘못된 추론이 있을 수 없지만, 귀납법은 잘못된 추론이 발생할 수 있습니다.

현대사회에서 귀납법을 이용하여 많은 사실을 이끌어내기는 하지만, 이것이 100% 올바른 답이라고 할 수 없습니다. 사회적 현상에서 특히 논란을 많이 발생시킵니다.

이 책에서는 일반적인 귀납법이 아닌 수학적 귀납법(Mathematical Induction)을 설명합니다. 수학적 귀납법은 앞에서도 잠깐 설명했듯이 자연수의 완비성을 근거로 추론을 합니다. 그렇지만 귀납법과는 달리 수학적 귀납법은 오류가 발생할 수 없습니다.

P(n)이라는 명제가 있다고 할 때, 모든 자연수 n에 대하여 P(n)이 참이라고 증명을 하고자 합니다. 이 증명을 수학적 귀납법을 이용한다면, 다음과 같은 형식을 통해서 증명합니다.

a) P(1) 이 참임을 보인다.

b) P(1), P(2), P(3), ..., P(n) 이 모두 참이라고 가정한다.

c) b) 가정을 토대로 P(n+1)이 참임을 보인다.

a) 는 초기조건입니다. 초기조건은 문제에 따라서 다소 달라질 수 있습니다만, 일반적으로 첫 번째 항이 초기조건이 됩니다. b)는 귀납법을 위한 가정부분입니다. c)는 b)의 가정을 근거로 P(n+1)이 참임을 증명하는 것입니다.

이것이 어떻게 동작할 수 있는가 의아해할 수 있겠지만, 이것은 아주 잘 동작합니다.

앞의 증명 방법을 통해서 모든 자연수 n에 대하여 P(n)이 참이라고 결론내렸다고 합시다.

그러면 과연 정말 이것이 맞는 것인가 의심을 할 수 있습니다.

P(3)을 예로 듭시다.

P(1), P(2)가 참이라면 P(3)은 앞의 증명에 의해서 참입니다.

그런데 P(2)가 참인지 아닌지 알 수 없습니다.

P(1)이 참이라면 P(2)는 앞의 증명에 의해서 참입니다.

P(1)은 a)에 의해서 증명되었기 때문에 P(2)도 참입니다.

결국 n이 어떤 수이던, 이런 식으로 반복하면 앞의 귀납법에 의해서 모두 참임을 밝힐 수 있습니다.

수학적 귀납법을 알고리즘으로 증명하는 것은 어떨까요?

Algorithm I 주어진 자연수 n에 대하여 알고리즘이 P(n)이 참이라는 증명을 출력한다.

I1. k ← 1, a)에 의해서 P(1)은 참이다.

I2. k = n 이라면 알고리즘을 종료하고, 원하는 증명이 출력된다.

I3. b)에 의해서 P(k+1) 은 참이다.

I4. k ← k+1

I5. I2 로 돌아간다.

이 알고리즘을 통과하면 임의의 자연수 n에 대해서 참임을 밝힐 수가 있습니다.

수학적 귀납법은 일반 귀납법과 달리 단순하게 추측하는 것이 아닙니다. 확실한 증명을 하는 것이지요. 수학사에서 잘못된 추측은 상당히 많았습니다. 예를 들어서 피보나치 소수가 있습니다. 당시에는 컴퓨터가 없어서 일일이 사람의 손으로 계산해야 했지요. 그래서 모든 피보나치 소수가 올바른지 아닌지를 판단하는 것이 어려웠습니다. 또한 페르마의 소수도 비슷합니다. 프랑스 수학자 페르마가 이런 꼴은 항상 소수가 될 것이다라고 예측했지만, 실제 그 소수는 현재 5개가 유일합니다. 골드바흐의 추측 역시 아직까지 증명되지 않은 추측입니다. 골드바흐의 추측은 증명되지 않았지만, 대부분의 수학자들은 해당 추측이 맞을 것이다라고 생각합니다.

1부터 시작하는 홀수의 합은 항상 제곱수이다라는 것을 증명하고자 합니다. 수학에서 증명하는 방법은 여러 가지가 존재합니다. 우선 귀납법으로 생각을 해보도록 합니다.

\[ 1 = 1^{2} , 1 + 3 = 4 = 2^{2}, 1 + 3 + 5 = 9 = 3^{2}, ... \]

이런 경험적 사실로부터 우리는 1부터 시작하는 홀수의 합은 제곱수이다라고 추측할 수 있습니다. 여기까지는 일반적인 귀납법입니다.

자 다음으로는 이것이 정말 맞는지 증명하는 것입니다.

 

\[ Proof. 1 + 3 + 5 + 7 + ... + 2n-3 + 2n-1 = n^{2} \]

\[ \begin{align} i) &~n=1 \\ &~1 = 1^{2} \\ ii) &~\text{Assume that} ~1 + 3 + 5 + 7 + .. + 2k-1 = k^{2} \\ iii) &~n=k+1 \\ &~1+3+5+7+...+2k-1+2k+1 = k^{2}+2k+1 = (k+1)^{2} \end{align} \\ Q.E.D. \]

 

이렇게 함으로써 우리는 항상 이 식이 성립함을 증명할 수 있습니다.

그런데 알고리즘에서 왜 갑자기 밑도 끝도 없이 수학적 귀납법이 나오는가 의문을 가질 수 있겠죠. 수학적 귀납법은 알고리즘에서 올바른지 아닌지 검사하는데 많이 사용됩니다. 또한 알고리즘의 효율성을 평가하는 데에도 수학적 귀납법이 사용됩니다.