Updated at 2021.5.25
Updated at 2019.12.11
수학적 증명 방법 (귀류법 및 귀납법)
수학에서 증명(Proof)이란 어떤 명제가 참이라는 것을 보여주는 것이다. 가장 기본적인 증명은 주어진 명제 또는 사실들의 다른 표현을 찾는 것이다. 이를 직접 증명(Direct Proof) 또는 연역(演繹)적 증명(Deductive Proof)이라 부른다. 이것은 별 재미도 없고 흥미롭지도 않다. 수학 시간에 맨처음 접했을 때 감탄사를 연발했던 증명법이 두가지 있었다.
| 귀류법 | 수학적 귀납법 |
|---|---|
| Proof by contradiction | Proof by mathematical induction |
| 歸謬: 오류로 귀착된다 | 歸納: 납득하게 된다 |
| 예) 제곱근 2 | 예) 홀수 합의 공식 증명 |
우리말 용어가 어려워 헤깔리지만 수학을 배울 때 꼭 기억해 두어야 할 내용이다. 인류 유산의 총아라고 할 수 있다. 생각하는 법을 알려 주기 때문이다. 내가 배우지 않고 혼자서 생각했다면 이것을 깨우칠 수 있었을까?
귀류법: 루트2의 무리수 증명
유리수가 아닌 것을 무리수라고 한다. 그런데 유리수란 무엇인가? 그 정의를 알아야 한다.
❝정수와 정수의 나누기 형태, 즉 정수의 비로 나타낼 수 있는 수가 유리수이다.
루트2를 유리수라고 가정 해보자. 그러면 서로소(1 이외의 공약수가 없음, 즉 서로 나눠지지 않음)인 두 정수 \(m, n\) 이 존재하여 다음과 같은 수식으로 나타낼 수 있다.
\begin{align}\sqrt 2 = \frac{m}{n}\end{align}
식(1)의 양변을 제곱하여 정리하면
\begin{align}2n^2 = m^2\end{align}
식(2)에서 좌변이 짝수이므로 우변도 짝수이다. 제곱을 해서 짝수가 되는 수는 짝수 밖에 없으므로
\begin{align}m = 2k\end{align}
식(3)을 식(2)에 넣고 정리하면
\begin{align}n^2 = 2k^2\end{align}
식(4)에 따르면 \(n\) 도 짝수이다. 식(3)에서 \(m\) 이 짝수라고 하였는데, \(n\) 도 짝수이므로 \(m\) 과 \(n\) 은 서로소가 아니다. 이는 처음에 했던 가정과 배치된다. 즉 모순이다. 따라서 루트2는 유리수가 아닌 무리수이다. 증명이 끝났다.
정리해보자.
제곱근 2가 유리수라고 가정하고 그것이 모순됨을 증명하여 유리수가 아님을 알게되는 것이다. 어떤 명제가 거짓이라고 가정하면 모순이 발생한다는 것을 증명하여 그 명제가 참임을 증명하는 것이 바로 귀류법이다. 가정이 오류로 귀착된다는 것이다.
수학적 귀납법: 홀수 합의 공식 증명
무수히 많은 상황에 대해 참임을 증명해야 하는 경우, 각각을 모두 헤아려 볼 수 없다. 수학적으로 순서가 있으면(순차적이면) 아래와 같은 두 단계를 거치면 모든 상황에도 성립함을 납득시킬 수 있다.
- 맨 처음 것(\(n=1\))에 대한 증명
- \(n\) 에 대해 성립 가정하고, \(n+1\) 일 때 증명
위와 같은 증명법을 수학적 귀납법이라고 한다. 다음은 홀수의 합에 대한 공식이다.
\begin{align}1 + 3 + 5 + \cdots + (2n-1) = n^2\end{align}
몇 가지 홀수에 대해 헤아려보면 알겠지만, 위의 공식은 맞는 것 같다. 그런데 홀수의 개수가 무한히 많은데, 그 많은 경우를 어떻게 헤아려 해보겠는가?
\(n = 1\) 일 때를 보면 아래 수식과 같이 참임을 쉽게 알 수 있다.
\begin{align}n^2 = 1^2 = 2n - 1 = 2\times 1 -1\end{align}
\(n = k\) 일 때 참이라고 가정해보자.
\begin{align}1 + 3 + 5 + \cdots + (2k-1) = k^2\end{align}
식(7)의 양변에 \(2k + 1\) 을 더하면 아래와 같은 수식이 되어 \(n = k + 1\) 일 때도 참이 됨을 알 수 있다.
\begin{align}\begin{split}1 + \cdots + (2k-1) + (2k+1) &= k^2 + 2k + 1 \\ &= (k+1)^2\end{split}\end{align}
증명이 끝났다.
정리해 보면, 임의 순서에서 참일 때 그 다음이 참임을 증명했기 때문에 맨 처음만 참이면 모든 경우에 대해 참이 된다. 누구도 부정할 수 없는 사실이다. 딱 두가지 경우에 대해서만 성립함을 증명하고도 무한한 가지수에 대해서 성립함을 증명할 수 있게 된 것이다. 정말 혁신적이다.
