수학적 귀납법
“귀납법은 무한한 도미노를 두 번의 확인으로 전부 쓰러뜨리는 기술이다.”
수식
[ P(1) ∧ ( P(k) ⟹ P(k+1) ) ] ⟹ ∀n ≥ 1, P(n)읽는 법: 첫 번째 경우가 참이고, 어떤 경우가 참이면 그다음도 참임을 보이면, 모든 자연수에서 참이 된다
- P(n)
- — 자연수 n에 대해 증명하려는 명제
- P(1)
- — 첫 번째 도미노를 쓰러뜨리기 — 출발점이 참
- P(k) ⟹ P(k+1)
- — 한 도미노가 다음 도미노를 쓰러뜨림
- ∀n ≥ 1
- — 그러므로 모든 자연수에서 성립
이야기의 시작
무한히 많은 경우를 단 두 줄로 증명한다 — 첫 도미노를 쓰러뜨리고, 각 도미노가 다음을 쓰러뜨림을 보이면 끝.
쉬운 말로
수학적 귀납법은 '모든 자연수 n에서 참'인 명제를 증명하는 방법이다. (1) n=1에서 참임을 보이고(기초), (2) n=k에서 참이라 가정하면 n=k+1에서도 참임을 보이면(귀납), 도미노처럼 전부 참이 된다.
직관
길게 늘어선 무한한 도미노를 생각하라. 하나하나 손으로 쓰러뜨릴 수는 없다. 하지만 두 가지만 확인하면 된다 — 첫 도미노가 쓰러지고, '어떤 도미노든 쓰러지면 바로 옆도 쓰러진다.' 그러면 첫 번째가 두 번째를, 두 번째가 세 번째를… 무한히 이어져 전부 쓰러진다. 무한을 유한한 두 확인으로 정복한다.
어떻게 만들어지나
두 부품 — 기초 단계와 귀납 단계. 기초는 출발점(보통 n=1)이 참임을 직접 확인한다. 귀납은 'P(k)가 참'이라는 귀납 가정을 딛고 P(k+1)을 끌어낸다. 둘 다 있어야 한다: 첫 도미노 없이는 아무것도 안 쓰러지고, 연쇄 없이는 하나만 쓰러진다.
예시
1+2+⋯+n = n(n+1)/2 를 증명. 기초 n=1: 좌변 1 = 1·2/2 = 1 ✓. 귀납: 1+⋯+k = k(k+1)/2 라 가정하면, 1+⋯+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2. 이는 n=k+1 공식과 일치 ✓. 따라서 모든 n에서 성립.
흔한 오해
귀납 가정 'P(k)가 참이라 하자'는 결론을 미리 가정하는 순환논법처럼 보이지만 아니다. 우리는 P(k)가 실제로 참이라고 주장하는 게 아니라, '만약 참이라면 다음도 참'이라는 조건부 연결고리(도미노 간격)만 증명하는 것이다.
어디에 쓰나
합·부등식 공식 증명, 알고리즘의 정당성(재귀·반복문) 검증, 자료구조와 컴파일러의 정확성 증명, 정수론·조합론의 무수한 정리 — 무한한 경우를 다루는 컴퓨터과학과 수학 어디에나 쓰인다.
어디서 왔나
파스칼이 17세기에 파스칼의 삼각형을 다루며 명시적으로 사용했고, 19세기 페아노가 자연수의 공리로 못박아 논리의 기둥으로 삼았다.
선행 개념
확인 문제
수학적 귀납법에서 기초 단계 말고 반드시 증명해야 하는 것은?
- P(k) 가 참이면 P(k+1) 도 참임✓
- 어떤 큰 n 하나에서 P(n) 이 참임
- P(n) 이 결코 거짓이 아님
- 더 증명할 것이 없다
연습
공식 1+2+⋯+n = n(n+1)/2 를 이용해 1+2+⋯+10 을 구하라.
정답: 55
- n=10 대입: 10·11/2
- = 110/2 = 55
핵심: 귀납법으로 증명한 공식은 대입만 하면 된다.
1+2+⋯+100 을 구하라.
정답: 5050
- 100·101/2
- = 10100/2 = 5050
핵심: 가우스가 어릴 때 순식간에 풀었다는 그 합.
처음 n개의 홀수의 합 1+3+5+⋯+(2n−1) = n² 이다. n=5 일 때 값을 구하라.
정답: 25
- 1+3+5+7+9 = 25
- = 5² = 25
핵심: 홀수의 합은 완전제곱 — 귀납법의 고전 예제.
1+2+⋯+n = n(n+1)/2 를 수학적 귀납법으로 증명하라(기초 + 귀납 단계를 노트에 적어라).
정답: undefined
- 기초 n=1: 1 = 1·2/2 = 1 ✓
- 가정: 1+⋯+k = k(k+1)/2
- +(k+1): k(k+1)/2 + (k+1) = (k+1)(k+2)/2 = n=k+1 공식 ✓
핵심: 기초 + 귀납 = 무한한 경우의 완전한 증명.