수학적 귀납법(Mathematical induction)

도미노를 한 줄로 세워 두었습니다. 두 가지만 확인하면 모두 넘어진다는 것을 압니다. 첫째, 첫 도미노가 넘어진다. 둘째, 어느 도미노든 넘어지면 바로 다음 도미노를 넘어뜨린다. 수학적 귀납법은 이 논리를 자연수에 옮긴 것입니다. 명제 $P(n)$에 대해 기초 단계⁠(base case)⁠ $P(1)$이 참이고, 귀납 단계⁠(inductive step)⁠ '$P(k)$가 참이면 $P(k+1)$도 참'을 보이면, 모든 자연수 n에서 $P(n)$이 참입니다. 도미노와 다른 점도 있습니다. 도미노 줄에는 끝이 있고 차례로 넘어지는 데 시간이 걸리지만, 귀납법은 끝없이 많은 명제 $P(1), P(2), P(3), \ldots$를 두 가지 확인만으로 한꺼번에 얻습니다.

도미노 개, . 밀기 다시 세우기

두 조건 가운데 하나라도 빠지면 결론이 무너집니다. 기초 단계가 없으면 '넘어지면 다음도 넘어진다'는 조건은 헛돌 뿐입니다. 귀납 단계가 어느 한 곳에서라도 깨지면 그 뒤로는 아무 보장이 없습니다. 귀납법이 옳은 까닭은 자연수의 성질에 있습니다. 거짓인 n이 있다면 그런 n들의 집합⁠(set)⁠에 가장 작은 원소⁠(element)⁠ m이 있을 것입니다. m은 1이 아닙니다(기초 단계). 그러면 m−1도 자연수이고 m보다 작으니 P(m−1)은 참이며, 귀납 단계에 따라 P(m)도 참이어야 합니다. 모순입니다. 자연수의 공집합⁠(empty set)⁠이 아닌 부분집합⁠(subset)⁠에는 언제나 가장 작은 원소가 있다는 이 성질을 정렬성⁠(well-ordering principle)⁠이라 하며, 정렬성과 귀납법은 한쪽에서 다른 쪽을 증명할 수 있는 같은 힘의 원리입니다.

보기. 처음 m개 홀수의 합은 $m^2$입니다. m = 일 때:

m = 1이면 1 = 1²이므로 참입니다(기초⁠, basics⁠). m×m 정사각형의 위와 오른쪽에 ㄱ자 모양으로 $2m+1$칸을 두르면 $(m+1)\times(m+1)$ 정사각형이 됩니다. 식으로는 $m^2 + (2m+1) = (m+1)^2$이고, 이것이 귀납 단계입니다. 같은 방식으로 등비급수⁠(geometric series)⁠의 합 공식, 이항정리⁠(binomial theorem)⁠, 피보나치 수의 여러 항등식을 증명합니다.

강한 귀납법. 귀납 단계에서 바로 앞 하나가 아니라 1부터 k까지 전부가 참이라고 가정해도 됩니다. 2 이상의 자연수는 모두 소인수분해⁠(prime factorization)⁠된다는 증명이 그렇습니다. n이 소수⁠(prime number)⁠이면 n 자신이 소인수분해입니다. 소수가 아니면 $n = ab\ (1 \lt a, b \lt n)$이고, a와 b는 n보다 작으므로 가정에 따라 이미 소수의 곱으로 쓰입니다. 그러니 n도 그렇습니다. 여기서 a와 b는 n−1이라는 보장이 없으므로, 바로 앞 하나만 가정하는 보통의 귀납법으로는 부족합니다. 항 하나가 앞의 여러 항으로 정해지는 점화식⁠(recurrence relation)⁠의 성질도 대개 이렇게 증명합니다.

프로그램과 귀납법. 재귀⁠(recursion)⁠는 귀납법을 거꾸로 돌린 것입니다. 프로그램이 가장 작은 경우를 옳게 풀고, 큰 경우의 답을 더 작은 경우의 답으로 옳게 짓는다고 합시다. 줄여 나가다 보면 반드시 가장 작은 경우에 닿는다면, 귀납법이 그 프로그램이 모든 입력에서 옳은 답을 낸다는 것을 보장합니다. 반복문이 옳다는 증명에는 '루프 불변식⁠(loop invariant)⁠', 곧 반복이 한 바퀴 돌 때마다 참으로 유지되는 명제를 씁니다. 처음에 참이고 한 바퀴가 참을 참으로 넘겨준다는 것을 보이는 일이니, 반복 횟수에 대한 귀납법입니다. 유클리드 호제법⁠(Euclidean algorithm)⁠이 언제나 최대공약수⁠(greatest common divisor)⁠를 준다는 증명이 대표적인 예입니다. 두 수를 (큰 수를 작은 수로 나눈 나머지⁠(remainder)⁠, 작은 수)로 바꾸어도 두 수의 최대공약수는 변하지 않는다는 것이 불변식이고, 나머지가 0이 되어 멈추면 남은 수가 곧 최대공약수입니다(알고리즘⁠(algorithm)⁠). 리스트나 나무처럼 제 안에 같은 모양을 품는 대수적 자료형⁠(algebraic data type)⁠에서는 같은 원리를 자료의 짜임새를 따라 쓰는데(구조적 귀납법⁠, structural induction⁠), 증명 보조기⁠(proof assistant)⁠는 이런 귀납 증명의 모든 단계를 기계로 검사합니다.

조심할 점. '모든 말은 색이 같다'는 유명한 가짜 증명이 있습니다. 말 n+1마리에서 한 마리씩 빼면 겹치는 두 무리가 생기고, 각 무리는 귀납 가정에 따라 한 색이므로 모두 한 색이라는 것입니다. 그러나 1마리에서 2마리로 넘어갈 때는 두 무리가 겹치지 않아 귀납 단계가 깨집니다. 도미노 그림의 '벌어진 틈'이 바로 거기입니다.

이어지는 곳. 귀납법은 자연수처럼 가장 작은 것에서 출발해 한 걸음씩 쌓아 올린 구조라면 어디서나 씁니다. 원소를 하나씩 셀 수 있다(가산)는 것만으로는 부족합니다. 유리수⁠(rational number)⁠는 셀 수 있지만, 크기 순서로 보면 0보다 큰 유리수 전체처럼 가장 작은 원소가 없는 부분집합이 있어서 위의 정렬성 논법이 통하지 않습니다. 비둘기집 원리⁠(pigeonhole principle)⁠, 순열⁠(permutation)⁠의 개수 n!, 카탈랑 수⁠(Catalan number)⁠의 점화식이 모두 귀납법으로 증명됩니다. 1889년 이탈리아의 수학자 페아노는 '1은 자연수다', '모든 자연수에는 바로 다음 수가 있다' 같은 몇 개의 공리⁠(axiom)⁠로 자연수를 정했는데(페아노 공리계⁠, Peano axioms⁠), 귀납법이 그 공리 가운데 하나로 들어가 있습니다.

이 체계를 논리식으로 적은 페아노 산술⁠(Peano arithmetic)⁠에 모순이 없다면, 귀납법까지 갖춘 그 안에서도 증명할 수 없는 참인 명제가 있습니다. 이것이 1931년 괴델이 보인 불완전성 정리⁠(incompleteness theorem)⁠입니다. 범주론⁠(category theory)⁠으로 적으면(여기서는 자연수를 0부터 셉니다) 귀납법은 (ℕ, 0, S)가 함자⁠(functor)⁠ $X\mapsto 1 + X$의 시작 대수라는 문장의 '다른 대수로 가는 준동형⁠(homomorphism)⁠이 하나뿐'이라는 부분이고, '하나 있다'는 부분이 재귀로 함수⁠(function)⁠를 정의해도 된다는 보증입니다. 반복문이 끝났을 때 불변식이 참이라는 호어 논리⁠(Hoare logic)⁠의 규칙도 돈 바퀴 수에 대한 귀납법으로 정당화됩니다.