수학적 귀납법은 자연수를 포함한 명제를 증명할 때 아주 유용하게 쓰이는 도구입니다. 수학사에 대한 저술로 유명한 Morris Klein은 Mathematical Thought: From Ancient to Modern Times에서 유클리드가 원론에서 소수의 개수가 무한개라는 것을 증명할 때 처음 사용했다고 주장합니다. 하지만, 그리스인들은 무한에 대한 논쟁에 결론을 내리지 못한 상태였기 때문에 유클리드가 소수의 개수가 무한이라는 생각을 정리했을지는 확실하지 않습니다. 그리고, 유클리드가 사용한 식 $$p_1 p_2 p_3 \cdots p_k +1$$ 이 또다른 소수를 나타내는 식은 아닙니다. 예를 들어, 2, 3, 5, 7, 11, 13이 모두 소수이지만 $2 \times 3 \times 5 \times 7 \times 11 \times 13+1 = 59 \times 509$로 소수가 아닙니다. 유클리드의 증명을 본따서 소수가 무한개 있다는 것을 증명하려면 이야기를 좀 다르게 풀어가야 합니다. 귀납법을 유지하려면 어떻게 해야 하는지는 다음 글의 댓글에서 확인할 수 있습니다.
그래서, 수학적 귀납법의 시작은 Morris Klein이 두 번째라고 언급한 16세기 무렵이라고 보는 것이 맞다고 보는 견해가 많습니다. 1575년 Maurolycus가 Arithmetica에서 다음 등식을 증명할 때 처음 수학적 귀납법이 등장합니다. $$ 1+3+5+ \cdots + (2n-1) = n^2$$
파스칼은 1665년 Traité du triangle arithmétique에서 그의 ⟨파스칼 삼각형⟩에 대한 여러 결과를 입증하는 데 수학적 귀납법을 사용했습니다.
1889년, 페아노는 학회 팜플렛 Arithmetices principia, nova methodo exposita에 자연수 구성의 공리인 ⟨페아노 공리⟩의 제5공리의 구성에 수학적 귀납법을 사용했습니다. 실제로, 페아노의 제5공리는 수학적 귀납법과 동치라는 것을 증명할 수 있습니다. 이것은 검색을 통해 확인하시기 바랍니다.
수학적 귀납법
수학적 귀납법은 자연수 $n$에 대한 명제 $p(n)$이 참이라는 것을 다음 두 과정을 거쳐서 증명하는 법을 말합니다.
- $p(1)$이 참이다.
- 임의의 자연수 $k$에 대해, $p(k)$가 참 $\Longrightarrow$ $p(k+1)$도 참
강한 수학적 귀납법
강한 수학적 귀납법은 자연수 $n$에 대한 명제 $p(n)$이 참이라는 것을 다음 두 과정을 거쳐서 증명하는 법을 말합니다.
- $p(1)$이 참이다.
- 임의의 자연수 $k$에 대해 $p(1)$, $p(2)$, $\cdots$, $p(k)$가 참 $\Longrightarrow$ $p(k+1)$도 참
강한 수학적 귀납법 $\Longrightarrow$ 수학적 귀납법
쉬운 것부터 합시다. 강한 수학적 귀납법은 위에서 소개한 문장 I, II를 만족하는 명제 $p(n)$은 모든 자연수 $n$에 대해 참이라는 것입니다. 이 논리에 의해 A, B를 만족하는 명제 $p(n)$도 모든 자연수 $n$에 대해 참이라는 것을 설명해 보겠습니다.
우선, A는 I과 같으므로 I이 성립합니다. 이제, $p(1)$, $p(2)$, $\cdots$, $p(k)$가 모두 성립한다고 가정하겠습니다. 그러면 $p(k)$가 참이 되므로 B에 의해 $p(k+1)$이 성립하게 됩니다. 즉, 강한 귀납법의 II번 조건을 만족하게 됩니다. 따라서, 강한 수학적 귀납법에 의해 $p(n)$은 모든 자연수 $n$에 대해 성립합니다.
그러므로, 강한 수학적 귀납법이 성립한다면 수학적 귀납법도 성립합니다.
수학적 귀납법 $\Longrightarrow$ 강한 수학적 귀납법
이번에는 수학적 귀납법을 이용해서 강한 수학적 귀납법이 성립함을 증명해 보겠습니다. 증명을 위해서 새로운 명제 $P(n)$을 다음과 같이 정의하겠습니다. $$P(n): p(1), p(2), \cdots, p(n)\text{이 모두 참이다.}$$
I이 성립하므로 $P(1)$이 성립합니다. 이제, $P(k)$가 성립한다고 가정하겠습니다. 그러면 $p(1)$, $p(2)$, $\cdots$, $p(k)$가 모두 성립하므로 II에 의해 $p(k+1)$이 성립하게 됩니다. 즉, $P(k+1)$도 참이 됩니다. 따라서, 수학적 귀납법에 의해 임의의 자연수 $n$에 대해 $P(n)$이 참이 되고, 그 결과로 $P(n)$에 포함된 $p(n)$도 참이 됩니다.
그러므로, 수학적 귀납법이 성립한다면 강한 수학적 귀납법도 성립합니다.
수학적 귀납법 vs 강한 수학적 귀납법
수학적 귀납법과 강한 수학적 귀납법이 같은 말을 하고 있기는 하지만, 증명해야 할 명제의 특성에 따라 둘 중 하나를 선택해서 사용합니다. 대체로 $k$번째만으로 $k+1$번째가 증명가능하면 수학적 귀납법을, $k$번째 이전의 결과도 필요하면 강한 수학적 귀납법을 사용합니다. 대표적인 것이 수열의 일반항 증명인데, 수열의 점화식이 $a_n$과 $a_{n+1}$만의 관계식으로 이루어져 있다면 수학적 귀납법을, 이보다 복잡하면 강한 수학적 귀납법을 이용합니다.
수학적 귀납법의 잘못된 예
수학적 귀납법을 잘못 사용하면 뜻하지 않은 결과를 얻을 수도 있습니다. 잘못된 사용의 예는 아마도 다음 증명이 가장 유명할 것입니다.
(잘못된) 증명: 모든 자연수 $n$에 대해 $n$명의 키가 같다는 것을 귀납법으로 증명하겠다. $n=1$일 때는 자명하다. 이제, $k$명의 키가 같다는 것을 가정하고 $k+1$명의 키를 생각해 보자. $k+1$명의 키를 각각 실수 $l_1$, $l_2$, $l_3$, $\cdots$, $l_{k+1}$이라 하면 귀납법의 가정에 의해 $k$명의 키를 비교하면 서로 같아야 하므로 $$l_1 = l_2 = \cdots = l_k, \quad l_2 = l_3 = \cdots = l_{k+1}$$ 이 성립해야 한다. 따라서, $l_1 = l_2 = l_3 = \cdots = l_k = l_{k+1}$이 되어 $k+1$명의 키도 서로 같다. 그러므로, 수학적 귀납법에 의해 모든 자연수 $n$에 대해 $n$명의 키는 같다.
오류 설명: 위 증명에서 틀린 부분은 식 $$l_1 = l_2 = \cdots = l_k, \quad l_2 = l_3 = \cdots = l_{k+1}$$ 에서 $l_1 = l_2 = l_3 = \cdots = l_k = l_{k+1}$을 얻어낸 부분입니다. 언뜻 자연스러워 보이지만 $k=1$일 때는 유도가 되지 않는 결과입니다. 수학적 귀납법을 사용할 때 $k$의 범위를 잊지 않길 바랍니다.