수학적 귀납법
대수
고등 · v1
· 🤖 LLM 버전
🧭
이 문서가 어렵다면 먼저 읽어 보세요 —
부등식 (중등)정의
수학적 귀납법(mathematical induction)은 자연수 $n$에 대한 명제 $p(n)$이 모든 자연수 $n$에 대하여 성립함을 증명하는 방법이다. 다음 두 단계를 모두 보이면 된다.
- 기초 단계: $n=1$일 때 $p(1)$이 성립한다.
- 귀납 단계: $n=k$일 때 $p(k)$가 성립한다고 가정하면($k$는 임의의 자연수), $n=k+1$일 때도 $p(k+1)$이 성립한다.
이 두 조건이 모두 확인되면, 모든 자연수 $n$에 대하여 $p(n)$이 성립한다고 결론지을 수 있다.
직관
수학적 귀납법은 도미노를 넘어뜨리는 원리와 같다. 첫 번째 도미노($n=1$)가 넘어지고, "어떤 도미노가 넘어지면 바로 다음 도미노도 넘어진다"는 규칙(귀납 단계)만 확인되면, 도미노가 끝없이 이어져 있어도 결국 모든 도미노가 넘어진다는 것을 알 수 있다. 무한히 많은 자연수 하나하나를 직접 대입해 확인할 수는 없지만, "처음 것이 되고, 하나가 되면 다음 것도 된다"는 두 가지만 보이면 전체가 성립함을 보장할 수 있다는 것이 핵심이다.
예시
예시 1 — 등식 $1+2+\cdots+n = \dfrac{n(n+1)}{2}$가 모든 자연수 $n$에서 성립함을 증명하자.
- 기초 단계: $n=1$일 때 좌변 $=1$, 우변 $=\dfrac{1\cdot2}{2}=1$이므로 성립한다.
- 귀납 단계: $n=k$일 때 $1+2+\cdots+k = \dfrac{k(k+1)}{2}$가 성립한다고 가정하자. 이 식의 양변에 $k+1$을 더하면
$$1+2+\cdots+k+(k+1) = \frac{k(k+1)}{2}+(k+1) = \frac{(k+1)(k+2)}{2}$$
이는 $n=k+1$일 때의 식과 같으므로 $n=k+1$일 때도 성립한다.
따라서 모든 자연수 $n$에 대하여 위 등식이 성립한다.
예시 2 — $3^n-1$이 2의 배수임을 증명하자.
- 기초 단계: $n=1$일 때 $3^1-1=2$이고, 2는 2의 배수이다.
- 귀납 단계: $n=k$일 때 $3^k-1$이 2의 배수라고 가정하면 $3^k-1=2m$($m$은 정수)로 쓸 수 있다. 그러면
$$3^{k+1}-1 = 3\cdot 3^k - 1 = 3(2m+1)-1 = 6m+2 = 2(3m+1)$$
이므로 $3^{k+1}-1$도 2의 배수이다.
따라서 모든 자연수 $n$에 대하여 $3^n-1$은 2의 배수이다.
⚠️ 흔한 실수
잘못된 생각: "$n=k$일 때 성립한다고 가정한다"는 부분을 이미 증명된 사실을 사용하는 것으로 착각한다.
→ 왜 틀렸는가: 귀납 단계는 "$p(k)$가 참이라면 $p(k+1)$도 참이다"라는 조건문 자체를 증명하는 것이다. $p(k)$ 자체가 참이라고 미리 확정 짓는 것이 아니라, 가정 하에 논리적 연결고리를 만드는 과정임을 이해해야 한다.
잘못된 생각: 귀납 단계만 보이고 기초 단계 확인을 생략하거나, 반대로 기초 단계만 확인하고 안심한다.
→ 왜 틀렸는가: 귀납 단계만으로는 "성립하는 도미노가 있다면 다음 것도 넘어진다"는 것만 보일 뿐, 애초에 첫 도미노가 넘어지는지는 알 수 없다. 두 단계는 반드시 모두 필요하다.
잘못된 생각: $n=k+1$일 때의 식을 귀납적 가정($p(k)$)을 전혀 사용하지 않고 처음부터 다시 계산해서 증명하려 한다.
→ 왜 틀렸는가: 이는 수학적 귀납법이 아니라 그냥 각 경우를 따로 증명하는 것과 같아, $n=k+1$과 $p(k)$ 사이의 연결을 보이지 못한다. 반드시 가정한 $p(k)$의 식을 변형해 $p(k+1)$을 이끌어내야 한다.
확인 문제
- 수학적 귀납법으로 어떤 명제를 증명할 때 반드시 확인해야 하는 두 단계는 무엇인가?
- $2+4+6+\cdots+2n = n(n+1)$임을 수학적 귀납법으로 증명하시오.
- $n=k$일 때 성립을 가정하고 $n=k+1$일 때를 유도했지만 기초 단계($n=1$)를 확인하지 않았다면, 이 증명은 완성된 것인가?
정답 보기
- 기초 단계($n=1$일 때 성립)와 귀납 단계($n=k$일 때 성립을 가정하면 $n=k+1$일 때도 성립함을 보이는 것).
- 기초 단계: $n=1$일 때 좌변 $=2$, 우변 $=1\cdot2=2$로 성립. 귀납 단계: $n=k$일 때 $2+4+\cdots+2k=k(k+1)$을 가정하면, 양변에 $2(k+1)$을 더해 $2+4+\cdots+2k+2(k+1) = k(k+1)+2(k+1) = (k+1)(k+2)$가 되어 $n=k+1$일 때도 성립한다.
- 아니다. 귀납 단계만으로는 첫 자연수에서 명제가 실제로 성립하는지 보장할 수 없으므로, 기초 단계를 반드시 확인해야 증명이 완성된다.
관련 개념
- 명제 — 참·거짓을 판별할 수 있는 문장으로, 귀납법으로 증명하는 대상인 $p(n)$ 자체가 명제이다.
- 수열 — 자연수 $n$에 대해 정의된 수열의 일반항이나 합의 공식을 귀납법으로 증명하는 경우가 많다.
- 등차수열, 등비수열 — 이 수열들의 합 공식을 귀납법으로 검증할 수 있다.
- 이항정리 — 전개식의 계수 공식을 증명할 때 수학적 귀납법이 활용되기도 한다.
- 부등식 — 자연수에 대한 부등식(예: $2^n>n$)을 증명하는 데 수학적 귀납법이 널리 쓰인다.