cki_math_lab logo Home
홈/ 선행학습/ 수학적 귀납법

선행학습 · PREREQUISITE

수학적 귀납법

Mathematical Induction

序

수학적 귀납법은 "모든 자연수 n에 대하여 P(n)"이라는, 무한히 많은 경우를 담은 명제를 단 두 개의 유한한 논증으로 증명하는 방법이다. n에 1, 2, 3, …을 몇 개 넣어 확인하는 것은 증명이 아니다(증명법의 반례 n²+n+41은 n=39까지 소수이다가 n=40에서 깨진다). 귀납법은 "처음 경우가 성립한다"와 "어떤 경우가 성립하면 그다음 경우도 성립한다"만 보이면 그 사슬이 모든 자연수에 닿는다는 원리를 쓴다. 이 원리는 아래에서 보듯 자연수의 공리 속에 들어 있다.

History

귀납적인 논증은 오래전부터 쓰였지만, 오늘날처럼 "기초 단계"와 "귀납 단계"를 나누어 분명하게 적은 초기 인물로는 17세기의 파스칼1)이 흔히 꼽힌다. 19세기 말 페아노2)는 자연수를 몇 개의 공리로 규정하면서 귀납의 원리를 그 공리 가운데 하나로 넣었다. 그래서 수학적 귀납법은 따로 증명하는 정리가 아니라 자연수가 무엇인지를 정하는 원리에 속한다.

페아노 공리계 (Peano System)

집합 N과, N의 각 원소 n에 원소 n′("n의 다음 수")을 대응시키는 규칙이 다음 다섯 조건을 만족한다고 하자.
ⅰ1의 존재N에는 1이라는 원소가 있다.
ⅱ다음 수N의 각 원소 n에 대하여 다음 수 n′이 N 안에 단 하나 정해진다.
ⅲ1은 처음어떤 원소의 다음 수도 1이 아니다.
ⅳ다음 수의 구별m′ = n′이면 m = n이다. 곧 서로 다른 두 원소의 다음 수는 서로 다르다.
ⅴ귀납 공리N의 부분집합 S가 1을 원소로 갖고, n∈S일 때마다 n′∈S이면 S = N이다.

이 조건을 만족하는 N을 자연수 집합이라 하고, n′을 보통 n+1로 쓴다.

수학적 귀납법

자연수 n에 관한 명제 P(n)에 대하여 다음 Ⅰ, Ⅱ가 성립하면 P(n)은 모든 자연수 n에 대하여 성립한다.
Ⅰ(기초 단계) P(1)이 성립한다.
Ⅱ(귀납 단계) 임의의 자연수 k에 대하여 P(k)가 성립하면 P(k+1)도 성립한다. 곧 P(k) ⟹ P(k+1).

Ⅱ를 증명할 때 잠시 참이라고 놓는 P(k)를 귀납 가정이라고 한다. Ⅱ는 P(k)가 실제로 참이라고 주장하는 것이 아니라 "P(k)가 참이라면 P(k+1)도 참"이라는 조건문을 증명하는 것이다.

왜 성립하는가. S = {n∈N | P(n)이 성립한다}로 놓자. Ⅰ에 의해 1∈S이고, Ⅱ에 의해 k∈S이면 k+1∈S이다. 따라서 귀납 공리 ⅴ에 의해 S = N, 곧 모든 자연수 n에 대하여 P(n)이 성립한다. 흔히 쓰는 "도미노" 비유(P(1)이 참이고 P(1)⟹P(2)이므로 P(2)가 참이고, …)는 이 사실을 풀어 쓴 것인데, "…"으로 끝없이 이어지는 부분을 한 번에 보장해 주는 것이 바로 귀납 공리이다.

例 1

모든 자연수 n에 대하여 1+3+5+⋯+(2n−1) = n² ⋯ ⓐ 이다. 곧 처음 n개의 홀수의 합은 n의 제곱이다.

n=1, 2, 3을 넣으면 1=1², 1+3=4=2², 1+3+5=9=3²으로 맞지만, 이것만으로는 증명이 아니다. ⓐ를 P(n)이라 하고 Ⅰ, Ⅱ를 보이자.

Proof.
Ⅰn=1일 때 좌변은 1, 우변은 1²=1이므로 P(1)이 성립한다.
Ⅱ P(k), 곧 1+3+⋯+(2k−1) = k² 이 성립한다고 가정하자. k+1번째 홀수는 2(k+1)−1 = 2k+1이므로 양변에 2k+1을 더하면 1+3+⋯+(2k−1)+(2k+1) = k²+2k+1 = (k+1)² 이다. 이것은 ⓐ의 n 자리에 k+1을 넣은 식, 곧 P(k+1)이다.
Ⅰ, Ⅱ와 수학적 귀납법에 의해 ⓐ는 모든 자연수 n에 대하여 성립한다.

例 2

모든 자연수 n에 대하여 n³−n은 6의 배수이다.

Proof. 이 명제를 P(n)이라 하자.

Ⅰn=1이면 1³−1 = 0 = 6·0이므로 P(1)이 성립한다.
Ⅱ k³−k가 6의 배수라고 가정하자. 그러면 (k+1)³−(k+1) = (k³+3k²+3k+1)−(k+1) = (k³−k) + 3k(k+1) 이다. 우변의 k³−k는 귀납 가정에 의해 6의 배수이고, k(k+1)은 연속한 두 정수의 곱이므로 짝수이다 (경우를 나누는 증명의 보기). 따라서 3k(k+1)도 6의 배수이고, 두 6의 배수의 합인 (k+1)³−(k+1)은 6의 배수이다. 곧 P(k+1)이 성립한다.

Ⅰ, Ⅱ에 의해 모든 자연수 n에 대하여 n³−n은 6의 배수이다.

例 3 (베르누이 부등식3))

실수 h > −1과 모든 자연수 n에 대하여 (1+h)n ≥ 1+nh 이다.

Proof. 주어진 부등식을 P(n)이라 하자.

Ⅰn=1이면 양변이 모두 1+h이므로 P(1)이 성립한다(등호).
Ⅱ (1+h)k ≥ 1+kh라고 가정하자. h > −1이므로 1+h > 0이고, 양수를 곱해도 부등호 방향은 그대로이므로 (1+h)k+1 ≥ (1+kh)(1+h) = 1+(k+1)h+kh² 이다. kh² ≥ 0이므로 우변은 1+(k+1)h 이상이다. 곧 (1+h)k+1 ≥ 1+(k+1)h, P(k+1)이 성립한다.

Ⅰ, Ⅱ에 의해 부등식은 모든 자연수 n에 대하여 성립한다. h ≠ 0이면 n ≥ 2일 때(n = k+1, k ≥ 1) Ⅱ의 kh²이 0보다 커서 등호 없는 부등식 (1+h)n > 1+nh를 얻는다.

출발점이 1이 아닐 때. 명제가 어떤 정수 m 이상의 n에 대해서만 주장된다면, Ⅰ을 "P(m)이 성립한다"로, Ⅱ를 "k ≥ m일 때 P(k) ⟹ P(k+1)"로 바꾸면 된다. 이것은 Q(n) = P(n+m−1)에 원래의 귀납법을 적용한 것과 같다.

귀납 단계의 여러 모양

귀납 단계 Ⅱ는 같은 내용을 다음처럼 쓰기도 한다.

Ⅲ k ≥ 2인 임의의 자연수 k에 대하여 P(k−1) ⟹ P(k).
Ⅱ의 k를 k−1로 바꾸어 적었을 뿐이므로 Ⅱ와 같은 말이다.

귀납 가정을 더 넉넉하게 잡는 형태도 있다. P(k+1)을 보일 때 바로 앞의 P(k)만이 아니라 P(1)부터 P(k)까지 전부를 가정해도 된다.

Ⅳ 임의의 자연수 k에 대하여, P(1), P(2), ⋯, P(k)가 모두 성립하면 P(k+1)도 성립한다.
Ⅴ k ≥ 2인 임의의 자연수 k에 대하여, P(1), P(2), ⋯, P(k−1)이 모두 성립하면 P(k)도 성립한다.
(Ⅴ는 Ⅳ의 k를 k−1로 바꾼 것이다.)

Ⅰ과 Ⅳ(또는 Ⅴ)가 성립해도 P(n)은 모든 자연수 n에 대하여 성립한다. 이 형태를 강한 귀납법이라고도 한다. 이유 : Q(n)을 "P(1), P(2), ⋯, P(n)이 모두 성립한다"로 놓자. Ⅰ에 의해 Q(1)이 성립한다. Q(k)가 성립하면 Ⅳ에 의해 P(k+1)이 성립하므로 Q(k+1)도 성립한다. 따라서 원래의 수학적 귀납법에 의해 모든 n에 대하여 Q(n)이, 따라서 P(n)이 성립한다. 가정이 강해진 만큼, P(k+1)이 바로 앞이 아닌 더 작은 경우에 기대는 명제(아래 例 4)를 다룰 때 편리하다.

例 4

2 이상의 모든 자연수는 소수이거나 소수 몇 개의 곱이다.

Proof. 2 이상의 자연수 n에 대하여 이 명제를 P(n)이라 하고, 출발점이 2인 강한 귀납법(Ⅴ의 꼴)을 쓴다.

Ⅰ2는 소수이므로 P(2)가 성립한다.
Ⅴ k ≥ 3이고, 2 이상 k 미만의 모든 자연수에 대하여 명제가 성립한다고 가정하자. k가 소수이면 P(k)는 바로 성립한다. k가 소수가 아니면 k = ab (2 ≤ a, b < k)로 쓸 수 있다. a와 b는 모두 2 이상 k 미만이므로 귀납 가정에 의해 각각 소수이거나 소수들의 곱이고, 따라서 그 곱 k도 소수들의 곱이다. 곧 P(k)가 성립한다.

여기서 a, b는 k−1이 아니라 그보다 훨씬 작을 수 있으므로, P(k−1)만 가정하는 보통의 귀납법으로는 이 논증이 되지 않는다.

  1. 1) Pascal, Blaise, 1623~1662, 프랑스
  2. 2) Peano, Giuseppe, 1858~1932, 이탈리아
  3. 3) Bernoulli's inequality
← 증명법 목차로 →
prerequisite:logic source:cki_math_lab-blog