수학적 귀납법(Mathematical induction)이란 수학의 증명 방법 중 하나로, 주로 어떠한 명제가 모든 자연수에 대하여 성립함을 보이려고 할 때 이용된다. 수학적 귀납법은 두 단계로 이루어진다. 먼저 주어진 명제가 1에 대하여 (일반적으로 $k$에 대하여) 성립함을 보인다. 다음으로, 그 명제가 $1$ 이상의 ($k$ 이상의) 임의의 자연수 $n$에 대하여 성립하면, $n+1$에서도 성립함을 보인다. 그러면 수학적 귀납법에 의하여 주어진 명제가 모든 자연수에 ($k$ 이상의 자연수에) 대하여 성립하게 된다.

최초로 수학적 귀납법이 사용된 예로는 유클리드 (Euclid)의 소수의 무한성에 대한 증명에서 찾아 볼 수 있다. 하지만 유클리드는 수학적 귀납법을 자신이 사용한 증명의 방법으로서 명확히 밝히지 않았으며, 최초로 귀납법에 대한 엄밀한 서술은 1665년에서야 파스칼 (Blaise Pascal)에 의해 이루어졌다. 후에 귀납법은 베르누이 (Jacob Bernoulli)에 의하여 본격적으로 다음어지고 널리 이용되었다. 현대의 좀 더 일반적으로 구조화 된 형태의 귀납법은 19세기에 와서야 이루저 졌으며, 부울 (George Boole), 드 모르간(Augustus de Morgan), 펄스 (Charles Sanders Peirce), 페아노 (Giuseppe Peano), 데데킨트 (Richard Dedekind) 등의 수학자에 의해 정립 되었다.

이제 1575년 마우롤리코 (Francesco Maurolico)에 의해 증명 된 다음의 명제 "첫 $n$개의 홀수의 합은 $n^2$과 같다." 를 증명해 보자.

증명. 먼저 $n$이 $1$일 때, 주어진 명제가 성립함은 자명하다. ($1 = 1^2$) 이제 $n$에 대하여 주어진 명제가 성립한다고 가정하자. 그러면 아래의 등식이 성립한다. \[ 1 + 3 + \cdots + (2n-1) = n^2. \] 이제 $n+1$번 째 홀수인 $2n+1$을 양변에 더해주면, \[ 1 + 3 + \cdots + (2n-1) + (2n+1) = n^2 + (2n+1) = (n+1)^2 \] 이 되므로 $n+1$에서도 명제가 참임을 알 수 있다. 따라서 수학적 귀납법에 의하여 증명이 완료된다.

  수학적 귀납법은 다양한 방법으로 확장이 가능하다. 먼저 가장 기본적인 형태의 귀납법을 다시 수학적으로 정리해보자. 자연수 $n$에 대하여 주어진 명제 $P(n)$에 대하여,

• $P(1)$이 참이다.
• $P(n)$이 참이면 $P(n+1)$도 참이다.

를 만족하면, 모든 자연수 $n$에 대하여 $P(n)$이 참이다.

강한 수학적 귀납법 (Strong Mathematical Induction)으로 불리는 수학적 귀납법의 변형 중 하나는 다음과 같다. 주어진 명제 $P(n)$에 대하여,

• $P(1)$이 참이다.
• $P(1),\, P(2),\, \ldots,\, P(n)$이 모두 참이면, $P(n+1)$도 참이다.

를 만족하면, 모든 자연수에 $n$ 대하여 $P(n)$이 참이다.

다음과 같은 형태의 강한 수학적 귀납법의 변형도 생각해 볼 수 있다.

• $P(1),\, P(2),\, \ldots,\, P(k)$가 모두 참이다.
• $P(n)$이 참이면 $P(n+k)$도 참이다.

• $P(1)$과 $P(2)$가 참이다.
• $P(n)$과 $P(n+1)$이 참이면 $P(n+2)$도 참이다.

• $P(1)$과 $P(2)$가 참이다.
• $P(n)$이 참이면 $P(n+2)$도 참이다.

다음과 같은 형태의 역 수학적 귀납법 (Reverse Mathematical Induction)도 가능하다.

• $P(2)$가 참이다.
• $P(n)$이 참이면 $P(2n)$도 참이다.
• $P(n)$이 참이면 $P(n-1)$도 참이다.

역 수학적 귀납법의 변형으로는 다음이 있다.

• 어떤 자연수의 무한 부분집합 $A$가 존재하여, $n \in A$이면 $P(n)$이 참이다.
• $P(n)$이 참이면 $P(n-1)$도 참이다.

주어진 명제가 두개인 경우에도 수학적 귀납법의 적용이 가능하다. 예를 들어 자연수 $n$에 대하여 주어진 두 명제 $P(n)$과 $Q(n)$이 있다고 하자.

• $P(1)$이 참이다.
• $P(n)$이 참이면 $Q(n)$이 참이다.
• $Q(n)$이 참이면 $P(n+1)$이 참이다.

그러면 모든 자연수 $n$에 대하여, $P(n)$과 $Q(n)$ 모두 참이 된다.

마지막으로 주어진 명제가 하나 이상의 자연수에 대한 명제인 경우를 살펴보자. 예를 들어 두 자연수 $m,\,n$에 대하여 주어진 명제 $P(m,\,n)$에 대하여, 모든 자연수 $m,\,n$에 대하여,

• $P(m,\,1)$, $P(1,\,n)$이 참이다.
• $P(m+1,\,n)$, $P(m,\,n+1)$이 참이면 $P(m+1,\,n+1)$도 참이다.

그러면 모든 자연수 $m,\,n$에 대하여, $P(m,\,n)$이 참이 된다.

이제 수학적 귀납법 (정확하게는 강한 수학적 귀납법)을 이용한 재미있는 정리를 끝으로 마무리 하고자 한다.

  증명. 우선 자연수 $1$은 자연수의 제일 처음으로 나타나는 수이다. 따라서 $1$은 특별할 수 밖에 없다. 이제 $1$부터 $n$까지의 자연수가 모두 특별하다고 가정하다. 우리는 $n+1$또한 특별한 수임을 증명해야 한다. 만약에 $n+1$이 특별한 수가 아니라면, 이는 특별하지 않은 최소의 자연수가 되므로 굉장히 특별한 수가 된다! 따라서 모순이 발생하고 $n+1$은 특별한 수일 수 밖에 없다. 따라서 귀납법에 의해 모든 자연수는 특별하다.