직관 — 출발점과 끊기지 않는 연결
도미노를 한 줄로 세웠다고 하자. 첫 조각을 넘어뜨리는 일과, 어느 조각이 넘어져도 바로 다음 조각을 넘어뜨리는 배치는 서로 다른 조건이다. 두 조건이 함께 있어야 뒤의 조각까지 차례로 이어진다.
첫 조각은 증명의 첫 경우, 이웃 조각의 연결은 한 경우가 참이면 다음 경우도 참이라는 논증에 대응한다. 그림을 길게 그리는 것이 증명은 아니다. 어느 번호에서도 끊기지 않는 이유를 일반적인 문자로 보여야 한다. 이 방법을 배우면 수열의 합처럼 자연수마다 하나씩 주어진 주장을 증명할 수 있다.
수학적 귀납법은 첫 경우와 다음 경우의 연결로 증명한다
수학적 귀납법은 자연수에 관한 명제가 첫 경우에서 참이고, 임의의 번호에서 참이면 다음 번호에서도 참임을 보여 전체 범위에서 성립함을 증명하는 방법이다. 여기서는 자연수를 로 놓고, 번호 에 관한 명제를 이라 쓴다.
화살표 는 ‘앞의 명제가 참이면 뒤의 명제도 참이다’를 뜻한다. 첫 조건이 출발점을 주고, 둘째 조건을 에 차례로 적용할 수 있다. 이 두 조건으로 결론을 얻는 원리가 수학적 귀납법이다.
| 기호 | 이름 | 원어 | 뜻 |
|---|---|---|---|
| n에 관한 명제 | statement about n | 번호 n을 넣었을 때 참·거짓을 판단할 주장 | |
| 첫 경우 | base case | 직접 참임을 확인하는 출발점 | |
| 임의의 자연수 | arbitrary natural number | 특정 값에 고정하지 않은 번호 | |
| 귀납가정 | induction hypothesis | 다음 경우를 보일 때 전제로 놓는 주장 | |
| 귀납 단계 | inductive step | 한 경우에서 다음 경우로 이어지는 논증 |
교과서는 같은 내용을 ‘(i) 일 때 성립한다. (ii) 일 때 성립한다고 가정하면 일 때도 성립한다’로 쓴다. (ii)의 가정이 이 페이지의 귀납가정 다. 결론의 ‘모든 자연수’는 모든과 어떤에서 배운 ‘모든’이다.
그림 1의 윗줄에서는 첫 경우가 출발점이다. 아랫줄은 어떤 에서도 통하는 연결 규칙을 따로 표시한다. ‘첫 세 경우를 확인했다’와 ‘모든 연결이 성립한다’는 다른 말이다.
figures/base_and_step.py자연수의 합에서 귀납가정은 어디에 쓰일까?
귀납가정은 이미 더한 앞부분을 간단한 식으로 바꾸는 자리에 쓰인다. 등차수열의 합에서 배운 공식을 이번에는 귀납법으로 증명해 보자. 증명할 명제는
첫 경우 에서 왼쪽은 1, 오른쪽은 이다. 따라서 은 참이다.
다음으로 임의의 자연수 를 잡고, 가 참이라고 가정하자. 즉 라고 놓는다. 목표인 의 왼쪽은 여기에 새 항 을 더한 합이다.
식 (3)의 첫 등호에서 귀납가정을 사용했다. 마지막 식은 식 (2)의 을 로 바꾼 오른쪽과 정확히 같다. 따라서 가 참이면 도 참이다. 첫 경우와 귀납 단계를 모두 보였으므로 식 (2)는 모든 자연수 에서 성립한다.
예를 들어 일 때는 앞 네 항의 합 10에 다음 항 5를 더해 15가 된다. 그림 2는 이 덧셈을 칸 수로 보여 준다. 계단 모양 10칸이 귀납가정이 알려 주는 앞부분이고, 새로 붙인 한 줄 5칸이 새 항 이다.
figures/triangle_step.py이 그림은 식 (3)의 동작을 읽는 예다. 증명을 완성하는 것은 4라는 한 값이 아니라 임의의 에 대해 쓴 전개다.
참이라고 가정하면 결론을 미리 믿는 것 아닌가?
귀납가정은 전체 결론을 선언하는 일이 아니다. 조건명제 ‘가 참이면 도 참이다’를 증명하기 위해 앞쪽을 잠시 전제로 삼는 것이다. 다음 경우까지 이미 참이라고 가정해서는 안 된다.
이 차이는 첫 경우를 빼면 드러난다. 틀린 주장 을 생각해 보자. 를 가정해 양변에 을 더하면
이어서 같은 형태의 을 얻는다. 하지만 은 라는 거짓 명제다. 연결 형식이 유지되어도 출발점이 없으면 결론을 얻지 못한다. 식 (2)의 증명에서 첫 경우를 따로 확인한 이유다.
부등식도 같은 두 단계로 증명할 수 있을까?
부등식도 첫 경우와 귀납 단계를 증명하면 된다. 다만 가정을 적용한 뒤 목표 부등식까지 이어지는 비교를 빠뜨리지 않아야 한다. 모든 자연수 에서
임을 보이자. 이면 양변이 2로 같아서 첫 경우가 성립한다. 임의의 자연수 에서 이라고 가정하고 양변에 양수 2를 곱하면
첫 부등호는 귀납가정에서 나온다. 마지막 부등호는 이므로 성립한다. 끝의 는 이어서 다음 경우의 목표와 같다. 두 단계가 완성되었으므로 식 (5)가 성립한다.
식 (3)은 합을 같은 값으로 바꾸는 등호의 연결이고, 식 (6)은 가정으로 얻은 하한에서 목표 하한까지 잇는 부등호의 연결이다. 어느 쪽이든 가정을 쓴 위치와 최종 목표를 함께 확인한다.
1이 아닌 수부터 성립하는 명제는 어떻게 증명할까?
첫 경우를 그 수로 잡고, 귀납 단계도 그 수 이상의 에서 보이면 된다. 예를 들어 인 모든 자연수에서
을 증명하자. 첫 경우 에서 이므로 성립한다.
임의의 자연수 에서 이라고 가정한다. 양변에 2를 곱하면 이므로, 이 보다 크다는 것만 보이면 된다.
식 (8)의 부등호는 에서 이기 때문이다. 따라서 이고, 두 단계에 의해 식 (7)은 에서 성립한다.
출발점이 왜 4일까? 그림 3처럼 식 (7)은 에서 참이지만 에서 으로 깨진다. 식 (8)의 값도 에서 이어서, 2에서 3으로 가는 연결이 실제로 끊긴다. 에서는 식 (8)이 양수지만 이 거짓이어서 출발점이 될 수 없다.
figures/power_vs_square.py배수임을 보이는 귀납 단계는 어떻게 쓸까?
다음 경우의 식을 귀납가정이 그대로 보이는 꼴로 쪼갠다. 모든 자연수 에서 이 3의 배수임을 보이자. 첫 경우 에서 이므로 성립한다.
임의의 자연수 에서 (은 자연수)이라고 가정한다. 다음 경우의 식 안에 을 일부러 만들면
셋째 줄에서 귀납가정을 썼다. 이 자연수이므로 도 3의 배수다. 두 단계에 의해 모든 자연수 에서 은 3의 배수다.
그림 4는 이 쪼개기를 막대로 그렸다. 는 길이 3인 막대 네 개와 3으로, 은 길이 15인 막대 네 개와 3으로 이루어진다. 쪼갠 조각이 모두 3의 배수이므로 전체도 3의 배수다.
figures/divisibility_bars.py수학적 귀납법은 첫 경우를 직접 보이고, 임의의 자연수 k에서 P(k)가 참이면 P(k+1)도 참임을 증명한다. 두 조건이 함께 있어야 정한 시작점 이후의 모든 자연수에 대한 결론을 얻는다.
수학적 귀납법에서 몇 개의 예가 맞으면 충분한가?
수학적 귀납법 없이 몇 개를 대입해 맞힌 것만으로는 모든 자연수에서 참이라고 할 수 없다. 예를 들어 은 부터 까지 모두 소수지만, 이면 이 되어 소수가 아니다. 귀납법은 사례를 많이 모으는 대신 임의의 에서 다음 경우로 넘어가는 이유를 증명한다.
수학적 귀납법에서 n=k일 때 성립한다고 가정하는 k는 무엇인가?
수학적 귀납법의 는 특정한 수가 아니라 아무 자연수나 하나 고른 것이다. 그래서 에 대한 계산 하나가 1→2, 2→3, 3→4, …의 연결을 한꺼번에 보인다. 를 3으로 정해 계산하면 하나만 보인 것이므로 귀납 단계가 끝나지 않는다.
수열의 귀납적 정의와 수학적 귀납법은 어떻게 다른가?
수열의 귀납적 정의는 첫 값과 다음 값을 만드는 규칙으로 수열을 정한다. 수학적 귀납법은 자연수 번호에 관한 주장이 참임을 증명한다. 둘 다 앞에서 다음으로 이어지지만, 값을 정하는 일과 명제를 증명하는 일은 구별한다.
수학적 귀납법의 흔한 오해
- 목표인 다음 식을 맞다고 놓고 정리해도 된다 — 은 보여야 할 대상이다. 식 (3)처럼 다음 합의 왼쪽에서 출발해, 가정한 앞부분만 바꿔 목표의 오른쪽을 얻는다.
- 첫 경우가 참이고 귀납 단계의 계산이 어디선가 통하면 증명이 끝난다 — 식 (7)은 이 참이고 식 (8)도 에서 양수지만, 에서 연결이 끊겨 에서 거짓이다. 귀납 단계는 첫 경우 이상의 모든 에서 성립해야 한다.
직접 해보기
- 모든 자연수 에 대해 임을 귀납법으로 증명하라. 귀납가정을 사용한 곳을 표시하라.
- 모든 자연수 에 대해 임을 귀납법으로 증명하라. 가정을 적용한 뒤 목표 하한까지 비교하라.
- 모든 자연수 에 대해 임을 귀납법으로 증명하라.
- 모든 자연수 에 대해 이 4의 배수임을 귀납법으로 증명하라.
- 인 모든 자연수에서 임을 증명하라. 에서는 왜 시작할 수 없는지도 말하라.
답 — 첫 경우, 가정, 다음 목표를 차례로 쓴다
- 이면 이다. 임의의 자연수 에서 앞 개 항의 합이 이라고 가정한다. 다음 항은 이다. 따라서 다음 합은 귀납가정으로 앞부분을 바꾼 뒤 이다. 이는 이므로 다음 경우가 성립한다. 두 단계에 의해 모든 자연수에서 성립한다.
- 이면 이다. 임의의 자연수 에서 이라고 가정하면, 양수 3을 곱해 을 얻는다. 이므로 이다. 첫 경우와 일반 단계를 함께 확인했으므로 증명이 끝난다.
- 이면 양변이 이다. 앞 개의 제곱합이 이라고 가정하고 을 더한다. 귀납가정으로 바꾼 합은 이다. 이는 을 넣은 오른쪽이므로 다음 경우가 성립한다. 같은 공식을 소거로 얻는 방법은 자연수의 거듭제곱의 합에 있다.
- 이면 다. (은 자연수)이라고 가정하면 이다. 둘째 등호 뒤에서 귀납가정을 썼고, 이 자연수이므로 다음 경우도 4의 배수다.
- 이면 이다. 에서 라고 가정하면 이고, 이므로 이다. 에서는 라서 부등식 가 성립하지 않아 첫 경우가 될 수 없다.
더 읽기
- Oscar Levin, Discrete Mathematics: An Open Introduction 3판 2.5절 — “Formalizing Proofs”와 예제 2.5.1. 귀납 단계를 조건명제로 읽고 가정을 대입하는 자리를 확인한다. 자료는 0부터 시작하는 경우도 다루지만 이 글의 기본 범위는 1부터다.
- AMSI, Proofs by induction — 인쇄 4–8쪽. 첫 경우와 모든 연결 조건이 각각 필요한 이유를 읽을 수 있다. 강한 귀납법이나 복잡한 점화식으로 범위를 넓히지 않는다.
영상 노트
- 00:00 도미노의 출발점과 연결을 따로 보기
- 00:40 식 (1)과 그림 1의 두 조건, 교과서의 (i)(ii) 서술
- 01:35 식 (2)의 첫 경우를 확인하기
- 02:10 식 (3) 첫 등호에서 귀납가정 사용하기, 그림 2의 10칸과 5칸
- 03:15 식 (4)에서 첫 경우가 빠진 논증 살피기
- 04:10 식 (5)를 식 (6)의 두 부등호로 이어 증명하기
- 05:10 식 (7)을 4부터 증명하고 식 (8)과 그림 3에서 끊긴 연결 찾기
- 06:30 식 (9)로 배수를 쪼개고 그림 4의 막대 읽기
- 07:30 n²−n+41의 반례와 임의의 k, 새 연습에 두 단계 적용하기
지도에서의 위치
- 2026-11-15 · 에이전트 초안 — 첫 경우와 일반 단계, 등식·부등식의 귀납가정
- 2026-11-16 · 전수 검수 반영 — 숫자 앞뒤 띄어쓰기 바로잡음, 교과서의 (i)(ii) 서술, 1이 아닌 수에서 시작하는 부등식, 배수 증명, 몇 개의 예가 깨지는 사례와 임의의 k 질문, 연습 5문항으로 보강 (에이전트 수정, 그림 1→4)
- 2026-11-16 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림