미적분수학적 귀납법#101

수학적 귀납법

Mathematical Induction

수학적 귀납법은 첫 경우가 참임을 보이고, 임의의 자연수에서 다음 자연수로 참이 이어짐을 증명하는 방법이다. 1+2+…+n=n(n+1)/2를 예로 귀납가정을 쓰는 자리를 찾는다. 부등식과 배수 명제, 1이 아닌 수에서 시작하는 증명, 몇 번의 대입 확인과 일반 증명의 차이를 다룬다.

읽는 시간
약 7분
선수 개념
수열의 귀납적 정의모든과 어떤등차수열의 합

직관 — 출발점과 끊기지 않는 연결

직관

도미노를 한 줄로 세웠다고 하자. 첫 조각을 넘어뜨리는 일과, 어느 조각이 넘어져도 바로 다음 조각을 넘어뜨리는 배치는 서로 다른 조건이다. 두 조건이 함께 있어야 뒤의 조각까지 차례로 이어진다.

첫 조각은 증명의 첫 경우, 이웃 조각의 연결은 한 경우가 참이면 다음 경우도 참이라는 논증에 대응한다. 그림을 길게 그리는 것이 증명은 아니다. 어느 번호에서도 끊기지 않는 이유를 일반적인 문자로 보여야 한다. 이 방법을 배우면 수열의 합처럼 자연수마다 하나씩 주어진 주장을 증명할 수 있다.

수학적 귀납법은 첫 경우와 다음 경우의 연결로 증명한다

수학적 귀납법은 자연수에 관한 명제가 첫 경우에서 참이고, 임의의 번호에서 참이면 다음 번호에서도 참임을 보여 전체 범위에서 성립함을 증명하는 방법이다. 여기서는 자연수를 1,2,3,…1,2,3,\ldots로 놓고, 번호 nn에 관한 명제를 P(n)P(n)이라 쓴다.

P(1)이 참이다.모든 자연수 k에 대해P(k)⇒P(k+1).∴ P(n)은 모든 자연수 n에서 참이다.(1)\begin{gathered} P(1)\text{이 참이다.}\\ \text{모든 자연수 }k\text{에 대해}\quad P(k)\Rightarrow P(k+1).\\[2pt] \therefore\ P(n)\text{은 모든 자연수 }n\text{에서 참이다.} \end{gathered} \tag{1}

화살표 ⇒\Rightarrow는 ‘앞의 명제가 참이면 뒤의 명제도 참이다’를 뜻한다. 첫 조건이 출발점을 주고, 둘째 조건을 k=1,2,3,…k=1,2,3,\ldots에 차례로 적용할 수 있다. 이 두 조건으로 결론을 얻는 원리가 수학적 귀납법이다.

정의
기호이름원어뜻
P(n)P(n)n에 관한 명제statement about n번호 n을 넣었을 때 참·거짓을 판단할 주장
P(1)P(1)첫 경우base case직접 참임을 확인하는 출발점
kk임의의 자연수arbitrary natural number특정 값에 고정하지 않은 번호
P(k)P(k)귀납가정induction hypothesis다음 경우를 보일 때 전제로 놓는 주장
P(k)⇒P(k+1)P(k)\Rightarrow P(k+1)귀납 단계inductive step한 경우에서 다음 경우로 이어지는 논증

교과서는 같은 내용을 ‘(i) n=1n=1일 때 성립한다. (ii) n=kn=k일 때 성립한다고 가정하면 n=k+1n=k+1일 때도 성립한다’로 쓴다. (ii)의 가정이 이 페이지의 귀납가정 P(k)P(k)다. 결론의 ‘모든 자연수’는 모든과 어떤에서 배운 ‘모든’이다.

그림 1의 윗줄에서는 첫 경우가 출발점이다. 아랫줄은 어떤 k≥1k\ge1에서도 통하는 연결 규칙을 따로 표시한다. ‘첫 세 경우를 확인했다’와 ‘모든 연결이 성립한다’는 다른 말이다.

파란 P(1)은 직접 확인할 첫 경우다. 아랫줄의 주황 화살표는 모든 자연수 k≥1에서 P(k)가 참이면 P(k+1)도 참임을 증명해야 한다는 뜻이다. 이 규칙을 윗줄의 각 연결에 적용한다. 몇 개의 상자를 그린 사실만으로 나머지가 증명되지는 않는다.
그림 1 파란 P(1)은 직접 확인할 첫 경우다. 아랫줄의 주황 화살표는 모든 자연수 k≥1에서 P(k)가 참이면 P(k+1)도 참임을 증명해야 한다는 뜻이다. 이 규칙을 윗줄의 각 연결에 적용한다. 몇 개의 상자를 그린 사실만으로 나머지가 증명되지는 않는다. figures/base_and_step.py

자연수의 합에서 귀납가정은 어디에 쓰일까?

귀납가정은 이미 더한 앞부분을 간단한 식으로 바꾸는 자리에 쓰인다. 등차수열의 합에서 배운 공식을 이번에는 귀납법으로 증명해 보자. 증명할 명제는

P(n):1+2+⋯+n=n(n+1)2.(2)P(n):\quad 1+2+\cdots+n=\frac{n(n+1)}2. \tag{2}

첫 경우 n=1n=1에서 왼쪽은 1, 오른쪽은 1×2/2=11\times2/2=1이다. 따라서 P(1)P(1)은 참이다.

다음으로 임의의 자연수 kk를 잡고, P(k)P(k)가 참이라고 가정하자. 즉 1+2+⋯+k=k(k+1)/21+2+\cdots+k=k(k+1)/2라고 놓는다. 목표인 P(k+1)P(k+1)의 왼쪽은 여기에 새 항 k+1k+1을 더한 합이다.

1+2+⋯+k+(k+1)=k(k+1)2⏟귀납가정+(k+1)=k(k+1)+2(k+1)2=(k+1)(k+2)2.(3)\begin{aligned} 1+2+\cdots+k+(k+1) &=\underbrace{\frac{k(k+1)}2}_{\text{귀납가정}}+(k+1)\\ &=\frac{k(k+1)+2(k+1)}2\\ &=\frac{(k+1)(k+2)}2. \end{aligned} \tag{3}

식 (3)의 첫 등호에서 귀납가정을 사용했다. 마지막 식은 식 (2)의 nn을 k+1k+1로 바꾼 오른쪽과 정확히 같다. 따라서 P(k)P(k)가 참이면 P(k+1)P(k+1)도 참이다. 첫 경우와 귀납 단계를 모두 보였으므로 식 (2)는 모든 자연수 nn에서 성립한다.

예를 들어 k=4k=4일 때는 앞 네 항의 합 10에 다음 항 5를 더해 15가 된다. 그림 2는 이 덧셈을 칸 수로 보여 준다. 계단 모양 10칸이 귀납가정이 알려 주는 앞부분이고, 새로 붙인 한 줄 5칸이 새 항 k+1k+1이다.

k=4일 때 식 (3)을 칸 수로 나타냈다. 회색 계단 10칸은 귀납가정의 k(k+1)/2, 파란 한 줄 5칸은 새 항 k+1이고, 합친 15칸이 (k+1)(k+2)/2와 같다.
그림 2 k=4k=4일 때 식 (3)을 칸 수로 나타냈다. 회색 계단 10칸은 귀납가정의 k(k+1)/2k(k+1)/2, 파란 한 줄 5칸은 새 항 k+1k+1이고, 합친 15칸이 (k+1)(k+2)/2(k+1)(k+2)/2와 같다. figures/triangle_step.py

이 그림은 식 (3)의 동작을 읽는 예다. 증명을 완성하는 것은 4라는 한 값이 아니라 임의의 kk에 대해 쓴 전개다.

참이라고 가정하면 결론을 미리 믿는 것 아닌가?

귀납가정은 전체 결론을 선언하는 일이 아니다. 조건명제 ‘P(k)P(k)가 참이면 P(k+1)P(k+1)도 참이다’를 증명하기 위해 앞쪽을 잠시 전제로 삼는 것이다. 다음 경우까지 이미 참이라고 가정해서는 안 된다.

이 차이는 첫 경우를 빼면 드러난다. 틀린 주장 Q(n):1+2+⋯+n=n(n+1)/2+1Q(n):1+2+\cdots+n=n(n+1)/2+1을 생각해 보자. Q(k)Q(k)를 가정해 양변에 k+1k+1을 더하면

k(k+1)2+1+(k+1)=(k+1)(k+2)2+1(4)\frac{k(k+1)}2+1+(k+1) =\frac{(k+1)(k+2)}2+1 \tag{4}

이어서 같은 형태의 Q(k+1)Q(k+1)을 얻는다. 하지만 Q(1)Q(1)은 1=21=2라는 거짓 명제다. 연결 형식이 유지되어도 출발점이 없으면 결론을 얻지 못한다. 식 (2)의 증명에서 첫 경우를 따로 확인한 이유다.

부등식도 같은 두 단계로 증명할 수 있을까?

부등식도 첫 경우와 귀납 단계를 증명하면 된다. 다만 가정을 적용한 뒤 목표 부등식까지 이어지는 비교를 빠뜨리지 않아야 한다. 모든 자연수 nn에서

2n≥n+1(5)2^n\ge n+1 \tag{5}

임을 보이자. n=1n=1이면 양변이 2로 같아서 첫 경우가 성립한다. 임의의 자연수 kk에서 2k≥k+12^k\ge k+1이라고 가정하고 양변에 양수 2를 곱하면

2k+1=2⋅2k≥2(k+1)=2k+2≥k+2.(6)2^{k+1}=2\cdot2^k \ge 2(k+1)=2k+2 \ge k+2. \tag{6}

첫 부등호는 귀납가정에서 나온다. 마지막 부등호는 (2k+2)−(k+2)=k≥1(2k+2)-(k+2)=k\ge1이므로 성립한다. 끝의 k+2k+2는 (k+1)+1(k+1)+1이어서 다음 경우의 목표와 같다. 두 단계가 완성되었으므로 식 (5)가 성립한다.

식 (3)은 합을 같은 값으로 바꾸는 등호의 연결이고, 식 (6)은 가정으로 얻은 하한에서 목표 하한까지 잇는 부등호의 연결이다. 어느 쪽이든 가정을 쓴 위치와 최종 목표를 함께 확인한다.

1이 아닌 수부터 성립하는 명제는 어떻게 증명할까?

첫 경우를 그 수로 잡고, 귀납 단계도 그 수 이상의 kk에서 보이면 된다. 예를 들어 n≥4n\ge4인 모든 자연수에서

2n≥n2(7)2^n\ge n^2 \tag{7}

을 증명하자. 첫 경우 n=4n=4에서 24=16=422^4=16=4^2이므로 성립한다.

임의의 자연수 k≥4k\ge4에서 2k≥k22^k\ge k^2이라고 가정한다. 양변에 2를 곱하면 2k+1≥2k22^{k+1}\ge2k^2이므로, 2k22k^2이 (k+1)2(k+1)^2보다 크다는 것만 보이면 된다.

2k2−(k+1)2=(k−1)2−2≥32−2=7>0(8)2k^2-(k+1)^2=(k-1)^2-2\ge3^2-2=7>0 \tag{8}

식 (8)의 부등호는 k≥4k\ge4에서 k−1≥3k-1\ge3이기 때문이다. 따라서 2k+1≥2k2>(k+1)22^{k+1}\ge2k^2>(k+1)^2이고, 두 단계에 의해 식 (7)은 n≥4n\ge4에서 성립한다.

출발점이 왜 4일까? 그림 3처럼 식 (7)은 n=1,2n=1,2에서 참이지만 n=3n=3에서 23=8<9=322^3=8<9=3^2으로 깨진다. 식 (8)의 값도 k=2k=2에서 1−2=−11-2=-1이어서, 2에서 3으로 가는 연결이 실제로 끊긴다. k=3k=3에서는 식 (8)이 양수지만 P(3)P(3)이 거짓이어서 출발점이 될 수 없다.

n=1부터 7까지 2^n과 n^2을 비교한 표다. 그린 범위에서 2^n<n^2인 것은 n=3(주황)뿐이다. 주황 점선은 2에서 3으로 가는 연결이 끊긴 곳이고, 파란 화살표는 첫 경우 n=4에서 시작한 귀납 단계다.
그림 3 n=1n=1부터 77까지 2n2^n과 n2n^2을 비교한 표다. 그린 범위에서 2n<n22^n<n^2인 것은 n=3n=3(주황)뿐이다. 주황 점선은 2에서 3으로 가는 연결이 끊긴 곳이고, 파란 화살표는 첫 경우 n=4n=4에서 시작한 귀납 단계다. figures/power_vs_square.py

배수임을 보이는 귀납 단계는 어떻게 쓸까?

다음 경우의 식을 귀납가정이 그대로 보이는 꼴로 쪼갠다. 모든 자연수 nn에서 4n−14^n-1이 3의 배수임을 보이자. 첫 경우 n=1n=1에서 41−1=34^1-1=3이므로 성립한다.

임의의 자연수 kk에서 4k−1=3m4^k-1=3m(mm은 자연수)이라고 가정한다. 다음 경우의 식 안에 4k−14^k-1을 일부러 만들면

4k+1−1=4⋅4k−4+3=4(4k−1)+3=4⋅3m+3=3(4m+1)(9)\begin{aligned} 4^{k+1}-1&=4\cdot4^k-4+3\\ &=4(4^k-1)+3\\ &=4\cdot3m+3=3(4m+1) \end{aligned} \tag{9}

셋째 줄에서 귀납가정을 썼다. 4m+14m+1이 자연수이므로 4k+1−14^{k+1}-1도 3의 배수다. 두 단계에 의해 모든 자연수 nn에서 4n−14^n-1은 3의 배수다.

그림 4는 이 쪼개기를 막대로 그렸다. 42−1=154^2-1=15는 길이 3인 막대 네 개와 3으로, 43−1=634^3-1=63은 길이 15인 막대 네 개와 3으로 이루어진다. 쪼갠 조각이 모두 3의 배수이므로 전체도 3의 배수다.

4^n-1을 n=1,2,3에 대해 길이로 그렸다. 아랫줄 막대는 바로 윗줄 막대 네 개(회색)와 길이 3(파랑)으로 이루어지고, 눈금은 3마다 찍었다. 그래서 3, 15, 63은 모두 3의 배수다.
그림 4 4n−14^n-1을 n=1,2,3n=1,2,3에 대해 길이로 그렸다. 아랫줄 막대는 바로 윗줄 막대 네 개(회색)와 길이 3(파랑)으로 이루어지고, 눈금은 3마다 찍었다. 그래서 3, 15, 63은 모두 3의 배수다. figures/divisibility_bars.py
핵심

수학적 귀납법은 첫 경우를 직접 보이고, 임의의 자연수 k에서 P(k)가 참이면 P(k+1)도 참임을 증명한다. 두 조건이 함께 있어야 정한 시작점 이후의 모든 자연수에 대한 결론을 얻는다.

수학적 귀납법에서 몇 개의 예가 맞으면 충분한가?

수학적 귀납법 없이 몇 개를 대입해 맞힌 것만으로는 모든 자연수에서 참이라고 할 수 없다. 예를 들어 n2−n+41n^2-n+41은 n=1n=1부터 4040까지 모두 소수지만, n=41n=41이면 412=168141^2=1681이 되어 소수가 아니다. 귀납법은 사례를 많이 모으는 대신 임의의 kk에서 다음 경우로 넘어가는 이유를 증명한다.

수학적 귀납법에서 n=k일 때 성립한다고 가정하는 k는 무엇인가?

수학적 귀납법의 kk는 특정한 수가 아니라 아무 자연수나 하나 고른 것이다. 그래서 kk에 대한 계산 하나가 1→2, 2→3, 3→4, …의 연결을 한꺼번에 보인다. kk를 3으로 정해 계산하면 P(3)⇒P(4)P(3)\Rightarrow P(4) 하나만 보인 것이므로 귀납 단계가 끝나지 않는다.

수열의 귀납적 정의와 수학적 귀납법은 어떻게 다른가?

수열의 귀납적 정의는 첫 값과 다음 값을 만드는 규칙으로 수열을 정한다. 수학적 귀납법은 자연수 번호에 관한 주장이 참임을 증명한다. 둘 다 앞에서 다음으로 이어지지만, 값을 정하는 일과 명제를 증명하는 일은 구별한다.

수학적 귀납법의 흔한 오해

  • 목표인 다음 식을 맞다고 놓고 정리해도 된다 — P(k+1)P(k+1)은 보여야 할 대상이다. 식 (3)처럼 다음 합의 왼쪽에서 출발해, 가정한 앞부분만 바꿔 목표의 오른쪽을 얻는다.
  • 첫 경우가 참이고 귀납 단계의 계산이 어디선가 통하면 증명이 끝난다 — 식 (7)은 P(1)P(1)이 참이고 식 (8)도 k≥3k\ge3에서 양수지만, k=2k=2에서 연결이 끊겨 n=3n=3에서 거짓이다. 귀납 단계는 첫 경우 이상의 모든 kk에서 성립해야 한다.

직접 해보기

  1. 모든 자연수 nn에 대해 3+7+⋯+(4n−1)=n(2n+1)3+7+\cdots+(4n-1)=n(2n+1)임을 귀납법으로 증명하라. 귀납가정을 사용한 곳을 표시하라.
  2. 모든 자연수 nn에 대해 3n≥2n+13^n\ge2n+1임을 귀납법으로 증명하라. 가정을 적용한 뒤 목표 하한까지 비교하라.
  3. 모든 자연수 nn에 대해 12+22+⋯+n2=n(n+1)(2n+1)61^2+2^2+\cdots+n^2=\dfrac{n(n+1)(2n+1)}6임을 귀납법으로 증명하라.
  4. 모든 자연수 nn에 대해 5n−15^n-1이 4의 배수임을 귀납법으로 증명하라.
  5. n≥5n\ge5인 모든 자연수에서 2n>4n2^n>4n임을 증명하라. n=4n=4에서는 왜 시작할 수 없는지도 말하라.
답 — 첫 경우, 가정, 다음 목표를 차례로 쓴다
  1. n=1n=1이면 3=1×33=1\times3이다. 임의의 자연수 kk에서 앞 kk개 항의 합이 k(2k+1)k(2k+1)이라고 가정한다. 다음 항은 4(k+1)−1=4k+34(k+1)-1=4k+3이다. 따라서 다음 합은 귀납가정으로 앞부분을 바꾼 뒤 k(2k+1)+(4k+3)=2k2+5k+3=(k+1)(2k+3)k(2k+1)+(4k+3)=2k^2+5k+3=(k+1)(2k+3)이다. 이는 (k+1){2(k+1)+1}(k+1)\{2(k+1)+1\}이므로 다음 경우가 성립한다. 두 단계에 의해 모든 자연수에서 성립한다.
  2. n=1n=1이면 3=2×1+13=2\times1+1이다. 임의의 자연수 kk에서 3k≥2k+13^k\ge2k+1이라고 가정하면, 양수 3을 곱해 3k+1≥6k+33^{k+1}\ge6k+3을 얻는다. (6k+3)−(2k+3)=4k≥0(6k+3)-(2k+3)=4k\ge0이므로 3k+1≥2k+3=2(k+1)+13^{k+1}\ge2k+3=2(k+1)+1이다. 첫 경우와 일반 단계를 함께 확인했으므로 증명이 끝난다.
  3. n=1n=1이면 양변이 1=1⋅2⋅3/61=1\cdot2\cdot3/6이다. 앞 kk개의 제곱합이 k(k+1)(2k+1)/6k(k+1)(2k+1)/6이라고 가정하고 (k+1)2(k+1)^2을 더한다. 귀납가정으로 바꾼 합은 {k(k+1)(2k+1)+6(k+1)2}/6=(k+1)(2k2+7k+6)/6=(k+1)(k+2)(2k+3)/6\{k(k+1)(2k+1)+6(k+1)^2\}/6=(k+1)(2k^2+7k+6)/6=(k+1)(k+2)(2k+3)/6이다. 이는 n=k+1n=k+1을 넣은 오른쪽이므로 다음 경우가 성립한다. 같은 공식을 소거로 얻는 방법은 자연수의 거듭제곱의 합에 있다.
  4. n=1n=1이면 5−1=45-1=4다. 5k−1=4m5^k-1=4m(mm은 자연수)이라고 가정하면 5k+1−1=5(5k−1)+4=5⋅4m+4=4(5m+1)5^{k+1}-1=5(5^k-1)+4=5\cdot4m+4=4(5m+1)이다. 둘째 등호 뒤에서 귀납가정을 썼고, 5m+15m+1이 자연수이므로 다음 경우도 4의 배수다.
  5. n=5n=5이면 32>2032>20이다. k≥5k\ge5에서 2k>4k2^k>4k라고 가정하면 2k+1>8k2^{k+1}>8k이고, 8k−(4k+4)=4k−4>08k-(4k+4)=4k-4>0이므로 2k+1>4(k+1)2^{k+1}>4(k+1)이다. n=4n=4에서는 24=16=4⋅42^4=16=4\cdot4라서 부등식 >>가 성립하지 않아 첫 경우가 될 수 없다.

더 읽기

  • 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, 새 연습에 두 단계 적용하기

지도에서의 위치

이 페이지의 기록
  1. 2026-11-15 · 에이전트 초안 — 첫 경우와 일반 단계, 등식·부등식의 귀납가정
  2. 2026-11-16 · 전수 검수 반영 — 숫자 앞뒤 띄어쓰기 바로잡음, 교과서의 (i)(ii) 서술, 1이 아닌 수에서 시작하는 부등식, 배수 증명, 몇 개의 예가 깨지는 사례와 임의의 k 질문, 연습 5문항으로 보강 (에이전트 수정, 그림 1→4)
  3. 2026-11-16 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림