정의
수학적 귀납법(數學的歸納法, mathematical induction)은 모든 자연수가 어떤 주어진 성질을 만족시킨다는 명제를 증명하는 방법의 하나이다. 가장 작은 자연수(문맥에 따라 0 또는 1)가 그 성질을 만족시킴을 증명한 뒤, 만약 어떤 자연수가 만족시키면 바로 다음 자연수 역시 만족시킴을 증명함으로써 모든 자연수에 대한 증명을 완성한다. 이름과는 달리 귀납적 논증이 아닌 연역적 논증에 속하며, 자연수의 페아노 공리계의 공리이자 메타논리학적 추론 규칙이기도 하다.
증명의 구조
수학적 귀납법을 통한 증명은 일반적으로 다음 두 단계로 구성된다.
- 기초 단계(basis step): 처음 오는 자연수(0 또는 1)에 대하여 명제가 성립함을 증명한다.
- 귀납 단계(inductive step): 임의의 자연수 $n$에 대하여 명제가 성립한다고 가정(귀납 가정)한 뒤, $n+1$에 대해서도 성립함을 증명한다.
이 두 단계가 모두 증명되면, 수학적 귀납법에 의하여 해당 명제는 모든 자연수에 대하여 성립한다.
페아노 공리계에서의 형식화
자연수의 2차 논리 이론인 페아노 공리계에서는 수학적 귀납법이 다음과 같은 공리로 등장한다. 임의의 1항 술어 $P(-)$가 다음 두 조건을 만족시킨다고 하자.
- $P(0)$이 성립한다.
- 임의의 $n \in \mathbb{N}$에 대하여, 만약 $P(n)$이 성립한다면 $P(n+1)$도 성립한다.
그렇다면, 임의의 $n \in \mathbb{N}$에 대하여 $P(n)$이 성립한다.
변형 및 일반화
수학적 귀납법에는 여러 가지 변형이 존재한다.
- 시작점 변경: 0이나 1 대신 임의의 정수 $m$에서 시작하여 $m$ 이상의 모든 정수에 대해 증명할 수 있다.
- 역진 귀납법: $n+1$에서 성립하면 $n$에서도 성립함을 이용하여 $m$ 이하의 모든 자연수에 대해 증명한다.
- 강한 수학적 귀납법(초한 귀납법): $n$보다 작은 모든 자연수에 대해 성립한다는 가정 하에 $n$에서 성립함을 증명한다. 이는 제2 수학적 귀납법 또는 완전 수학적 귀납법이라고도 불린다.
- 초한 귀납법: 자연수 집합을 넘어 정초 관계(well-founded relation)를 갖춘 임의의 집합으로 확장한 형태이다.
역사
수학적 귀납법의 기원은 유클리드의 소수의 무한성 증명이나 바스카라 2세의 순환 방법(cyclic method) 등에서 찾을 수 있다. 1000년경 알카라지(al-Karaji)는 이항 정리 등을 증명하기 위해 수학적 귀납법의 한 형태를 사용했다. 최초로 귀납법에 대한 엄밀한 서술을 한 이는 프란체스코 마우롤리코(Francesco Maurolico)로, 1575년 저서 《Arithmeticorum libri duo》에서 처음 n개의 홀수의 합이 $n^2$임을 증명하는 데 사용했다. 이후 야코프 베르누이, 블레즈 파스칼, 피에르 드 페르마도 독립적으로 귀납법을 발견했다.
'수학적 귀납법'이라는 용어는 1838년 오거스터스 드 모르간(Augustus de Morgan)이 처음 사용했다. 1888년 리하르트 데데킨트(Richard Dedekind)는 《수란 무엇인가》(Was sind und was sollen die Zahlen?)에서 '완전 귀납법'(vollständige Induktion)이라는 표현을 사용했고, 1889년 주세페 페아노(Giuseppe Peano)는 페아노 공리계를 제안하면서 수학적 귀납법을 공리화하여 오늘날의 엄밀한 형태를 갖추게 되었다.
예: 홀수의 합 공식
모든 자연수 $n$에 대하여 다음 등식이 성립함을 수학적 귀납법으로 증명할 수 있다.
$$ 1 + 3 + 5 + \cdots + (2n-1) = n^2 $$
증명:
- $n=1$일 때, $1 = 1^2$이므로 성립한다.
- $n$에 대하여 성립한다고 가정하면 $1 + 3 + 5 + \cdots + (2n-1) = n^2$이다. 양변에 $2n+1$을 더하면 $1 + 3 + 5 + \cdots + (2n-1) + (2n+1) = n^2 + 2n + 1 = (n+1)^2$이므로 $n+1$에 대해서도 성립한다.
따라서 수학적 귀납법에 의하여 모든 자연수 $n$에 대하여 등식이 성립한다.
