수학적 귀납법(mathematical induction)은 자연수 $n$에 대한 명제 $p(n)$이 모든 자연수 $n$에 대하여 성립함을 증명하는 방법이다. 다음 두 단계를 모두 보이면 된다.
이 두 조건이 모두 확인되면, 모든 자연수 $n$에 대하여 $p(n)$이 성립한다고 결론지을 수 있다.
수학적 귀납법은 도미노를 넘어뜨리는 원리와 같다. 첫 번째 도미노($n=1$)가 넘어지고, "어떤 도미노가 넘어지면 바로 다음 도미노도 넘어진다"는 규칙(귀납 단계)만 확인되면, 도미노가 끝없이 이어져 있어도 결국 모든 도미노가 넘어진다는 것을 알 수 있다. 무한히 많은 자연수 하나하나를 직접 대입해 확인할 수는 없지만, "처음 것이 되고, 하나가 되면 다음 것도 된다"는 두 가지만 보이면 전체가 성립함을 보장할 수 있다는 것이 핵심이다.
수학적 귀납법의 두 단계(기초 단계, 귀납 단계)가 왜 "모든 자연수에 대한 성립"을 보장하는지는 이미 알고 있는 사실 하나로부터 이끌어낼 수 있다. 바로 자연수의 정렬성이다: 자연수로 이루어진 집합이 공집합이 아니면, 그 집합은 반드시 가장 작은 원소를 가진다. 이는 자연수 $1, 2, 3, \dots$가 더 이상 내려갈 수 없는 시작점 $1$을 가지고 순서대로 나열되어 있다는, 이미 당연하게 받아들이는 사실이다.
이제 이 사실만으로 두 단계가 왜 충분한지 보이자. 기초 단계와 귀납 단계가 모두 성립한다고 하자. 만약 $p(n)$이 어떤 자연수에서 거짓이 될 수 있다면 어떤 일이 생기는지 따라가 본다.
$p(n)$이 거짓인 자연수들을 모아 집합 $S$를 만들자. $$S = \{\, n \in \text{자연수} : p(n)\text{이 거짓} \,\}$$
$p(n)$이 모든 자연수에서 성립하지 않는다고, 즉 $S$가 공집합이 아니라고 가정하자. 정렬성에 의해 $S$는 가장 작은 원소 $m$을 가진다.
여기서 막힌 부분을 뚫어야 한다: 이 $m$이 실제로 존재할 수 있는지 따져 보면 모순이 생긴다.
이는 $m \in S$, 즉 $p(m)$이 거짓이라는 가정과 정면으로 모순된다. 따라서 애초의 가정이 틀렸다는 뜻이므로 $S$는 공집합이어야 하고, 결국 모든 자연수 $n$에 대하여 $p(n)$이 참이다.
이렇게 해서 "기초 단계 + 귀납 단계"라는 두 조건만 확인하면 되는 이유가 드러난다. 두 단계는 각각 정렬성이 최소원소를 만들어내지 못하도록 막는 역할을 한다 — 기초 단계는 최소원소가 $1$이 되는 것을 막고, 귀납 단계는 그 밖의 어떤 수도 최소원소가 되는 것을 막는다.
예시 1 — 등식 $1+2+\cdots+n = \dfrac{n(n+1)}{2}$가 모든 자연수 $n$에서 성립함을 증명하자.
따라서 모든 자연수 $n$에 대하여 위 등식이 성립한다.
예시 2 — $3^n-1$이 2의 배수임을 증명하자.
따라서 모든 자연수 $n$에 대하여 $3^n-1$은 2의 배수이다.
컴퓨터 프로그램의 재귀 함수나 반복문이 모든 입력에 대해 항상 올바르게 동작함을 증명할 때 수학적 귀납법과 똑같은 논리 구조가 쓰인다. 예를 들어 $n$개의 숫자를 정렬하는 재귀 알고리즘이 있다고 하자. "입력 크기가 $1$일 때는 항상 올바르게 정렬된다"(기초 단계에 해당)를 확인하고, "입력 크기가 $k$ 이하일 때 항상 올바르게 정렬된다고 가정하면, 크기 $k+1$인 입력도 올바르게 정렬된다"(귀납 단계에 해당)를 보이면, 그 알고리즘은 모든 크기의 입력에 대해 올바르게 동작한다고 결론지을 수 있다. 이런 증명 방식을 컴퓨터 과학에서는 흔히 "구조적 귀납법" 또는 "루프 불변식(loop invariant)" 증명이라 부르는데, 그 뼈대는 수학적 귀납법과 동일하다.
잘못된 생각: "$n=k$일 때 성립한다고 가정한다"는 부분을 이미 증명된 사실을 사용하는 것으로 착각한다. → 왜 틀렸는가: 귀납 단계는 "$p(k)$가 참이라면 $p(k+1)$도 참이다"라는 조건문 자체를 증명하는 것이다. $p(k)$ 자체가 참이라고 미리 확정 짓는 것이 아니라, 가정 하에 논리적 연결고리를 만드는 과정임을 이해해야 한다.
잘못된 생각: 귀납 단계만 보이고 기초 단계 확인을 생략하거나, 반대로 기초 단계만 확인하고 안심한다. → 왜 틀렸는가: 귀납 단계만으로는 "성립하는 도미노가 있다면 다음 것도 넘어진다"는 것만 보일 뿐, 애초에 첫 도미노가 넘어지는지는 알 수 없다. 두 단계는 반드시 모두 필요하다.
잘못된 생각: $n=k+1$일 때의 식을 귀납적 가정($p(k)$)을 전혀 사용하지 않고 처음부터 다시 계산해서 증명하려 한다. → 왜 틀렸는가: 이는 수학적 귀납법이 아니라 그냥 각 경우를 따로 증명하는 것과 같아, $n=k+1$과 $p(k)$ 사이의 연결을 보이지 못한다. 반드시 가정한 $p(k)$의 식을 변형해 $p(k+1)$을 이끌어내야 한다.
명시적인 수학적 귀납법의 형태는 16세기 이탈리아의 수학자 프란체스코 마우롤리코(Francesco Maurolico)가 1575년 저작에서 홀수의 합이 제곱수가 됨을 증명하는 과정에서 처음 사용한 것으로 알려져 있다. 17세기에는 블레즈 파스칼이 파스칼의 삼각형과 관련된 성질들을 증명할 때 이 방법을 명확하게 활용했다. 그러나 "수학적 귀납법(mathematical induction)"이라는 이름 자체는 한참 뒤인 19세기에 오거스터스 드모르간이 붙인 것으로, 그는 이 논증이 경험을 일반화하는 통상적 의미의 "귀납"과는 다른, 엄밀한 연역적 증명법임을 명확히 구분해 설명했다. 이후 19세기 말 주세페 페아노가 자연수를 공리화하면서 귀납법을 자연수를 정의하는 공리 중 하나로 포함시켰고, 그 결과 오늘날과 같은 두 단계(기초 단계·귀납 단계) 형식이 표준으로 굳어졌다.